Linear Algebra
9.78 min read

Computing SVD via Covariance Matrix

The algorithm for SVD via K=AA⊤K = AA^\top: (1) form K=AA⊤K = AA^\top; (2) eigendecompose K=UΛKU⊤K = U\Lambda_K U^\top; (3) set σi=(ΛK)ii\sigma_i = \sqrt{(\Lambda_K)_{ii}}; (4) compute vi=1σiA⊤ui\mathbf{v}_i = \frac{1}{\sigma_i}A^\top \mathbf{u}_i for each nonzero σi\sigma_i; (5) extend to orthonormal basis for zero σi\sigma_i.

This approach is preferred when m<nm < n (the covariance matrix is smaller than the Gram matrix). The result is the same full SVD regardless of which path is taken.

Formal View

Example 9.1 — SVD via Covariance — Algorithm
Given AA (m×nm \times n), compute SVD via K=AA⊤K = AA^\top: 1. Form K=AA⊤K = AA^\top (m×mm \times m). 2. Eigendecompose: K=UΛKU⊤K = U\Lambda_K U^\top, sort λi\lambda_i descending. 3. σi=λi\sigma_i = \sqrt{\lambda_i}; form m×nm \times n matrix Σ\Sigma. 4. vi=1σiA⊤ui\mathbf{v}_i = \frac{1}{\sigma_i}A^\top \mathbf{u}_i for σi>0\sigma_i > 0; extend for zero σi\sigma_i. 5. Verify: A=UΣV⊤A = U\Sigma V^\top.

Interactive Visualization

Matrix Product — Column Perspective

Why This Matters

Knowing how to compute SVD from either AA⊤AA^\top or A⊤AA^\top A allows choosing the smaller matrix to reduce computational cost.

  • Word embeddings: tall matrices (many words, few documents) use covariance path.
  • Scientific computing: 10000×10010000 \times 100 matrices use the 100×100100 \times 100 Gram path.
  • MATLAB's `svd(A)` internally uses an optimized algorithm.

Quiz

Question 1

For a 100×10000100 \times 10000 matrix AA, which is more efficient?

Question 2

Both the covariance-path and Gram-path algorithms produce the same SVD.

Common Mistakes

  • Computing AA⊤AA^\top when you want the Gram matrix — Gram is A⊤AA^\top A, covariance is AA⊤AA^\top.
  • Not verifying A=UΣV⊤A = U\Sigma V^\top at the end.