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?

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

1 Answer 1

Reset to default
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.

Improve this answer
$\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
    Commented 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$
    – Brian Borchers
    Commented 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
    Commented 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$
    – Brian Borchers
    Commented Aug 4, 2015 at 13:52
  • $\begingroup$ @BrianBorchers you are right, it must have been a typo in their document. Thank you. $\endgroup$
    – Dimpag
    Commented Aug 4, 2015 at 15:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .