Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hello. I'd like to solve the following optimization problem.

$P_i$ is a 6x6 matrix
$X$, $Y$ is a 6xk matrix
$w_i$ is a kx1 vector
$diag(w_i)$ is a square diagonal matrix with diagonal entries equal to $w_i$

$\min_{w_i} ~ ||P_i - X diag(w_i) Y^T||_F^2$

So the question is how to optimize over $diag(w_i)$.

Does anyone know how to take derivative wrt a diagonal matrix?

Or would it work if treat $diag(w_i)$ as a square matrix, solve it,
and then set off-diagonal entries to zeros?

share|improve this question
    
You can certainly take derivatives with respect to matrix parameters, just using the usual multivariable calculus approach. However, it's not clear to me that this is the best way to approach your problem. –  Yemon Choi Sep 10 '11 at 1:14
    
Also: what values of $k$ are you (most) interested in? –  Yemon Choi Sep 10 '11 at 1:16
    
Lastly for now: are all vectors, matrices etc. real-valued here? –  Yemon Choi Sep 10 '11 at 1:16
add comment

1 Answer 1

up vote 2 down vote accepted

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

$\min_{w} \| P-X \mbox{diag}(w) Y^{T} \|_{F} $.

You may have a whole bunch of these problems to solve as $i$ varies over some index set, but each can be solved separately.

This is a linear least squares problem in disguise.

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.

Also note that

$X \mbox{diag}(w) Y^{T}=\sum_{j=1}^{k} w_{j} X_{j}Y_{j}^{T}$

where $X_{j}$ is the $j$th column of $X$, and $Y_{j}$ is the $j$th column of $Y$.

Now, your problem can be written as

$\min_{w} \| P- \sum_{j=1}^{k} w_{j} X_{j}Y_{j}^{T} \|_{F}$.

Let $H_{j}=X_{j}Y_{j}^{T}$, for $j=1, 2, \ldots, k$. We now have

$\min_{w} \| P - \sum_{j=1}^{k} w_{j} H_{j} \|_{F}. $

Transforming this into vector form, this becomes

$\min_{w} \| \mbox{vec}(P) - \sum_{j=1}^{k} w_{j} \mbox{vec}(H_{j}) \|_{2}$.

Let $A$ be the matrix whose columns are given by

$A_{j}=\mbox{vec}(H_{j})$.

Then the optimization problem can be written as

$\min_{w} \| \mbox{vec}(P) - Aw \|_{2} $.

which is a conventional linear least squares problem.

share|improve this answer
    
Wow I admire your intuition. At the moment I asked the question I had no idea how to approached the problem but now it turns out to be one of the easiest problems in Linear Algebra. Thank you very much. –  Jackson Sep 10 '11 at 8:29
    
I'd argue that this wasn't so much a matter of intuition as knowing some tricks that are frequently useful in convex optimization. I was very familiar with the idea of using $\mbox{vec}()$ to convert the Frobenius norm of a matrix into the 2-norm of a vector and with the idea of writing the the matrix triple product with a diagonal matrix in the middle as a sum of outer products. If you'd like to learn more of this, I'd strongly encourage you to read the textbook "Convex Optimization" by Vandenberghe and Boyd. –  Brian Borchers Sep 10 '11 at 16:00
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.