3
$\begingroup$

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?

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

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.

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

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.