Eckart-Young-Mirsky Theorem

Given an \(M \times N\) matrix \(X\) of rank \(R \le \min\{M,N\}\) and its SVD \(X = U\Sigma V^T\), where \(\Sigma = diag(\sigma_1, \sigma_2, ..., \sigma_R)\), among all the \(M \times N\) matrices of rank \(K \le R\), the best approximation to \(X\) is \(Y^\star = U\Sigma_K V^T\), where \(\Sigma_K = diag(\sigma_1, \sigma_2, ..., \sigma_K)\), when distance between \(X\) and \(Y\) is defined as Frobenius norm: \[ ||X - Y||_F = \sqrt{\sum_{ij}(X - Y)_{ij}^2} \] Firstly we prove that, if \(U\) is orthogonal, then \(||UA||_F = ||AU||_F = ||A||_F\): \[ \begin{aligned} ||UA||_F^2 &= tr((UA)^TUA) \\ &= tr(A^TUUA) \\ &= tr(A^TA) \\ &= ||A||_F^2 \end{aligned} \] The same can be derived for \(||AU||_F\).

For any \(m \times n\) matrix \(Y\) of rank \(K \le R\),

\[ \begin{aligned} ||X - Y||_F^2 &= ||U\Sigma V^T - Y||_F^2 \\ &= ||U^TU\Sigma V^TV - U^TYV||_F^2 \\ &= ||\Sigma - U^TYV||_F^2 \\ \end{aligned} \] Let \(Z = U^TYV\), \(Z\) is also of rank \(K\). \[ \begin{aligned} ||X - Y||_F^2 &= ||\Sigma - Z||_F^2 \\ &= \sum_{ij}(\Sigma_{ij} - Z_{ij})^2 \\ &= \sum_{i=1}^R(\sigma_{i} - Z_{ii})^2 + \sum_{i>R}^{\min\{M,N\}}Z_{ii}^2 + \sum_{i \ne j}Z_{ij}^2 \\ \end{aligned} \] The minimum is achieved if \[ \begin{gather} Z_{ii} = \sigma_{i}, i = 1, 2, \dots, K \\ Z_{ii} = \sigma_{i}, i = K, K + 1, \dots, R - 1 \\ Z_{ii} = 0, i = R, R + 1, \dots, \min\{M,N\} \\ Z_{ij} = 0, i = 1,2, .... M, j=1, 2, \dots, N, i \ne j \end{gather} \] Such \(Z\) exists when \(Y = U\Sigma_KV^T\).

Eckart-Young-Mirsky Theorem also holds for spectral norm .