How do I optimize over (or take derivative wrt) a square diagonal matrix? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T09:30:09Z http://mathoverflow.net/feeds/question/75051 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/75051/how-do-i-optimize-over-or-take-derivative-wrt-a-square-diagonal-matrix How do I optimize over (or take derivative wrt) a square diagonal matrix? Jackson 2011-09-09T23:24:46Z 2011-09-10T04:36:44Z <p>Hello. I'd like to solve the following optimization problem.</p> <p>$P_i$ is a 6x6 matrix<br> $X$, $Y$ is a 6xk matrix<br> $w_i$ is a kx1 vector<br> $diag(w_i)$ is a square diagonal matrix with diagonal entries equal to $w_i$</p> <p>$\min_{w_i} ~ ||P_i - X diag(w_i) Y^T||_F^2$</p> <p>So the question is how to optimize over $diag(w_i)$.</p> <p>Does anyone know how to take derivative wrt a diagonal matrix?</p> <p>Or would it work if treat $diag(w_i)$ as a square matrix, solve it,<br> and then set off-diagonal entries to zeros?</p> http://mathoverflow.net/questions/75051/how-do-i-optimize-over-or-take-derivative-wrt-a-square-diagonal-matrix/75066#75066 Answer by Brian Borchers for How do I optimize over (or take derivative wrt) a square diagonal matrix? Brian Borchers 2011-09-10T04:28:23Z 2011-09-10T04:36:44Z <p>Your notation is somewhat confusing, in that you apply the subscript $i$ to $w$, and have a vector $w_{i}$, but don't use $i$ in any meaningful way in your problem. I'm going to take the liberty of rewriting the problem as </p> <p>$\min_{w} \| P-X \mbox{diag}(w) Y^{T} \|_{F}$.</p> <p>You may have a whole bunch of these problems to solve as $i$ varies over some index set, but each can be solved separately.</p> <p>This is a linear least squares problem in disguise. </p> <p>The key to seeing this is to recognize that the Frobenius norm of a matrix $Z$ is the two norm of the vector $\mbox{vec}(Z)$ obtained from the matrix $Z$ by stacking the columns of $Z$ one on top of another. </p> <p>Also note that </p> <p>$X \mbox{diag}(w) Y^{T}=\sum_{j=1}^{k} w_{j} X_{j}Y_{j}^{T}$</p> <p>where $X_{j}$ is the $j$th column of $X$, and $Y_{j}$ is the $j$th column of $Y$.</p> <p>Now, your problem can be written as </p> <p>$\min_{w} \| P- \sum_{j=1}^{k} w_{j} X_{j}Y_{j}^{T} \|_{F}$.</p> <p>Let $H_{j}=X_{j}Y_{j}^{T}$, for $j=1, 2, \ldots, k$. We now have</p> <p>$\min_{w} \| P - \sum_{j=1}^{k} w_{j} H_{j} \|_{F}.$</p> <p>Transforming this into vector form, this becomes</p> <p>$\min_{w} \| \mbox{vec}(P) - \sum_{j=1}^{k} w_{j} \mbox{vec}(H_{j}) \|_{2}$.</p> <p>Let $A$ be the matrix whose columns are given by</p> <p>$A_{j}=\mbox{vec}(H_{j})$. </p> <p>Then the optimization problem can be written as </p> <p>$\min_{w} \| \mbox{vec}(P) - Aw \|_{2}$.</p> <p>which is a conventional linear least squares problem. </p>