9.88 min read

Computing SVD via Gram Matrix

Alternatively: (1) form $G = A^\top A$ ; (2) eigendecompose $G = V\Lambda_G V^\top$ ; (3) set $\sigma_i = \sqrt{(\Lambda_G)_{ii}}$ ; (4) compute $\mathbf{u}_i = \frac{1}{\sigma_i} A\mathbf{v}_i$ for nonzero $\sigma_i$ ; (5) extend for zero $\sigma_i$ .

This path is preferred when $n < m$ (the Gram is smaller). Both paths give the same SVD. MATLAB: [U, S, V] = svd(A) chooses the optimal algorithm internally.

Formal View

Example 9.2 — SVD via Gram — Algorithm

Given

A

(

m \times n

), compute SVD via

G = A^\top A

: 1. Form

G = A^\top A

(

n \times n

). 2. Eigendecompose:

G = V\Lambda_G V^\top

, sort descending. 3.

\sigma_i = \sqrt{\lambda_i}

; form

\Sigma

. 4.

\mathbf{u}_i = \frac{1}{\sigma_i}A\mathbf{v}_i

for

\sigma_i > 0

. 5. Verify:

A = U\Sigma V^\top

Interactive Visualization

Matrix Product — Column Perspective

Why This Matters

Choose Gram vs covariance path based on which gives the smaller matrix to decompose.

Wide data matrices (many features, few samples): Gram path is small.
Tall data matrices (many samples, few features): covariance path is small.
Square matrices: both paths equally sized; use bidiagonalization instead.

Learning Resources

SVD via Gram matrix

MIT OpenCourseWare

Computing SVD using $A^\top A$ eigendecomposition.

45 min

SVD in practice

Steve Brunton

Choosing between Gram and covariance paths for SVD computation.

20 min

Quiz

Question 1

Given $V$ from the spectral decomposition of $A^\top A$ , we compute $\mathbf{u}_i = \frac{1}{\sigma_i} A \mathbf{v}_i$ .

Question 2

For a $10000 \times 50$ matrix, which path is more efficient?

Common Mistakes

Computing $\mathbf{u}_i = A\mathbf{v}_i$ without dividing by $\sigma_i$ — the result is not a unit vector.
Using the Gram path when the covariance path gives a much smaller matrix.