Let $A\in\mathbb{C}^{m\times n}$ be a complex matrix. Let $B_k$ be a best rank-$k$ approximation to $A$ such that \begin{equation*} B_k\in\arg\min\limits_{{\rm rank}(B)=k}||A-B||_F, \end{equation*} where $||\cdot||_F$ denotes the Frobenius norm. Then, I guess $k$ largest singular values of $B_k$ is identical with the $k$ largest singular values of $A$ and other singular values of $B_k$ are all zero. Is my conjecture correct? Can anyone help me prove this?

  • $\begingroup$ By pre- and post- multiplication by unitary matrices, you may as well assume $A$ is diagonal. Then any besta pproximation to $\|A-B_k\|$ will be by diagonal $B_k$, and so on. $\endgroup$ – kimchi lover May 11 '19 at 7:46
  • $\begingroup$ why the best rank-k approximation to diagonal matrix should be also diagonal? $\endgroup$ – Lin Xuelei May 11 '19 at 9:52
  • $\begingroup$ The map that replaces off-diagonal entries with zero is an orthogonal projection onto the set of diagonal matrices. So you are left with a combinatorial problem, of selecting which $k$ diagonal elements to preserve and which others to set to 0. $\endgroup$ – kimchi lover May 11 '19 at 13:31
  • $\begingroup$ the feasible set is $\{B|{\rm rank(B)}=k\}$. A rank-$k$ matrix may have more than $k $ nonzero diagonal entries. So, what's the usage of the orthogonal projection here. could you provide more details? $\endgroup$ – Lin Xuelei May 11 '19 at 16:04

Your Answer

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

Browse other questions tagged or ask your own question.