0
$\begingroup$

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? I have asked the same question here https://stats.stackexchange.com/questions/376822/decomposition-of-a-diagonal-matrix

Edit: The number of zero elements in each row and column of $A$ matrix should not be greater than half the size of the row and column respectively.

$\endgroup$
1
$\begingroup$

For simplicity of explanation, suppose that $$ \Lambda = \pmatrix{\lambda_1 \\ & \lambda_2 \\ && \ddots \\ &&& \lambda_n} $$ with $|\lambda_1| \geq |\lambda_2| \geq \cdots \geq |\lambda_n|$. The Eckart-Young theorem tells us that the best rank-$k$ approximation (or at least one of the best rank-$k$ approximations) of $\Lambda$ (relative to the Frobenius norm or induced $2$-norm) will be the diagonal matrix $$ \Lambda^{(k)} = \pmatrix{\lambda_1 \\ & \ddots \\ && \lambda_k \\&&&0\\&&&&\ddots\\ &&&&&0} $$ We can write $\Lambda^{(k)} = M DM^T$, where $$ M = \pmatrix{\sqrt{|\lambda_1|}\\ & \ddots \\ && \sqrt{|\lambda_k|}\\&\mathbf 0_{(n-k)\times k}} $$ and $D$ is a $k\times k$ diagonal matrix with $\pm 1$ on the diagonal. If $U$ is an orthogonal matrix that satisfies $UD = DU$, then we have $$ (MU)D(MU)^T = MUDU^TM^T = MDUU^TM = MDM^T = \Lambda^{(k)} $$ I suspect that selecting a dense orthogonal matrix satisfying $UD = DU$ will give you a good result.


Regarding orthogonal matrices that commute with $D$: if $D$ is such that the $1$s and $-1$s are grouped together, then we have $$ D = \pmatrix{I_{p \times p} \\ & - I_{(n-p)\times (n-p)}} $$ An orthogonal matrix $U$ will satisfy $UD = DU$ if and only if it is conformably block-diagonal, i.e. if and only if we have $$ U = \pmatrix{U_{p \times p}^{(1)} & 0\\ 0 & U_{(n-p) \times (n-p)}^{(2)}} $$ and notably, the above $U$ will be orthogonal if and only if both $U^{(1)}$ and $U^{(2)}$ are orthogonal.

$\endgroup$
  • $\begingroup$ Thanks for the answer, but the $MU$ matrix has $n-k$ columns and rows completely 0 equal to zero. I want the matrix to be dense, and also it is not necessary to have minimum Frobenius norm. The main condition is that $A\Sigma A^T$ should be closed to diagonal matrix and $A$ is dense. $\endgroup$ – Dushyant Sahoo Nov 15 '18 at 6:43

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.