Approximating a Matrix with Limited Rank
A matrix can encode many directions of variation, but an application may only be able to store or use a simpler matrix. One way to formalize “simpler” is to limit the rank: a matrix of rank at most \(k\) has at most \(k\) independent columns. The difference between the original matrix and a candidate approximation is its residual. To compare candidates, we need a way to measure that residual.
There is more than one reasonable measure of matrix error. The Frobenius norm combines the sizes of all entries, while the operator 2-norm asks how large the residual can make a unit input vector. Singular values give exact formulas for both measures, but the formulas aggregate information differently. In this tutorial, “approximation” means a candidate of limited rank; determining the best candidate for either measure is a separate question.
The rank bound includes matrices of smaller rank, including the zero matrix. The approximation must have the same dimensions as \(\mathbf{A}\), so subtraction is defined. Neither definition specifies how \(\mathbf{B}\) is chosen; different candidates can have different residuals and different errors.
Two Ways to Measure the Residual
For a real matrix \(\mathbf{E}=(e_{ij})\), the Frobenius norm is the square root of the sum of the squares of all its entries. The operator 2-norm is the largest possible Euclidean length of \(\mathbf{E}\mathbf{x}\) when \(\mathbf{x}\) ranges over unit vectors. Equivalently, it is the supremum of the ratio of output length to input length over nonzero inputs.
The Frobenius norm treats all entries through a sum of squares. The operator norm does not sum the effects of separate entries: it measures the largest stretching of any single input direction. These definitions apply to any rectangular matrix, including a residual.
To express both norms through singular values, let \(q=\min(m,n)\). Write the singular values of \(\mathbf{E}\), including zeros as needed, in nonincreasing order as \(\sigma_1,\dots,\sigma_q\). A singular value decomposition writes \(\mathbf{E}=\mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^{\top}\), where \(\mathbf{U}\) and \(\mathbf{V}\) are orthogonal and the diagonal entries of \(\boldsymbol{\Sigma}\) are the singular values, with any required extra zero rows or columns.
Proof. Take a singular value decomposition \(\mathbf{E}=\mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^{\top}\). Multiplication by an orthogonal matrix preserves Euclidean length: if \(\mathbf{Q}^{\top}\mathbf{Q}=\mathbf{I}\), then \(\|\mathbf{Q}\mathbf{y}\|^2=\mathbf{y}^{\top}\mathbf{Q}^{\top}\mathbf{Q}\mathbf{y}=\mathbf{y}^{\top}\mathbf{y}=\|\mathbf{y}\|^2\). Thus, for any \(\mathbf{x}\), \(\|\mathbf{E}\mathbf{x}\|=\|\boldsymbol{\Sigma}\mathbf{V}^{\top}\mathbf{x}\|\), and \(\|\mathbf{V}^{\top}\mathbf{x}\|=\|\mathbf{x}\|\). As \(\mathbf{x}\) ranges over unit vectors, \(\mathbf{y}=\mathbf{V}^{\top}\mathbf{x}\) also ranges over unit vectors. For such a vector, the squared output length is \(\sum_{i=1}^{q}\sigma_i^2 y_i^2\), which is at most \(\sigma_1^2\sum_{i=1}^{q}y_i^2\le\sigma_1^2\). Equality is attained by choosing \(\mathbf{y}=\mathbf{e}_1\), so \(\|\mathbf{E}\|_2=\sigma_1\). For the Frobenius norm, orthogonal changes of coordinates preserve the sum of squared entries: the squared sum of entries is the sum of the squared Euclidean lengths of the columns, and left multiplication by \(\mathbf{U}\) preserves each column length; right multiplication by \(\mathbf{V}^{\top}\) preserves the sum of squared row lengths by the same orthogonality calculation. Therefore \(\|\mathbf{E}\|_F=\|\boldsymbol{\Sigma}\|_F\). The only nonzero entries of \(\boldsymbol{\Sigma}\) are its singular values, so \(\|\boldsymbol{\Sigma}\|_F^2=\sum_{i=1}^{q}\sigma_i^2\). Taking the nonnegative square root proves the Frobenius formula as well. \(\square\)
The formulas explain the distinction. The Frobenius error combines the squared singular values of the residual and then takes a square root. The operator error records only the largest singular value. A residual with several substantial singular values can therefore have a Frobenius error noticeably larger than its operator error.
Proof. The theorem gives \(\|\mathbf{E}\|_2=\sigma_1\) and \(\|\mathbf{E}\|_F=(\sum_{i=1}^{q}\sigma_i^2)^{1/2}\), with \(0\le\sigma_i\le\sigma_1\). Hence \(\sigma_1^2\le\sum_{i=1}^{q}\sigma_i^2\le q\sigma_1^2\). Taking nonnegative square roots yields both inequalities. \(\square\)
Computing Errors from Singular Values
Worked Example: Two Norms of a Residual
Find the Frobenius and operator 2-norms of \(\mathbf{E}=\begin{bmatrix}0&3\\4&0\end{bmatrix}\).
First compute the matrix that determines the singular values:
The eigenvalues of this diagonal matrix are \(16\) and \(9\), so the singular values of \(\mathbf{E}\) are \(4\) and \(3\). Therefore \(\|\mathbf{E}\|_2=4\), while \(\|\mathbf{E}\|_F=\sqrt{4^2+3^2}=5\).
Check: Directly from the entries, \(\|\mathbf{E}\|_F=\sqrt{0^2+3^2+4^2+0^2}=5\). For the operator norm, \(\|\mathbf{E}\mathbf{x}\|^2=16x_1^2+9x_2^2\le16(x_1^2+x_2^2)\), with equality for \(\mathbf{x}=(1,0)^{\top}\), confirming \(\|\mathbf{E}\|_2=4\).
For a rank-constrained approximation, the norms are applied to the residual, not to the candidate itself. The singular values to use are therefore those of \(\mathbf{A}-\mathbf{B}\). The candidate’s rank and the residual’s singular values answer different questions: the rank says how complex the candidate is, while the residual norms quantify its error.
Worked Example: A Rank-One Candidate and Its Residual
Let \(\mathbf{A}=\begin{bmatrix}6&0&0\\0&2&0\\0&0&0\end{bmatrix}\) and \(\mathbf{B}=\begin{bmatrix}6&0&0\\0&0&0\\0&0&0\end{bmatrix}\). Verify that \(\mathbf{B}\) is a rank-at-most-one approximation and compute both errors.
The first column of \(\mathbf{B}\) is nonzero and its other columns are zero, so its column space is spanned by one nonzero vector and \(\operatorname{rank}\mathbf{B}=1\). Subtract entry by entry:
The singular values of this diagonal residual are \(2,0,0\). Thus \(\|\mathbf{A}-\mathbf{B}\|_2=2\) and \(\|\mathbf{A}-\mathbf{B}\|_F=\sqrt{2^2}=2\).
Check: The entry formula gives \(\|\mathbf{E}\|_F=\sqrt{0+0+0+0+4+0+0+0+0}=2\). Also, \(\mathbf{E}\mathbf{x}=(0,2x_2,0)^{\top}\), so \(\|\mathbf{E}\mathbf{x}\|\le2\|\mathbf{x}\|\), with equality for \(\mathbf{x}=(0,1,0)^{\top}\). This confirms the operator norm.
Worked Example: One Residual, Different Error Measures
Consider the rank-at-most-one candidate \(\mathbf{B}=\mathbf{O}\) for \(\mathbf{A}=\begin{bmatrix}0&4\\3&0\end{bmatrix}\). Compute both errors and interpret their difference.
The zero matrix has rank \(0\), so it satisfies the rank bound. Its residual is \(\mathbf{E}=\mathbf{A}-\mathbf{O}=\begin{bmatrix}0&4\\3&0\end{bmatrix}\). Then \(\mathbf{E}^{\top}\mathbf{E}=\begin{bmatrix}9&0\\0&16\end{bmatrix}\), whose eigenvalues are \(16\) and \(9\). The singular values are therefore \(4\) and \(3\). The operator error is \(\|\mathbf{E}\|_2=4\), while the Frobenius error is \(\|\mathbf{E}\|_F=\sqrt{16+9}=5\).
Check: The entries give \(\|\mathbf{E}\|_F=\sqrt{4^2+3^2}=5\). For any \(\mathbf{x}=(x_1,x_2)^{\top}\), \(\|\mathbf{E}\mathbf{x}\|^2=9x_1^2+16x_2^2\le16(x_1^2+x_2^2)\), with equality at \((0,1)^{\top}\). Thus the operator error is indeed \(4\). The Frobenius measure includes both nonzero singular directions; the operator measure reports only the larger one.
What the Measures Do—and Do Not—Tell You
For each fixed rank bound \(k\), the two approximation questions are to make \(\|\mathbf{A}-\mathbf{B}\|_F\) small or to make \(\|\mathbf{A}-\mathbf{B}\|_2\) small, subject to \(\operatorname{rank}\mathbf{B}\le k\). The first objective accounts for residual error across all singular directions. The second limits the largest residual effect on any unit input. A candidate may be evaluated under both measures, but its rank bound alone does not determine either error.
There is also a useful caution in interpreting singular values. The formulas in the theorem apply to the residual \(\mathbf{A}-\mathbf{B}\), and its singular values need not be the singular values of \(\mathbf{A}\) with some entries deleted. That relationship requires a particular way of constructing \(\mathbf{B}\), which is not part of the definitions here. In particular, calculating a candidate’s errors is not by itself a proof that the candidate is optimal.
Common Mistake: Using the Largest Singular Value for Both Norms
A common incorrect calculation is to take the largest singular value as the Frobenius error. For the residual \(\mathbf{E}=\begin{bmatrix}0&4\\3&0\end{bmatrix}\), this gives the wrong claim \(\|\mathbf{E}\|_F=4\), because \(4\) is only the largest singular value. The correction is to use the appropriate formula for each norm: \(\|\mathbf{E}\|_2=4\), but \(\|\mathbf{E}\|_F=\sqrt{4^2+3^2}=5\). Conversely, adding the singular values would also be incorrect: neither definition uses their unsquared sum.
Keep the roles separate: first form the residual, then compute its singular values, then apply the formula for the requested norm. The operator norm is the largest singular value; the Frobenius norm is the square root of the sum of their squares.
Check Your Understanding
For each question, identify whether it concerns the candidate’s rank, the residual, or a norm of the residual.
- State the condition on \(\mathbf{B}\) for it to be a rank-at-most-two approximation to \(\mathbf{A}\in\mathbb{R}^{5\times3}\).
- A residual has singular values \(5,2,0\). Find its Frobenius norm and operator 2-norm.
- For \(\mathbf{E}=\begin{bmatrix}0&0\\0&7\end{bmatrix}\), compute both matrix norms directly and from its singular values.
- Explain why the Frobenius norm combines more information about the residual than the operator 2-norm.
- Does knowing that \(\operatorname{rank}\mathbf{B}\le k\) prove that \(\mathbf{B}\) is a best approximation to \(\mathbf{A}\)? Explain what additional comparison would be needed.
