The Eckart-Young Theorem

Definition Let $\mathbb{F}$ be $\mathbb{R}$ or $\mathbb{C}$, let $E \in \mathbb{F}^{m \times n}$, and give both $\mathbb{F}^n$ and $\mathbb{F}^m$ the Euclidean norm $\lVert x \rVert = \sqrt{x^{*}x}$. The spectral norm, or operator $2$-norm, of $E$ is

The maximum exists because the unit sphere of $\mathbb{F}^n$ is closed and bounded and $x \mapsto \lVert Ex \rVert$ is continuous. It gives $\lVert Ex \rVert \le \lVert E \rVert_2 \lVert x \rVert$ for every $x$. For unitary matrices $Q \in \mathbb{F}^{m \times m}$ and $W \in \mathbb{F}^{n \times n}$ (orthogonal when $\mathbb{F} = \mathbb{R}$),

because $Q$ keeps the length of every output and $x \mapsto Wx$ maps the unit sphere onto itself. With a singular value decomposition $E = U\Sigma V^{*}$ this gives $\lVert E \rVert_2 = \lVert \Sigma \rVert_2 = \sigma_1$, the largest singular value. Indeed, for a unit vector $y$ the output $\Sigma y$ has squared length $\sum_i \sigma_i^2 \lvert y_i \rvert^2 \le \sigma_1^2$, with equality at $y = e_1$. When $E$ is an approximation error $A - B$, its spectral norm is the error in the worst input direction.

Definition The Frobenius norm of $E \in \mathbb{F}^{m \times n}$ is the nonnegative number $\lVert E \rVert_F$ with

It is also unchanged by unitary factors, $\lVert QEW \rVert_F = \lVert E \rVert_F$ for unitary $Q$ and $W$ of sizes $m$ and $n$. Multiplying on the left by $Q$ keeps the length of every column, and multiplying on the right by $W$ keeps the length of every row. With a singular value decomposition this gives $\lVert E \rVert_F^2 = \sigma_1^2 + \cdots + \sigma_p^2$, where $p = \min(m, n)$. Taking $W$ with orthonormal columns $w_1, \dots, w_n$ shows that

for every orthonormal basis of $\mathbb{F}^n$, since the vectors $Ew_j$ are the columns of $EW$. The two norms compare as $\lVert E \rVert_2 \le \lVert E \rVert_F \le \sqrt{\operatorname{rank} E}\,\lVert E \rVert_2$, because at most $\operatorname{rank} E$ singular values are nonzero and none exceeds $\sigma_1$.

Definition Let $A \in \mathbb{F}^{m \times n}$ have a full singular value decomposition $A = U\Sigma V^{*}$, with unitary $U$ and $V$, columns $u_1, \dots, u_m$ and $v_1, \dots, v_n$, and singular values $\sigma_1 \ge \cdots \ge \sigma_p \ge 0$, where $p = \min(m, n)$, so that $Av_i = \sigma_i u_i$ for $i \le p$. For $0 \le k \le p$, the truncated SVD of $A$ at rank $k$ is

with $A_0 = 0$. In matrix form $A_k = U_k \Sigma_k V_k^{*}$, where $U_k$ and $V_k$ keep the first $k$ columns of $U$ and $V$ and $\Sigma_k = \operatorname{diag}(\sigma_1, \dots, \sigma_k)$. Equivalently $A_k = U_k U_k^{*} A$, which projects every column of $A$ orthogonally onto the span of $u_1, \dots, u_k$. Its rank is $\min(k, \operatorname{rank} A)$, so at most $k$. The discarded part is

which equals $U \Sigma' V^{*}$ where $\Sigma'$ keeps only the diagonal entries $\sigma_{k+1}, \dots, \sigma_p$. By unitary invariance, for $k < p$,

The matrix $A_k$ is built from one chosen decomposition. When $\sigma_k > \sigma_{k+1}$, or when $k \ge \operatorname{rank} A$, every singular value decomposition of $A$ gives the same $A_k$. A tie $\sigma_k = \sigma_{k+1} > 0$ is the case where the choice matters.

Definition Let $A \in \mathbb{F}^{m \times n}$, let $k \ge 0$ be an integer, and fix a norm on $\mathbb{F}^{m \times n}$, here the spectral or the Frobenius norm. A best approximation of $A$ of rank at most $k$ is a matrix $B_{\star} \in \mathbb{F}^{m \times n}$ with $\operatorname{rank} B_{\star} \le k$ and

for every $B \in \mathbb{F}^{m \times n}$ with $\operatorname{rank} B \le k$. The constraint is rank at most $k$, not exactly $k$, so competitors of smaller rank count. For $1 \le k < \min(m, n)$ the competitors do not form a subspace, so the projection theorem for subspaces does not apply. With $k = 1$, for instance, $\operatorname{diag}(1, 0) + \operatorname{diag}(0, 1) = I_2$ has rank $2$ while both summands have rank $1$. Two cases are settled at once. If $k = 0$, the only competitor is the zero matrix and the error is $\lVert A \rVert$. If $k \ge \operatorname{rank} A$, then $B = A$ is admissible with error $0$, and it is the only best approximation, because a zero error forces $B = A$. The real question is the range $1 \le k < \operatorname{rank} A$.

Definition Let $A \in \mathbb{F}^{m \times n}$, where $\mathbb{F}$ is $\mathbb{R}$ or $\mathbb{C}$, with a full singular value decomposition in the notation above, and let $0 \le k < p = \min(m, n)$. Then every $B \in \mathbb{F}^{m \times n}$ with $\operatorname{rank} B \le k$ satisfies

and the truncated SVD $A_k$ attains both bounds. So $A_k$ is a best approximation of rank at most $k$ in both norms, with minimum errors $\sigma_{k+1}$ and $(\sigma_{k+1}^2 + \cdots + \sigma_p^2)^{1/2}$. For $k \ge p$ the matrix $A$ itself is admissible.

For the spectral bound, rank-nullity gives $\dim \ker B \ge n - k$, and the span of $v_1, \dots, v_{k+1}$ has dimension $k + 1$. The two dimensions add to more than $n$, so the subspaces share a unit vector $x = c_1v_1 + \cdots + c_{k+1}v_{k+1}$, where $\lvert c_1 \rvert^2 + \cdots + \lvert c_{k+1} \rvert^2 = 1$. Since $Bx = 0$ and $Ax = \sum_i c_i \sigma_i u_i$ with orthonormal $u_i$,

For the Frobenius bound, let $P$ be the orthogonal projector onto the column space of $B$, of rank $d = \operatorname{rank} B \le k$. Since $PB = B$, the error splits as $(I - P)A + (PA - B)$, and the columns of the two parts lie in perpendicular subspaces. Hence

Set $w_i = \lVert Pu_i \rVert^2$ for $i = 1, \dots, m$, and $\sigma_i = 0$ for $p < i \le m$. Each $w_i$ lies between $0$ and $1$, and $\sum_i w_i = \sum_i u_i^{*}Pu_i = \operatorname{tr}(U^{*}PU) = \operatorname{tr} P = d$. Since $PA = PU\Sigma V^{*}$, unitary invariance gives $\lVert PA \rVert_F^2 = \sum_i \sigma_i^2 w_i$, the energy captured by $P$. For $k \ge 1$ let $h = \sum_{i \le k} (1 - w_i) \ge 0$ be the weight missing from the first $k$ positions. Then $\sum_{i > k} w_i = d - k + h \le h$. Using $\sigma_i \ge \sigma_k$ for $i \le k$ and $\sigma_i \le \sigma_{k+1}$ for $i > k$,

Subtracting from $\lVert A \rVert_F^2 = \sigma_1^2 + \cdots + \sigma_p^2$ gives the bound. For $k = 0$ the only competitor is $B = 0$, and the bound holds with equality. Neither argument assumes that $B$ shares singular vectors with $A$, so the theorem compares $A_k$ with every admissible matrix.

Definition Keep the notation of the theorem and let $1 \le k < \operatorname{rank} A$, so that $\sigma_k > 0$. In the Frobenius norm the answer depends on the gap at the cut.

• If $\sigma_k > \sigma_{k+1}$, then $A_k$ is the only best approximation of rank at most $k$. For an optimal $B$, the inequalities in the proof above must all be equalities. This forces $PA = B$ and $(\sigma_k^2 - \sigma_{k+1}^2)h = 0$, so $h = 0$ and every $w_i$ with $i \le k$ equals $1$. Then $u_1, \dots, u_k$ lie in the image of $P$, which has dimension at most $k$, so $P = U_kU_k^{*}$ and $B = PA = A_k$.
• If $\sigma_k = \sigma_{k+1}$, the best approximation is not unique. Swapping the pairs $(u_k, v_k)$ and $(u_{k+1}, v_{k+1})$ gives another singular value decomposition of $A$, whose truncation differs from $A_k$ by $\sigma_k(u_{k+1}v_{k+1}^{*} - u_kv_k^{*}) \ne 0$ and has the same error. Rotating the two pairs together by any angle gives infinitely many more.

In the spectral norm the best approximation is never unique in this range, even with a strict gap. The bound only controls the worst direction, so a competitor may change the retained part as long as that does not make the worst direction worse. For instance, lowering $\sigma_1$ to $\sigma_1 - \sigma_{k+1}$ in $A_k$ gives a different matrix of rank at most $k$, whose error $\sigma_{k+1}u_1v_1^{*} + (A - A_k)$ still has largest singular value $\sigma_{k+1}$. The theorem therefore guarantees the minimum error and one matrix that attains it, and any claim of uniqueness must name its norm and its hypothesis on the singular values.