Singular Value Decomposition and Low-Rank Structure

Why Singular Values Matter

A matrix can stretch different directions by different amounts, and those amounts reveal its effective dimension and the structure it preserves. The singular value decomposition (SVD) makes this precise: it expresses any real matrix using orthonormal directions in its domain and codomain, together with nonnegative stretching factors. It is useful both for exact questions, such as finding rank and null spaces, and for approximation questions, such as deciding which directions carry most of a matrix’s size.

The construction begins with a symmetric matrix associated with $A$, namely $A^T A$. This matrix is positive semidefinite, so the spectral theorem supplies an orthonormal eigenbasis. The eigenvalues determine the singular values; the eigenvectors determine the directions on which $A$ acts.

Definition: Let $A$ be a real $m\times n$ matrix and let $p=\min(m,n)$. The singular values of $A$ are the nonnegative numbers $\sigma_1\geq \sigma_2\geq\cdots\geq\sigma_p\geq0$ obtained as the square roots of the largest $p$ eigenvalues of $A^T A$, counting multiplicity. A singular value decomposition is a factorization $$ A=U\Sigma V^T, $$ where $U$ and $V$ are orthogonal matrices of sizes $m\times m$ and $n\times n$, respectively, and $\Sigma$ is an $m\times n$ diagonal rectangular matrix with diagonal entries $\sigma_1,\ldots,\sigma_p$.

Here, orthogonal means $U^TU=UU^T=I_m$ and $V^TV=VV^T=I_n$. The columns $u_i$ of $U$ and $v_j$ of $V$ are called left and right singular vectors. For each positive singular value, the defining action is $Av_i=\sigma_i u_i$. Directions with zero singular value are mapped to zero. In geometric terms, the SVD first resolves a vector into orthonormal right singular directions, scales each component, and expresses the result in orthonormal left singular directions.

Deriving the SVD from the Spectral Theorem

The spectral theorem says that a real symmetric matrix has an orthonormal eigenbasis. Apply it to $A^T A$, which is symmetric and satisfies $x^TA^TAx=\|Ax\|^2\geq0$ for every $x\in\mathbb R^n$. Its eigenvalues are therefore nonnegative. Let $v_1,\ldots,v_n$ be an orthonormal eigenbasis, ordered so that the corresponding eigenvalues $\lambda_i$ decrease. For every positive eigenvalue, define $u_i=Av_i/\sqrt{\lambda_i}$. The next result verifies that these are the required left singular vectors and completes the construction.

Theorem: Every real $m\times n$ matrix $A$ has an SVD. If $r=\operatorname{rank}(A)$, then its positive singular values are precisely $\sqrt{\lambda_1},\ldots,\sqrt{\lambda_r}$, where the positive eigenvalues of $A^TA$ are $\lambda_1\geq\cdots\geq\lambda_r>0$.

Diagonalize $A^TA$.
Choose an orthonormal eigenbasis $v_1,\ldots,v_n$ for $A^TA$, with eigenvalues $\lambda_1\geq\cdots\geq\lambda_n\geq0$.

Build the left vectors for positive eigenvalues.
For $1\leq i\leq r$, set $\sigma_i=\sqrt{\lambda_i}$ and $u_i=Av_i/\sigma_i$. These $u_i$ are orthonormal.

Complete orthonormal bases.
Extend the $u_i$ to an orthonormal basis of $\mathbb R^m$, and use the $v_i$ as an orthonormal basis of $\mathbb R^n$. The resulting matrices give $A=U\Sigma V^T$.

To verify the construction, for $i,j\leq r$,

u_i^Tu_j =\frac{v_i^TA^TAv_j}{\sigma_i\sigma_j} =\frac{\lambda_j v_i^Tv_j}{\sigma_i\sigma_j} =\begin{cases}1,&i=j,\\0,&i\ne j.\end{cases}

Thus the constructed left vectors are orthonormal. If $\lambda_j=0$, then $\|Av_j\|^2=v_j^TA^TAv_j=0$, so $Av_j=0$. For any $x=\sum_{j=1}^n(v_j^Tx)v_j$, it follows that

Ax=\sum_{j=1}^{r}(v_j^Tx)Av_j =\sum_{j=1}^{r}\sigma_j u_jv_j^Tx.

This identity gives $A=U\Sigma V^T$, with zero diagonal entries after the $r$ positive singular values. The number of positive eigenvalues is $r$: indeed, $\ker(A^TA)=\ker(A)$, since $A^TAx=0$ implies $0=x^TA^TAx=\|Ax\|^2$, and $Ax=0$ implies $A^TAx=0$. Rank-nullity then gives $\operatorname{rank}(A)=\operatorname{rank}(A^TA)$. This proves the theorem. $\square$

Worked Example: Constructing an SVD from $A^TA$

Let $A=\begin{pmatrix}1&1\\0&0\end{pmatrix}$. First calculate $A^TA=\begin{pmatrix}1&1\\1&1\end{pmatrix}$. Its eigenvalues are $2$ and $0$, with orthonormal eigenvectors $v_1=(1,1)^T/\sqrt2$ and $v_2=(1,-1)^T/\sqrt2$. Thus the singular values are $\sqrt2$ and $0$.

For the positive singular value, $Av_1=(\sqrt2,0)^T$, so $u_1=Av_1/\sqrt2=(1,0)^T$. Complete this to an orthonormal basis with $u_2=(0,1)^T$. Hence

U=I_2,\qquad \Sigma=\begin{pmatrix}\sqrt2&0\\0&0\end{pmatrix},\qquad V=\frac{1}{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}, \qquad A=U\Sigma V^T.

For a direct check, $\Sigma V^T$ has first row $(1,1)$ and second row $(0,0)$, so it equals $A$. The zero singular direction $v_2$ is in the null space: $Av_2=0$.

Rank, Range, and Null Spaces

Write $r$ for the number of positive singular values. The SVD gives more than a factorization: it describes the fundamental subspaces in terms of its singular vectors. The range of $A$ is the span of its first $r$ left singular vectors, and the null space of $A$ is the span of its right singular vectors with zero singular value. Similarly, the range of $A^T$ is spanned by the first $r$ right singular vectors, while the null space of $A^T$ is spanned by the remaining left singular vectors.

Result: If $A=U\Sigma V^T$ has $r$ positive singular values, then $$ \operatorname{rank}(A)=r,\quad \operatorname{range}(A)=\operatorname{span}(u_1,\ldots,u_r),\quad \operatorname{null}(A)=\operatorname{span}(v_{r+1},\ldots,v_n). $$ Also, $\operatorname{null}(A^T)=\operatorname{span}(u_{r+1},\ldots,u_m)$. A span with no listed vectors means the zero subspace.

For example, if $x=\sum_j c_jv_j$, then $Ax=\sum_{j=1}^r \sigma_jc_ju_j$. The vectors $u_1,\ldots,u_r$ are orthonormal and each $\sigma_j$ is positive, so $Ax=0$ exactly when $c_1=\cdots=c_r=0$. This proves the null-space statement and shows that the range is exactly the span of $u_1,\ldots,u_r$. Applying the same reasoning to $A^T=V\Sigma^TU^T$ yields the statements for $A^T$. In particular, the count of positive singular values equals the rank.

Worked Example: Reading Rank and Null Spaces from Singular Values

Consider $A=\begin{pmatrix}3&0\\0&2\\0&0\end{pmatrix}$, a $3\times2$ matrix. Its columns are already orthogonal, and $A^TA=\operatorname{diag}(9,4)$. Therefore its singular values are $\sigma_1=3$ and $\sigma_2=2$, with right singular vectors $v_1=(1,0)^T$ and $v_2=(0,1)^T$. The corresponding left singular vectors are $u_1=(1,0,0)^T$ and $u_2=(0,1,0)^T$.

Both singular values are positive, so $\operatorname{rank}(A)=2$. The two right singular vectors span all of $\mathbb R^2$, hence $\operatorname{null}(A)=\{0\}$. The left singular vectors span the first two coordinate directions in $\mathbb R^3$, so $\operatorname{range}(A)=\operatorname{span}((1,0,0)^T,(0,1,0)^T)$. The remaining left direction $(0,0,1)^T$ spans $\operatorname{null}(A^T)$.

Truncating the SVD: Best Low-Rank Structure

For $0\leq k\leq p$, the rank-$k$ truncated SVD keeps the first $k$ singular directions and discards the rest: $A_k=\sum_{i=1}^k\sigma_i u_iv_i^T$, where the sum is zero when $k=0$. This has rank at most $k$. To quantify its accuracy, the Frobenius norm is $\|C\|_F=(\sum_{i,j}C_{ij}^2)^{1/2}$, and the spectral norm is $\|C\|_2=\max_{\|x\|=1}\|Cx\|$. The Frobenius norm measures total squared entrywise error; the spectral norm measures the largest stretching of the error matrix.

Theorem (Eckart–Young–Mirsky, in the Frobenius and spectral norms): For any real $m\times n$ matrix $A$ with singular values $\sigma_1\geq\cdots\geq\sigma_p\geq0$, and any $0\leq k\leq p$, the truncated SVD $A_k$ minimizes both norms among matrices $B$ with $\operatorname{rank}(B)\leq k$. The minimum errors are $$ \min_{\operatorname{rank}(B)\leq k}\|A-B\|_F =\left(\sum_{i=k+1}^{p}\sigma_i^2\right)^{1/2}, \qquad \min_{\operatorname{rank}(B)\leq k}\|A-B\|_2 =\sigma_{k+1}, $$ where the spectral-norm minimum is $0$ if $k=p$, and $\sigma_{p+1}$ is taken to be $0$.

Here is a proof for both norms. The cases $k=p$ are immediate because $A$ itself has rank at most $p$. For the Frobenius norm, let $B$ have rank at most $k$, let $L=\operatorname{range}(B)$, and let $P$ be the orthogonal projection onto $L$. Column by column, $A-B$ is the sum of its component in $L$ and its component orthogonal to $L$. Since $(I-P)B=0$, this gives $\|A-B\|_F^2\geq\|(I-P)A\|_F^2$.

For an orthonormal basis $u_1,\ldots,u_m$ of left singular vectors, set $\alpha_i=u_i^TPu_i=\|Pu_i\|^2$. Each $\alpha_i$ lies in $[0,1]$, and $\sum_{i=1}^m\alpha_i=\operatorname{rank}(P)\leq k$. The eigenvalues of $AA^T$ in this basis are $\lambda_i=\sigma_i^2$ for $i\leq p$, with any additional values equal to zero. Therefore

\|PA\|_F^2=\operatorname{tr}(PAA^T)=\sum_{i=1}^m\lambda_i\alpha_i \leq\sum_{i=1}^k\lambda_i.

To check the inequality when $1\leq k<m$, use $\lambda_i\geq\lambda_k$ for $i\leq k$ and $\lambda_i\leq\lambda_k$ for $i>k$: $\sum_{i=1}^k\lambda_i-\sum_{i=1}^m\lambda_i\alpha_i \geq\lambda_k(k-\sum_{i=1}^m\alpha_i)\geq0$. The endpoint cases $k=0$ and $k\geq m$ follow directly from $\operatorname{rank}(P)\leq k$ and the nonnegativity of the $\lambda_i$. Since $\|A\|_F^2=\sum_i\lambda_i$ and the two projected components are orthogonal, it follows that $\|A-B\|_F^2\geq\sum_{i=k+1}^{p}\sigma_i^2$. The truncated SVD attains this bound because $A-A_k=\sum_{i=k+1}^p\sigma_i u_iv_i^T$, whose squared Frobenius norm is $\sum_{i=k+1}^p\sigma_i^2$.

For the spectral norm, suppose $k<p$. On the $(k+1)$-dimensional space $W=\operatorname{span}(v_1,\ldots,v_{k+1})$, the restriction of $B$ has rank at most $k$. Rank-nullity therefore gives a unit vector $x=\sum_{i=1}^{k+1}c_iv_i$ in $W$ with $Bx=0$. Then $\|(A-B)x\|^2=\|Ax\|^2=\sum_{i=1}^{k+1}\sigma_i^2c_i^2\geq\sigma_{k+1}^2$, because $\sum_i c_i^2=1$. Thus every such $B$ has spectral error at least $\sigma_{k+1}$. The error $A-A_k$ has spectral norm $\sigma_{k+1}$: for any unit vector $x$, its squared image norm is at most $\sigma_{k+1}^2$, and equality holds at $x=v_{k+1}$ if $\sigma_{k+1}>0$. If $\sigma_{k+1}=0$, the error is zero. This proves both optimality claims. $\square$

Worked Example: Comparing Rank-One Approximations

Let $A=\operatorname{diag}(4,2,1)$. Its singular values are $4,2,1$, so its best rank-at-most-one approximation is $A_1=\operatorname{diag}(4,0,0)$. The errors are $\|A-A_1\|_F=\sqrt{2^2+1^2}=\sqrt5$ and $\|A-A_1\|_2=2$.

Now compare $B=\operatorname{diag}(0,2,0)$. It has exactly one nonzero diagonal entry, so $\operatorname{rank}(B)=1$, making it a valid rank-one comparison. The difference is $A-B=\operatorname{diag}(4,0,1)$, and hence $\|A-B\|_F=\sqrt{4^2+1^2}=\sqrt{17}$ and $\|A-B\|_2=4$. Both errors exceed those of $A_1$, as the theorem predicts. A matrix with two nonzero diagonal entries would have rank two and would not be a valid rank-one comparison.

Interpretation and Common Pitfalls

A large singular value indicates a direction that the matrix stretches substantially; a small singular value indicates a direction with relatively little contribution to the output. When later singular values are small compared with the first few, the truncated SVD can provide a compact approximation with controlled error. The theorem quantifies that statement: the omitted singular values determine the Frobenius error through their squared sum and the spectral error through the largest omitted value.

Confusing eigenvalues and singular values. Singular values are nonnegative square roots of eigenvalues of $A^TA$, not generally eigenvalues of $A$. For a rectangular matrix, eigenvalues of $A$ may not even be defined.
Forgetting the transpose. The right singular vectors are eigenvectors of $A^TA$; the left singular vectors for positive singular values are obtained from $Av_i/\sigma_i$.
Miscounting rank. Rank is the number of positive singular values, not the number of entries in the matrix or the number of nonzero entries in a particular representation.
Using an invalid approximation in a comparison. To compare against a rank-at-most-$k$ optimum, first check that the proposed matrix really has rank at most $k$.

Key takeaway: The SVD converts a matrix into orthonormal input and output directions plus nonnegative scales. Its positive singular values count rank, its zero singular directions describe null spaces, and keeping the largest $k$ singular values gives a best rank-at-most-$k$ approximation in both Frobenius and spectral norm.

Check Your Understanding

Try these questions using the definitions and results above.

Why must every eigenvalue of $A^TA$ be nonnegative?
If a matrix has singular values $5,2,0,0$, what is its rank, and how many right singular vectors span its null space?
For singular values $6,3,1$, calculate the Frobenius and spectral errors of the rank-one truncated SVD.
Explain why a unit vector in the span of the first $k+1$ right singular vectors can be chosen to satisfy $Bx=0$ whenever $\operatorname{rank}(B)\leq k$.
What rank condition must a proposed comparison matrix satisfy when assessing a best rank-two approximation?

Singular Value Decomposition and Low-Rank Structure

What You'll Learn

Why Singular Values Matter

Deriving the SVD from the Spectral Theorem

Worked Example: Constructing an SVD from \(A^TA\)

Rank, Range, and Null Spaces

Worked Example: Reading Rank and Null Spaces from Singular Values

Truncating the SVD: Best Low-Rank Structure

Worked Example: Comparing Rank-One Approximations

Interpretation and Common Pitfalls

Check Your Understanding

Singular Value Decomposition and Low-Rank Structure

What You'll Learn

Why Singular Values Matter

Deriving the SVD from the Spectral Theorem

Worked Example: Constructing an SVD from \(A^TA\)

Rank, Range, and Null Spaces

Worked Example: Reading Rank and Null Spaces from Singular Values

Truncating the SVD: Best Low-Rank Structure

Worked Example: Comparing Rank-One Approximations

Interpretation and Common Pitfalls

Check Your Understanding

Previous

Next