Why does the reconstruction error of truncated SVD equal the sum of squared singular values? I saw this formula in a textbook: squared Frobenius norm of the original matrix $\mathbf X$ minus its truncated SVD $\mathbf X_k$ (which can be seen as the approximation error) equals the sum of squared singular values. 

Why is that? How to prove it?
 A: Let $$X = U\Sigma V^\prime$$ be the SVD of the $n\times r$ matrix $X$.  Let $||\quad ||$ be any matrix norm that is left- and right-invariant under orthogonal transformations (reflections and rotations); that is, whenever $P$ is an $n\times n$ orthogonal matrix or $Q$ is an $r\times r$ orthogonal matrix, then
$$||P^\prime X Q|| = ||X||.$$
Then, by the very definition of the SVD, the orthogonality of $U$ and $V$ imply $$||U^\prime (X-A) V||^2 = ||\Sigma - U^\prime A V||^2.$$
Since $A$ is formulated to make $U^\prime A V$ a diagonal matrix that agrees with the first $k$ entries of the diagonal matrix $\Sigma$, the right hand side is just the squared norm of $\Sigma$ after those $k$ diagonal entries have been zeroed out.
For the Frobenius norm (whose square is the sum of squared entries of its argument), the squared norm of this zeroed-out copy of $\Sigma$ is the sum of squares of its remaining entries, precisely 
$$ ||\Sigma - U^\prime A V||^2 = \sum_{j=k+1}^r \delta_j^2.$$
But the Frobenius norm obviously is invariant under left- and right-multiplication by orthogonal matrices, since orthogonality by definition means preservation of the Euclidean norm and the Frobenius norm (when squared) is both (a) the sum of squared Euclidean norms of the rows (and so is invariant under left multiplication, which preserves each row norm) and (b) the sum of squared Euclidean norms of the columns (and so is invariant under right multiplication, which preserves each column norm).
