01 / 20

Singular Value
Decomposition

Learn how any matrix can be broken into three elegant pieces: a rotation, a scaling, and another rotation. SVD is the Swiss Army knife of linear algebra.

Linear Algebra

What is SVD?

Every matrix \( A \) (any size, any entries) can be factored into three special matrices:

\( U \)
Orthogonal matrix of left singular vectors (output directions)
\( \Sigma \)
Diagonal matrix of singular values (scaling factors)
\( V^T \)
Orthogonal matrix of right singular vectors (input directions)

The Geometric Intuition

Any linear transformation \( A \) applied to a unit circle produces an ellipse. SVD decomposes this into three steps:

Unit Circle Input
\( V^T \)
 Rotate Align axes
\( \Sigma \)
 Scale Stretch/shrink
\( U \)
 Rotate Final output

Why Does SVD Matter?

SVD is one of the most widely used tools in applied mathematics, data science, and engineering. It works on every matrix: square or rectangular, real or complex.

Data Compression
Image compression keeps only the largest singular values to approximate the original image
Noise Reduction
Small singular values often represent noise: discarding them cleans up the signal
Recommendations
Netflix, Spotify, and search engines use SVD to discover hidden patterns in data

The SVD Theorem

1
Columns of \( U \): orthonormal eigenvectors of \( AA^T \) (left singular vectors)
2
Columns of \( V \): orthonormal eigenvectors of \( A^T A \) (right singular vectors)
3
Diagonal of \( \Sigma \): square roots of eigenvalues of \( A^T A \), i.e., \( \sigma_i = \sqrt{\lambda_i} \)

Structure of \( \Sigma \)

The singular value matrix \( \Sigma \) is a rectangular diagonal matrix. For an \( m \times n \) matrix with rank \( r \):

\( \sigma_1 \)
\( \sigma_2 \)
\( \vdots \)
 0 (zeros below)
\( \sigma_1 \ge \sigma_2 \ge \dots \ge \sigma_r > 0 \)
 r = rank(A) Dimensions:
\( U \): \( m \times m \)
\( \Sigma \): \( m \times n \)
\( V^T \): \( n \times n \)
 m rows n columns

SVD vs Eigendecomposition

SVD Eigendecomposition
Works on Any matrix (\( m \times n \)) Square matrices only
Always exists? Yes, always Not always
Factored form \( U\Sigma V^T \) \( PDP^{-1} \)
Diagonal entries Singular values (\( \geq 0 \)) Eigenvalues (can be negative/complex)
Factor matrices Orthogonal (\( U^T U = I \)) Not necessarily orthogonal

How to Compute SVD

1
Form \( A^T A \): Compute the \( n \times n \) symmetric matrix \( A^T A \)
2
Find eigenvalues: Solve \( \det(A^T A - \lambda I) = 0 \) for \( \lambda_1 \geq \lambda_2 \geq \cdots \)
3
Singular values: \( \sigma_i = \sqrt{\lambda_i} \). Place them on the diagonal of \( \Sigma \)
4
Build \( V \): Find orthonormal eigenvectors of \( A^T A \) as columns of \( V \)
5
Build \( U \): For each \( i \), compute \( \mathbf{u}_i = \frac{1}{\sigma_i} A \mathbf{v}_i \). Extend to a full orthonormal basis if needed
6
Verify: Check that \( U \Sigma V^T = A \) and that \( U, V \) are orthogonal

Example: \( 2 \times 2 \) Matrix

Step 1: Compute \( A^T A = \begin{pmatrix} 9 & 0 \\ 0 & 1 \end{pmatrix} \)

Step 2: Eigenvalues of \( A^T A \): \( \lambda_1 = 9 \), \( \lambda_2 = 1 \)

Step 3: Singular values: \( \sigma_1 = 3 \), \( \sigma_2 = 1 \)

Example: Non-Diagonal Matrix

1
\( A^T A = \begin{pmatrix} 1 & 1 \\ 1 & 2 \end{pmatrix} \). Eigenvalues: \( \lambda = \frac{3 \pm \sqrt{5}}{2} \)
2
Singular values: \( \sigma_1 = \sqrt{\frac{3+\sqrt{5}}{2}} \approx 1.62 \), \( \sigma_2 = \sqrt{\frac{3-\sqrt{5}}{2}} \approx 0.62 \)
3
\( V \) comes from eigenvectors of \( A^T A \), and \( U \) from \( \mathbf{u}_i = \frac{1}{\sigma_i} A \mathbf{v}_i \)

Example: Rectangular Matrix

Step 1: \( A^T A = \begin{pmatrix} 2 & 0 \\ 0 & 1 \end{pmatrix} \). Eigenvalues: \( \lambda_1 = 2, \lambda_2 = 1 \)

Step 2: Singular values: \( \sigma_1 = \sqrt{2} \approx 1.41 \), \( \sigma_2 = 1 \)

Step 3: \( V = I_2 \), and \( \Sigma \) is \( 3 \times 2 \) with \( \sqrt{2} \) and \( 1 \) on the diagonal, zeros in the third row.

Low-Rank Approximation

The Eckart-Young theorem says: the best rank-\( k \) approximation of \( A \) (in the Frobenius or operator norm) is obtained by keeping only the top \( k \) singular values:

\( \sigma_1 \)
\( \sigma_2 \)
\( \sigma_3 \)
\( \sigma_4 \)
\( \sigma_5 \)
 Keep (rank k=3) Discard Approximation error:
\( \sigma_4^2 + \sigma_5^2 \)
 Energy captured:
\( \sigma_1^2 + \sigma_2^2 + \sigma_3^2 \)

Rank and Singular Values

The singular values encode fundamental information about the matrix:

Rank
The number of nonzero singular values equals the rank of \( A \)
Condition Number
\( \kappa(A) = \frac{\sigma_1}{\sigma_r} \): measures how sensitive the matrix is to perturbation
Null Space
Columns of \( V \) corresponding to zero singular values form a basis for \( \text{null}(A) \)
Column Space
Columns of \( U \) corresponding to nonzero singular values form a basis for \( \text{col}(A) \)

The Pseudoinverse via SVD

If \( A \) is not invertible (or not even square), SVD lets us define the Moore-Penrose pseudoinverse:

where \( \Sigma^+ \) is formed by reciprocating each nonzero singular value and transposing \( \Sigma \):

1
Replace each \( \sigma_i \neq 0 \) with \( 1/\sigma_i \)
2
Leave all zeros as zeros
3
Transpose the result (if \( \Sigma \) is \( m \times n \), then \( \Sigma^+ \) is \( n \times m \))

Common Mistakes

✕ Confusing eigenvalues with singular values
Singular values are always non-negative. Eigenvalues can be negative, zero, or complex. They are related: \( \sigma_i = \sqrt{\lambda_i(A^T A)} \).
✕ Forgetting to order singular values
Singular values must be listed in decreasing order: \( \sigma_1 \geq \sigma_2 \geq \cdots \). The columns of \( U \) and \( V \) must match this ordering.
✕ Wrong dimensions of \( \Sigma \)
\( \Sigma \) has the same dimensions as \( A \) (\( m \times n \)), not \( n \times n \) or \( m \times m \). The "extra" rows or columns are filled with zeros.

SVD At a Glance

Property Detail
Formula \( A = U \Sigma V^T \)
Applies to Any \( m \times n \) matrix
\( U \) comes from Eigenvectors of \( AA^T \)
\( V \) comes from Eigenvectors of \( A^T A \)
\( \sigma_i \) comes from \( \sqrt{\lambda_i(A^T A)} \)
Rank of \( A \) Number of nonzero \( \sigma_i \)
Best rank-\( k \) approx. Keep top \( k \) singular values
Pseudoinverse \( A^+ = V \Sigma^+ U^T \)

Question 1 of 5

In the SVD \( A = U\Sigma V^T \), what are the diagonal entries of \( \Sigma \)?

Question 2 of 5

Which of the following is true about SVD but not about eigendecomposition?

Question 3 of 5

A \( 4 \times 3 \) matrix \( A \) has singular values \( \sigma_1 = 5 \), \( \sigma_2 = 2 \), \( \sigma_3 = 0 \). What is the rank of \( A \)?

Question 4 of 5

To find the best rank-1 approximation of a matrix \( A \) using SVD, you should:

Question 5 of 5

If \( A \) is a \( 3 \times 2 \) matrix, what are the dimensions of \( \Sigma \) in the SVD \( A = U\Sigma V^T \)?