# Is the low-rank approximation of a matrix unique?

Let $A \in \mathbb{R}^{m \times n}$ be a matrix with $\text{rank}(A)=\min(m,n)$. The Eckart–Young–Mirsky theorem for the Frobenius norm states that the best approximation of rank $k<\min(m,n)$ for $A$, denoted $A_k$, is:

$$\arg \min_{A_k} \left\Vert A - A_k \right\Vert_F^2 = \sum_{i=1}^k \sigma_i u_i v_i^T$$

where

$$A= \overset{\max(m,n)}{\underset{i=1}{\sum}} \sigma_i u_i v_i^T$$

is the singular value decomposition of $A$ (The singular vectors $u_i$ and $v_i$ are normalized and their corresponding singular values $\sigma_i$ are sorted in descending order).

Is this solution the unique global minimizer?

• Are you accounting for the fact that singular vectors do not necessarily have uniquely determined signs? – J. M. is a poor mathematician Mar 7 '18 at 9:53
• @J.M.isnotamathematician I mean uniqueness up to the signs (and norms, and permutations) of the singular vectors. – elliotp Mar 7 '18 at 9:59

The minimizer might not be unique. Consider the case where $k=1$ and the eigenvectors corresponding to the largest singular value are not unique. A simple example of that is a rank one approximation of identity matrix.

• Is it unique if all the singular values are distinct? – elliotp Mar 7 '18 at 17:56
• yes, in that case, it would be unique. – Maziar Sanjabi Mar 8 '18 at 6:46