3
$\begingroup$

I would like to solve the following optimization problem in $k$-vector $w_i$

$$ \min_{w_i} \quad \left\|P_i - X \mbox{diag} (w_i) Y^T \right\|_F^2 $$

where $P_i$ is a $6 \times 6$ matrix, $X$ and $Y$ are $6 \times k$ matrices, and $\mbox{diag}(w_i)$ is a (square) diagonal matrix whose main diagonal is $w_i$. How to optimize over $\mbox{diag} (w_i)$? Does anyone know how to take derivative wrt a diagonal matrix?

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Yemon Choi
    Sep 10, 2011 at 1:14
  • $\begingroup$ Also: what values of $k$ are you (most) interested in? $\endgroup$
    – Yemon Choi
    Sep 10, 2011 at 1:16
  • 1
    $\begingroup$ Lastly for now: are all vectors, matrices etc. real-valued here? $\endgroup$
    – Yemon Choi
    Sep 10, 2011 at 1:16

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Jackson
    Sep 10, 2011 at 8:29
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 10, 2011 at 16:00
  • $\begingroup$ You mentioned that $X diag(w)Y=\sum_{j=1}^kw_jX_jY_j^T$, where $X_j$ the $j^{th}$ column, but math.kennesaw.edu/~plaval/math3260/specmat.pdf (pg 1) mentions that $Adiag(w)$ is obtained by multiplying each $i^{th}$ row of A (not column) with $w_i$. Just wondering if that was a typo or I am missing something. $\endgroup$
    – Dimpag
    Aug 4, 2015 at 12:49
  • $\begingroup$ @DimitriosPagonakis the document you've referenced is simply wrong. To see this, Try multiplying a random 2 by 3 matrix (say A=[1 2 3; 4 5 6]) times a 3 by 3 diagonal matrix (say D=[1 0 0; 0 2 0; 0 0 3]) and see what happens. This scales the columns of A by the factors on the diagonal of D. $\endgroup$ Aug 4, 2015 at 13:52
  • $\begingroup$ @BrianBorchers you are right, it must have been a typo in their document. Thank you. $\endgroup$
    – Dimpag
    Aug 4, 2015 at 15:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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