The Eckart-Young theorem in the operator norm

Setup. Take a singular value decomposition $A=\sum_{i=1}^n\sigma_iu_iv_i^T$ with orthonormal families $(u_i)$, $(v_i)$.

Upper bound. Let $B_0=\sum_{i=1}^r\sigma_iu_iv_i^T$, which has rank $\le r$. Then $A-B_0=\sum_{i>r}\sigma_iu_iv_i^T$, whose singular values are $\sigma_{r+1},\dots,\sigma_n$ so $\|A-B_0\|=\sigma_{r+1}$.

Lower bound. Let $\operatorname{rank}B\le r$. Then $\dim\ker B\ge n-r$. Let $V=\operatorname{span}(v_1,\dots,v_{r+1})$, of dimension $r+1$. Since $(n-r)+(r+1)=n+1>n$, the subspaces $\ker B$ and $V$ intersect in a nonzero subspace; pick a unit vector $x$ in the intersection. Because $Bx=0$,
$$\|A-B\|\ge|(A-B)x|=|Ax|.$$
Writing $x=\sum_{i\le r+1}c_iv_i$ with $\sum c_i^2=1$, orthonormality of $(u_i)$ gives
$$|Ax|^2=\sum_{i\le r+1}\sigma_i^2c_i^2\ge\sigma_{r+1}^2\sum c_i^2=\sigma_{r+1}^2.$$
Thus $\|A-B\|\ge\sigma_{r+1}$ for every $B$ of rank $\le r$.

Conclusion. The minimum is attained at $B_0$ and equals $\sigma_{r+1}$.

Corollary (distance to singular matrices). For $r=n-1$: the operator-norm distance from an invertible $A$ to the set $\{\det=0\}$ is $\sigma_n(A)=1/\|A^{-1}\|$.

Example. $A=\operatorname{diag}(3,2,1)$, $r=1$: the best rank-one approximation is $\operatorname{diag}(3,0,0)$ at distance $2=\sigma_2$.

Remark. The same truncation $B_0$ is optimal for the Frobenius norm, with error $\sqrt{\sigma_{r+1}^2+\dots+\sigma_n^2}$ (Eckart-Young-Mirsky); the proof is different.