Singular Value Decomposition, Pseudoinverse, and Low-Rank Approximation

Eigenvalue decomposition mainly concerns square matrices. Singular value decomposition applies to every $m\times n$ matrix and uses separate orthogonal bases in the domain and codomain to describe one linear map.

Every matrix is orthogonal change, scaling, and orthogonal change

For every real matrix $A$, there are orthogonal matrices $U,V$ and a nonnegative diagonal-shaped matrix $\Sigma$ such that

$$A=U\Sigma V^{\mathsf T}.$$

$V^{\mathsf T}$ expresses inputs in the right-singular-vector basis, $\Sigma$ scales perpendicular directions, and $U$ places them in the output space. The positive entries

$$\sigma_1\ge\sigma_2\ge\cdots\ge\sigma_r>0$$

are the singular values. Their count $r$ is $\operatorname{rank}(A)$.

Check dimensions in a rectangular factorization

In the full SVD, $U$ is $m\times m$, $\Sigma$ is $m\times n$, and $V$ is $n\times n$. Keeping only positive modes gives the compact form $A=U_r\Sigma_rV_r^{\mathsf T}$, with $r$ columns on each side. Orthogonal transformations can include reflections, so they are not always rotations.

Singular values come from symmetric matrices

The matrix $A^{\mathsf T}A$ is symmetric positive semidefinite. The spectral theorem gives

$$A^{\mathsf T}A\mathbf v_i=\sigma_i^2\mathbf v_i.$$

For $\sigma_i>0$, define $\mathbf u_i=A\mathbf v_i/\sigma_i$. These vectors are orthonormal and satisfy $A\mathbf v_i=\sigma_i\mathbf u_i$. Completing bases on both sides produces the full SVD.

Eigenvalues may be negative or complex; singular values are always nonnegative real numbers. SVD exists even when a square matrix is not diagonalizable.

Symmetry follows by transposition, and positive semidefiniteness follows from $\mathbf z^{\mathsf T}A^{\mathsf T}A\mathbf z=\|A\mathbf z\|^2\ge0$. For the completed bases, the equations on every $\mathbf v_i$ give $AV=U\Sigma$, so right multiplication by $V^{\mathsf T}$ proves the factorization. The rank is $r$ because multiplication by invertible basis matrices preserves the image dimension and $\Sigma$ has exactly $r$ independent nonzero columns. When $r=0$, $A=0$ and any orthogonal bases work.

Why the constructed left vectors are orthonormal

For positive singular values,

$$\mathbf u_i^{\mathsf T}\mathbf u_j =\frac{\mathbf v_i^{\mathsf T}A^{\mathsf T}A\mathbf v_j}{\sigma_i\sigma_j} =\frac{\sigma_j^2}{\sigma_i\sigma_j}\delta_{ij} =\delta_{ij}.$$

A zero eigenvalue gives $\|A\mathbf v\|^2=0$, hence $A\mathbf v=0$. These two cases complete the construction from the spectral theorem.

SVD aligns the four fundamental subspaces

Right singular vectors with positive singular values span the row space; those with zero singular value span $\ker A$. Positive left singular vectors span the column space; the remaining ones span $\ker A^{\mathsf T}$. Thus

$$\operatorname{row}(A)=(\ker A)^\perp, \qquad \operatorname{col}(A)=(\ker A^{\mathsf T})^\perp.$$

This places the row, column, and null spaces computed in vector spaces and bases into one orthogonal structure.

Proof

Writing $\mathbf x=\sum_i y_i\mathbf v_i$ gives $A\mathbf x=\sum_{i\le r}\sigma_i y_i\mathbf u_i$. Orthogonality makes this zero exactly when $y_1=\cdots=y_r=0$, and it shows that the image is exactly the span of $\mathbf u_1,\ldots,\mathbf u_r$. Apply the same argument to $A^{\mathsf T}=V\Sigma^{\mathsf T}U^{\mathsf T}$ to identify its kernel and image. The row space is the image of $A^{\mathsf T}$, proving both orthogonal-complement identities.

The pseudoinverse unifies exact and least-squares solutions

Invert each positive singular value to form $\Sigma^+$. The Moore–Penrose pseudoinverse is

$$A^+=V\Sigma^+U^{\mathsf T}.$$

The vector $\widehat{\mathbf x}=A^+\mathbf b$ is the minimum-norm least-squares solution. For a consistent system it is the shortest exact solution, and for an invertible matrix it equals $A^{-1}$.

A small singular value amplifies data error by roughly $1/\sigma_i$. Truncating very small singular values sacrifices some fit in exchange for stability.

General proof of the minimum-norm property

For the full SVD $A=U\Sigma V^{\mathsf T}$, put $\mathbf y=V^{\mathsf T}\mathbf x$ and $\mathbf c=U^{\mathsf T}\mathbf b$. Orthogonal transformations preserve norms, giving

$$\|A\mathbf x-\mathbf b\|^2 =\sum_{i=1}^r(\sigma_i y_i-c_i)^2+\sum_{i=r+1}^m c_i^2.$$

The final sum is independent of the input. Each term in the first sum vanishes precisely when $y_i=c_i/\sigma_i$. The remaining $n-r$ input coordinates are free and describe the kernel. Since $\|\mathbf x\|^2=\sum_i y_i^2$, setting every free coordinate to zero gives the unique minimum norm. This is exactly $V\Sigma^+U^{\mathsf T}\mathbf b$.

All solutions of a rectangular example

For the single-row matrix $A=(1\ \ 1)$, a compact SVD is $U_r=(1)$, $\Sigma_r=(\sqrt2)$, and $V_r=(1,1)^{\mathsf T}/\sqrt2$. Thus

$$A^+=\begin{pmatrix}1/2\\1/2\end{pmatrix}.$$

For $b=2$, it returns $(1,1)$. Every exact solution is $(1+t,1-t)$, with squared length $2+2t^2$. The pseudoinverse selects the unique shortest one.

Truncated SVD gives the best low-rank approximation

Write SVD as an outer-product sum:

$$A=\sum_{i=1}^r\sigma_i\mathbf u_i\mathbf v_i^{\mathsf T}.$$

Keeping the first $k$ terms gives $A_k$. The Eckart–Young theorem states that $A_k$ is a closest matrix of rank at most $k$ in the operator or Frobenius norm. The discarded singular values determine the error exactly.

Precise low-rank errors and PCA conventions

The operator two-norm is the largest output norm from a unit input. The Frobenius norm is the square root of the sum of squared entries. For $0\le k<r$,

$$\|A-A_k\|_2=\sigma_{k+1}, \qquad \|A-A_k\|_F^2=\sum_{i>k}\sigma_i^2.$$

For operator-norm optimality, any rank-at-most-$k$ matrix $B$ has a unit null vector $\mathbf z$ in the span of the first $k+1$ right singular vectors. Therefore $\|(A-B)\mathbf z\|=\|A\mathbf z\|\ge\sigma_{k+1}$. Truncation attains this lower bound.

To verify the error formulas, write a unit input in the right singular basis. The squared output under $A-A_k$ is $\sum_{i>k}\sigma_i^2 y_i^2\le\sigma_{k+1}^2$, attained at $\mathbf v_{k+1}$. For the Frobenius norm, orthogonal left multiplication preserves each column length, and orthogonal right multiplication preserves each row length. Thus it preserves the sum of squared entries, reducing the computation to the discarded diagonal entries of $\Sigma$.

Proof of Frobenius-norm low-rank optimality

Let $W$ be the column space of $B$, of dimension at most $k$, and let $P$ be its orthogonal projector. Apply Pythagoras column by column:

$$\|A-B\|_F^2 =\|(I-P)A\|_F^2+\|PA-B\|_F^2 \ge\|A\|_F^2-\|PA\|_F^2.$$

For a full left singular basis, set $\alpha_i=\|P\mathbf u_i\|^2$. Then $0\le\alpha_i\le1$ and $\sum_i\alpha_i=\dim W\le k$: expand $P$ using an orthonormal basis of $W$ and sum over the complete basis. Orthogonality in the outer-product expansion gives

$$\|PA\|_F^2=\sum_{i=1}^r\sigma_i^2\alpha_i \le\sum_{i=1}^k\sigma_i^2.$$

The inequality assigns at most $k$ units of weight to the largest coefficients. Moving weight from a smaller coefficient to an unfilled larger one never decreases the sum. Thus every $B$ has squared error at least $\sum_{i>k}\sigma_i^2$, attained by truncated SVD. For $k\ge r$, taking $B=A$ gives zero error.

PCA also requires a centering decision

Place mean-centered samples in a data matrix. Right singular vectors give principal directions, and squared singular values are proportional to variance along them. The existing expectation and variance chapter supplies the probabilistic language. If feature units differ greatly, one must also decide whether to standardize, since raw scale can dominate the components.

For PCA, explicitly put $N>1$ samples in rows of centered $X\in\mathbb R^{N\times d}$. The sample covariance is

$$C=\frac{X^{\mathsf T}X}{N-1} =V\frac{\Sigma^{\mathsf T}\Sigma}{N-1}V^{\mathsf T}.$$

Principal directions are right singular vectors and their variances are $\sigma_i^2/(N-1)$. Putting samples in columns exchanges the roles of left and right singular vectors.

For a unit feature direction $\mathbf v$, the projected sample column is $X\mathbf v$, with mean zero and sample variance $\|X\mathbf v\|^2/(N-1)=\mathbf v^{\mathsf T}C\mathbf v$. The Rayleigh bound therefore proves maximal variance at the top right singular vector. Restricting to its orthogonal complement and repeating proves the successive principal directions; tied eigenvalues allow any orthonormal basis within the tied eigenspace.

Exercises

ExerciseA rank-one matrix

Explain why $A=\begin{pmatrix}1&2\\2&4\end{pmatrix}$ has exactly one positive singular value.

Solution

The second column is twice the first, so the rank is one. The number of positive singular values equals the rank.

ExercisePseudoinverse of an invertible matrix

Use SVD to show that $A^+=A^{-1}$ when $A$ is invertible.

Solution

All singular values are positive, so $A^+=V\Sigma^{-1}U^{\mathsf T}=(U\Sigma V^{\mathsf T})^{-1}$.

ExerciseError after truncation

If the singular values are $5,2,0.1$, what is the operator-norm error of the best rank-one approximation?

Solution

The error is the first discarded singular value, which is $2$.