Eckart-Young Theorem

• categories: Linear algebra, Theorem

Statement

The Eckart-Young Theorem provides the optimal low-rank approximation of a matrix in terms of the Singular Value Decomposition (SVD). It states:

Let $A\in {\mathbb{R}}^{m\times n}$ with singular value decomposition $A=U\Sigma V^T$, where $\Sigma =\text{diag}({\sigma }_1,{\sigma }_2,\dots ,{\sigma }_r)$ is the diagonal matrix of singular values. For any $k\le r$, the rank-$k$ approximation $A_k$ that minimizes the Frobenius Norm or Spectral Norm of the error satisfies:

$$A_k=\sum _{i=1}^k{\sigma }_i{\mathbf{u}}_i{\mathbf{v}}_i^T,$$

where ${\mathbf{u}}_i$ and ${\mathbf{v}}_i$ are the $i$th left and right singular vectors, respectively.

Equivalently:

$$A_k=U_k{\Sigma }_k{V}_k^T,$$

where $U_k$, ${\Sigma }_k$, and $V_k$ are obtained by truncating $U$, $\Sigma$, and $V$ to their first $k$ components.

Optimality

1. Frobenius Norm:
   The rank-$k$ approximation $A_k$ minimizes the Frobenius norm of the error:

   $$\Vert A-A_k{\Vert }_F=\underset{\text{rank}(B)\le k}{\min }\Vert A-B{\Vert }_F.$$

2. Spectral Norm:
   $A_k$ also minimizes the spectral norm of the error:

   $$\Vert A-A_k{\Vert }_2=\underset{\text{rank}(B)\le k}{\min }\Vert A-B{\Vert }_2.$$