From an SVD to a Low-Rank Approximation
A singular value decomposition separates a matrix into orthogonal directions, each weighted by a singular value. A truncated SVD keeps the directions with the largest singular values and discards the rest. The resulting matrix has low rank, while its error is measured by the singular values of the discarded part. In this tutorial, the goal is to carry out that calculation, compare two standard matrix norms, and verify the predicted errors directly on small examples.
Let \(\mathbf{A}\in\mathbb{R}^{m\times n}\) have rank \(r\). Its compact singular value decomposition is \(\mathbf{A}=\sum_{i=1}^{r}\sigma_i\mathbf{u}_i\mathbf{v}_i^{\top}\), where \(\sigma_1\ge\cdots\ge\sigma_r>0\), the vectors \(\mathbf{u}_i\in\mathbb{R}^m\) are orthonormal, and the vectors \(\mathbf{v}_i\in\mathbb{R}^n\) are orthonormal. Orthonormal means that the dot product of two distinct vectors in each list is zero and each vector has norm \(1\).
Each term \(\sigma_i\mathbf{u}_i\mathbf{v}_i^{\top}\) has rank one. Therefore, retaining \(k\) terms gives a matrix of rank at most \(k\). The choice of the largest singular values is important: the Eckart–Young theorems established in the earlier material on low-rank approximation state that, among matrices of rank at most \(k\), \(\mathbf{A}_k\) minimizes both the Frobenius error and the operator error. The formulas below let us compute those errors without row-reducing the difference matrix.
Proof. If \(k=r\), the truncated sum contains every term of the compact SVD, so \(\mathbf{A}-\mathbf{A}_k=\mathbf{O}\), and both norms are zero. Now suppose \(k<r\), and write \(\mathbf{E}=\mathbf{A}-\mathbf{A}_k=\sum_{i=k+1}^{r}\sigma_i\mathbf{u}_i\mathbf{v}_i^{\top}\). For matrices of the same size, the Frobenius inner product is the sum of the products of corresponding entries. The inner product of \(\mathbf{u}_i\mathbf{v}_i^{\top}\) and \(\mathbf{u}_j\mathbf{v}_j^{\top}\) is \((\mathbf{u}_i\cdot\mathbf{u}_j)(\mathbf{v}_i\cdot\mathbf{v}_j)\). It is \(0\) for \(i\ne j\) and \(1\) for \(i=j\). Thus the squared Frobenius norm of the sum is \(\sum_{i=k+1}^{r}\sigma_i^2\), giving the first formula. For any unit vector \(\mathbf{x}\), orthonormality of the \(\mathbf{u}_i\) gives $$ \|\mathbf{E}\mathbf{x}\|^2 =\sum_{i=k+1}^{r}\sigma_i^2(\mathbf{v}_i\cdot\mathbf{x})^2 \le \sigma_{k+1}^2\sum_{i=k+1}^{r}(\mathbf{v}_i\cdot\mathbf{x})^2 \le \sigma_{k+1}^2. $$ The last inequality holds because the squared coefficients along an orthonormal list sum to at most \(\|\mathbf{x}\|^2=1\). Taking \(\mathbf{x}=\mathbf{v}_{k+1}\) gives \(\|\mathbf{E}\mathbf{v}_{k+1}\|=\sigma_{k+1}\), so the upper bound is attained. The maximum over unit vectors is therefore \(\sigma_{k+1}\). \(\square\)
Worked Rank-One Approximation
Worked Example: A Symmetric \(2\times2\) Matrix
Find the rank-one truncated SVD approximation to \(\mathbf{A}=\begin{bmatrix}4&2\\2&4\end{bmatrix}\), and compute both errors.
Use the orthonormal vectors \(\mathbf{u}_1=\mathbf{v}_1=\frac{1}{\sqrt{2}}(1,1)^{\top}\) and \(\mathbf{u}_2=\mathbf{v}_2=\frac{1}{\sqrt{2}}(1,-1)^{\top}\). Direct multiplication gives \(\mathbf{A}\mathbf{v}_1=(6,6)^{\top}=6\mathbf{u}_1\) and \(\mathbf{A}\mathbf{v}_2=(2,-2)^{\top}=2\mathbf{u}_2\). Thus the singular values are \(6\) and \(2\), and $$ \mathbf{A} =6\mathbf{u}_1\mathbf{v}_1^{\top} +2\mathbf{u}_2\mathbf{v}_2^{\top} =\begin{bmatrix}3&3\\3&3\end{bmatrix} +\begin{bmatrix}1&-1\\-1&1\end{bmatrix} =\begin{bmatrix}4&2\\2&4\end{bmatrix}. $$
Keeping only the first term gives $$ \mathbf{A}_1=6\mathbf{u}_1\mathbf{v}_1^{\top} =\begin{bmatrix}3&3\\3&3\end{bmatrix}. $$ Subtracting from the original matrix, \(\mathbf{A}-\mathbf{A}_1=\begin{bmatrix}1&-1\\-1&1\end{bmatrix}=2\mathbf{u}_2\mathbf{v}_2^{\top}\). The discarded singular value is \(2\), so the theorem predicts Frobenius and operator errors both equal \(2\).
Check: The residual has four entries whose squares sum to \(1+1+1+1=4\), so its Frobenius norm is \(2\). Also, it sends the unit vector \(\mathbf{v}_2\) to \(2\mathbf{u}_2\), while it sends \(\mathbf{v}_1\) to \(\mathbf{0}\). Its operator norm is \(2\), as predicted.
A Rank-Two Approximation and Two Different Errors
Worked Example: Keeping Two Directions in a \(3\times3\) Matrix
For \(\mathbf{A}=\begin{bmatrix}3&-\tfrac{12}{5}&0\\4&\tfrac95&0\\0&0&1\end{bmatrix}\), find the rank-two truncated SVD approximation. Also find the rank-one approximation and compare their errors.
Take \(\mathbf{u}_1=(\tfrac35,\tfrac45,0)^{\top}\), \(\mathbf{u}_2=(-\tfrac45,\tfrac35,0)^{\top}\), \(\mathbf{u}_3=(0,0,1)^{\top}\), and \(\mathbf{v}_1=\mathbf{e}_1\), \(\mathbf{v}_2=\mathbf{e}_2\), \(\mathbf{v}_3=\mathbf{e}_3\). These lists are orthonormal: each vector has squared norm \(1\), and the dot product of each distinct pair in the \(\mathbf{u}\)-list is \(0\). The columns of \(\mathbf{A}\) are \((3,4,0)^{\top}\), \((-\tfrac{12}{5},\tfrac95,0)^{\top}\), and \((0,0,1)^{\top}\), respectively. These are \(5\mathbf{u}_1\), \(3\mathbf{u}_2\), and \(\mathbf{u}_3\). Hence $$ \mathbf{A} =5\mathbf{u}_1\mathbf{v}_1^{\top} +3\mathbf{u}_2\mathbf{v}_2^{\top} +\mathbf{u}_3\mathbf{v}_3^{\top}, \qquad (\sigma_1,\sigma_2,\sigma_3)=(5,3,1). $$
For \(k=2\), retain the first two terms: $$ \mathbf{A}_2 =\begin{bmatrix}3&-\tfrac{12}{5}&0\\4&\tfrac95&0\\0&0&0\end{bmatrix}, \qquad \mathbf{A}-\mathbf{A}_2 =\begin{bmatrix}0&0&0\\0&0&0\\0&0&1\end{bmatrix}. $$ The residual has just one nonzero entry, so its Frobenius and operator norms are both \(1\). These equal the sole discarded singular value, \(\sigma_3=1\).
For \(k=1\), retain only \(5\mathbf{u}_1\mathbf{v}_1^{\top}\): $$ \mathbf{A}_1 =\begin{bmatrix}3&0&0\\4&0&0\\0&0&0\end{bmatrix}, \qquad \mathbf{A}-\mathbf{A}_1 =\begin{bmatrix}0&-\tfrac{12}{5}&0\\0&\tfrac95&0\\0&0&1\end{bmatrix}. $$ The squared Frobenius norm of this residual is \((\tfrac{12}{5})^2+(\tfrac95)^2+1^2=\tfrac{144}{25}+\tfrac{81}{25}+1=10\), so its Frobenius norm is \(\sqrt{10}\). Its singular values are \(3\) and \(1\), so the operator norm is \(3\). Directly, the residual sends \(\mathbf{v}_2\) to \(3\mathbf{u}_2\) and \(\mathbf{v}_3\) to \(\mathbf{u}_3\); the largest stretching factor is \(3\). The formulas give \(\sqrt{3^2+1^2}=\sqrt{10}\) and \(3\), respectively.
Check: Adding \(\mathbf{A}-\mathbf{A}_2\) to \(\mathbf{A}_2\) restores the original third column \((0,0,1)^{\top}\). Adding \(\mathbf{A}-\mathbf{A}_1\) to \(\mathbf{A}_1\) restores the original second and third columns. Both approximations and residuals therefore sum back to \(\mathbf{A}\).
A Rectangular Example
Worked Example: Truncating a \(3\times2\) Matrix
Find the rank-one truncated SVD approximation to \(\mathbf{B}=\begin{bmatrix}3&0\\4&0\\0&3\end{bmatrix}\), and verify its two errors.
The first column is \(5\mathbf{u}_1\) for \(\mathbf{u}_1=(\tfrac35,\tfrac45,0)^{\top}\), while the second column is \(3\mathbf{u}_2\) for \(\mathbf{u}_2=(0,0,1)^{\top}\). These vectors are orthonormal. With \(\mathbf{v}_1=\mathbf{e}_1\) and \(\mathbf{v}_2=\mathbf{e}_2\), the SVD is $$ \mathbf{B}=5\mathbf{u}_1\mathbf{v}_1^{\top} +3\mathbf{u}_2\mathbf{v}_2^{\top}, \qquad (\sigma_1,\sigma_2)=(5,3). $$ Thus the rank-one approximation and its residual are $$ \mathbf{B}_1=\begin{bmatrix}3&0\\4&0\\0&0\end{bmatrix}, \qquad \mathbf{B}-\mathbf{B}_1=\begin{bmatrix}0&0\\0&0\\0&3\end{bmatrix}. $$ The residual has one nonzero entry, \(3\), so both its Frobenius and operator norms are \(3\), matching the discarded singular value. Adding the displayed residual to \(\mathbf{B}_1\) recovers \(\mathbf{B}\) entry by entry.
Common Error: Adding the Discarded Singular Values
For the rank-one approximation in the \(3\times3\) example, the discarded singular values are \(3\) and \(1\). A tempting but incorrect calculation is to say that the Frobenius error is \(3+1=4\). The Frobenius formula squares the discarded singular values, adds the squares, and then takes a square root: the correct error is \(\sqrt{3^2+1^2}=\sqrt{10}\). The operator error is different: it is the largest discarded singular value, which is \(3\), not \(4\) or \(\sqrt{10}\).
This distinction follows from what each norm measures. The Frobenius norm combines the squared contributions of all orthogonal residual directions. The operator norm measures the greatest stretching in a single unit-vector direction, so only the largest remaining singular value determines it. When just one singular value is discarded, as in the \(2\times2\) example, the two errors agree. With several discarded values, they generally do not.
For a practical check, first sort the singular values in nonincreasing order, then retain exactly the first \(k\) terms. Subtract the approximation from the original matrix and verify that the residual matches the discarded terms. Finally, compute the Frobenius error by summing squares and taking a square root, and the operator error by selecting the largest discarded singular value. The Eckart–Young results guarantee that these truncated approximations are optimal among matrices of rank at most \(k\) in the corresponding norm; retaining a different set of directions need not be optimal.
Check Your Understanding
Use the singular values and, where requested, write out the residual to check your calculations.
- A matrix has singular values \(8,5,2\). What are the Frobenius and operator errors of its rank-one truncated SVD approximation?
- For singular values \(6,4,1\), calculate both errors for the rank-two truncated SVD approximation.
- Why is the Frobenius error for the discarded values \(4\) and \(3\) equal to \(5\), rather than \(7\)?
- In the rectangular example, what is the rank-two truncated SVD approximation, and what are its two errors?
- What feature of the singular values determines the operator error after truncation?
