I want to decompose a diagonal matrix $\Lambda \in R^{n \times n}$ such that $$ \Lambda \approx A\Sigma A^T $$ where $\Sigma \in R^{k \times k}$ is a diagonal matrix and $A \in R^{n \times k}$ is a dense matrix (or it is non-diagonal matrix), and $k < n$. Is there any decomposition which can be used to solve the above problem?

Edit: Here the approximation implies that $\|\Lambda - A\Sigma A^T\|_F^2$ should be as low as possible.

  • $\begingroup$ I think it is impossible as we have orthogonal columns... In a slightly circular way of dealing with this we can get the truncated SVD of the matrix $\Lambda \approx U\Sigma V^T$ and that will allow us to select the $\Sigma$ such that it include the maximal absolute values of our $\Lambda$ and $A$ (i.e. $U$) will be just encode the row and the sign of the of the values of $\Sigma$... $\endgroup$ – usεr11852 Nov 14 '18 at 0:11
  • $\begingroup$ @usεr11852 If I do SVD, then I will get diagonal $A$. $\endgroup$ – Dushyant Sahoo Nov 14 '18 at 1:59
  • $\begingroup$ It won't be necessarily diagonal. Just it will have a single non-zero value per row. But, OK, we are just playing with words now. :) $\endgroup$ – usεr11852 Nov 14 '18 at 21:34
  • $\begingroup$ Re the edit: as you surely know, the solution to the less restricted problem of approximating $\Lambda$ as $U\Sigma V^\prime$ is given by the SVD. In this case the SVD yields $\Sigma=\Lambda$ (up to permutation), so all you need to do is remove the smallest $n-k$ singular values, which can be written in the form you require, whence the SVD does the trick. $\endgroup$ – whuber May 19 at 14:39
  • $\begingroup$ @whuber SVD won't give the solution where $A$ is a dense matrix $\endgroup$ – Dushyant Sahoo May 19 at 15:21

For the diagonal matrix $\Lambda$, its rank is the number of non-zero diagonal elements. If $\DeclareMathOperator{\rank}{\text{rank}} \rank(\Lambda)>k$ then equality is impossible since $$ \rank(A\Sigma A^T)\le \min\{ \rank A, \rank\Sigma , \rank A^T \} \le k $$ so $$ \rank\{ A\Sigma A^T \} < \rank \Lambda. $$ But you didn't ask about equality, but used $\approx$ symbol without explaining in what sense there should be approximation. So then the question is unclear, but at least equality is impossible and any approximation would loose rank.

  • $\begingroup$ Yes you are right, there won't be any equality that is why I used approximation. I updated the question to make everything more clear. $\endgroup$ – Dushyant Sahoo May 19 at 8:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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