Unit 1.7 · about 6 h
57 / 324SVD, pseudoinverse and low-rank approximation
SVD describes every real linear map, including rectangular and rank-deficient ones. It unifies lost directions, minimum-norm solutions and the best low-rank representation.
- derive
- implement
You can now
- Construct an SVD from the symmetric eigendecomposition of \(A^\top A\), including its zero-singular-value case.
- Derive the pseudoinverse as the minimum-norm least-squares solution map.
- Prove the spectral-norm Eckart-Young bound and derive PCA as maximum projected variance.
- Implement truncated-SVD reconstruction and check its error against the singular-value tail.
Covers
- Singular-value decomposition and the pseudoinverse
- PCA, low-rank approximation and reconstruction error
Study, in this order
4 steps
- SVD and the pseudoinverseMIT 18.06 - Linear Algebra
Video Lecture 29, Singular value decomposition; Lecture 33, Left and right inverses; pseudoinverse
- Constructing and truncating the SVDMathematics for Machine Learning
Chapter 4, section 4.5 (pp. 119 to 129), especially construction equations (4.71) to (4.79) on pp. 123 to 124; section 4.6, Theorems 4.24 and 4.25 and the proof on pp. 131 to 132
Depth · Follow the construction, not the movie-rating example. Normalize \(Av_i\) only when \(\sigma_i>0\); complete the left basis orthonormally for the remaining directions.
- Best rank-k approximationMIT 18.065 - Applied matrix bridge
Lecture 7, Eckart-Young: The Closest Rank k Matrix to A
Depth · Focus on the rank constraint and the norm in the optimality claim. Leave large-data applications.
- PCA as a variance maximization problemMathematics for Machine Learning
Chapter 10, section 10.2 (pp. 320 to 325), equations (10.9) to (10.25)
Depth · Use the spectral decomposition to bound the Rayleigh quotient; no optimization algorithm is needed. The book stores samples as columns. Transpose its convention for the row-sample NumPy check.
Focus on
- For each positive eigenvalue \(\lambda_i\) of \(A^\top A\) set \(\sigma_i=\sqrt{\lambda_i}\), \(u_i=Av_i/\sigma_i\). Prove \(u_i^\top u_j=\delta_{ij}\). Zero eigenvalues mean \(Av_i=0\), not a vector to normalize.
- For \(A=U_r\Sigma_r V_r^\top\), \(A^+=V_r\Sigma_r^{-1}U_r^\top\). The row-space solution is orthogonal to all null-space additions, hence has minimum Euclidean norm.
- For rank at most \(k\), Eckart-Young gives minimum spectral error \(\sigma_{k+1}\). The truncated SVD also has squared Frobenius error \(\sum_{i>k}\sigma_i^2\). State which norm you measure.
- For centered row-sample \(X\) with \(n>1\), sample covariance is \(X^\top X/(n-1)\). A unit direction's variance is its Rayleigh quotient; right singular vectors maximize it, and retained variance is sum of retained \(\sigma_i^2/(n-1)\).
Reproduce closed-book
float64 A, no random draws, and U,s,Vt=np.linalg.svd(A,full_matrices=False). Implement A1=(U[:,:1]*s[:1])@Vt[:1] and Ap=(Vt.T/s)@U.T. The reconstruction Frobenius norm is 1.2e-15; spectral and Frobenius truncation errors are approximately 3; norm(A@Ap@A-A,'fro') is 2.9e-15. Require identity residuals below 1e-12 and scalar errors within 1e-12 of 3. In the same check use centered float64 X=[[3,0],[-3,0],[0,1],[0,-1]], take its first right singular vector v, and reconstruct (X@v[:,None])@v[None,:]. Verify sample variances (6,2/3) and squared Frobenius reconstruction error 2 within 1e-12. Explain both results from the spectrum, rather than treating this as a fitted ML evaluation.Traps
- Deriving existence from \(A^\top A\) does not recommend forming it to compute an SVD. Its conditioning cost is proved in the next unit.
- Repeated singular values allow rotations within a singular subspace, not just sign flips. Compare reconstructed matrices or subspace projectors.
- A numerical pseudoinverse must declare its singular-value cutoff. Inverting tiny retained values amplifies noise; never divide by zero and then mask the result.
Practice
MML Exercises 4.9, 4.11 and 4.12: a square SVD and two spectral proofs
Chapter 4, Exercises 4.9, 4.11 and 4.12, printed p. 138
Derive both singular-vector families of the 2 by 2 matrix by hand and keep \(Av=\sigma u\) when fixing signs. Prove 4.11 from the SVD construction in this unit and 4.12 from the spectral decomposition of \(A^\top A\); the Eckart-Young proof uses 4.12. The section mini-project should implement a cutoff-aware pseudoinverse and sign-invariant PCA reconstruction on a new matrix, including a zero singular value.
18.06 Problem set 10: the Fibonacci matrix SVD
Problem set 10, Strang 4th ed., section 6.7, Problem 4
Attempt before the official solutions. Keep \(Av=\sigma u\) when matching signs; symmetry does not imply \(U=V\) when an eigenvalue is negative. Skip the neighbouring section 6.7 Problem 11 solution: it incorrectly sets \(U=I\) for orthogonal columns. The normalized columns belong in \(U\), with \(V=I\) before any reordering.
Self-test
-
Why does the SVD construction cover rectangular and rank-deficient matrices?
\(A^\top A\) is real symmetric PSD, so the spectral theorem gives an orthonormal domain basis with nonnegative eigenvalues. For positive values, \(u_i^\top u_j=v_i^\top A^\top Av_j/(\sigma_i\sigma_j)=\delta_{ij}\). For zero values, \(\|Av_i\|^2=0\). Complete the \(r\) output vectors to an orthonormal basis of \(\mathbb{R}^m\); \(m\ge r\) permits this. The identities on every domain basis vector then give \(A=U\Sigma V^\top\). -
What proves the spectral-norm Eckart-Young lower bound?
For \(k<\operatorname{rank}(A)\), any \(B\) of rank at most \(k\) has a kernel of dimension at least \(n-k\). Its intersection with \(\operatorname{span}(v_1,\ldots,v_{k+1})\) is nontrivial since the dimension sum exceeds \(n\). Choose a unit \(z\) there: \(Bz=0\) and \(\|Az\|\ge\sigma_{k+1}\), so \(\|A-B\|_2\ge\sigma_{k+1}\). Orthogonality in the SVD makes the truncated tail attain this bound. For \(k\ge\operatorname{rank}(A)\), choosing \(B=A\) gives zero error. -
Why does \(A^+b\) select the minimum-norm least-squares solution?
In orthonormal output coordinates, minimize each reachable component by setting \(v_i^\top x=(u_i^\top b)/\sigma_i\) for positive \(\sigma_i\). Unreachable output components remain in the residual. The null-space coordinates do not affect the residual, but add their squared norm to \(\|x\|^2\). Setting them to zero uniquely minimizes the norm. -
Why must the unit-length constraint and centering appear in the PCA derivation?
Centering makes \(X^\top X/(n-1)\) the sample covariance rather than an uncentered second moment. For unit \(v=Qz\), \(v^\top Cv=\sum_i\lambda_i z_i^2\le\lambda_{\max}\) since \(\sum_i z_i^2=1\). Equality is attained in a leading eigendirection. Without the length constraint, scaling a nonzero-variance direction makes the objective unbounded.
Completion criterion
Stop when
You construct the wide SVD, derive its pseudoinverse and optimal rank-1 error, give the dimension-intersection proof, and explain the PCA variance and reconstruction checks from the singular spectrum.
Mark passed, then open 1.8 Only mark this when you can do it without notes.Leads to
- 4.3 PCA via SVD: directions, explained variance and sign ambiguity Apply maximum-variance PCA to data; do not repeat its centered 3 by 2 example here.
- 2.1 Least squares: residuals, normal equations and stable solvers Use singular values and the pseudoinverse when coefficient identifiability fails.
- 1.8 Batched shapes, operation costs and conditioning Read amplification and condition numbers from the singular spectrum.
Comes after
- 1.5 Projections, residuals and least squaresRemove the full-column-rank restriction with the pseudoinverse.
- 1.6 Eigenvalues, symmetric and positive-semidefinite matricesApply the spectral theorem to \(A^\top A\) to construct an SVD.
Resources for this unit
- MIT 18.06 - Linear Algebra Follow lectures 1-10, 14-17, 21-22, 25, 27, 29-31 and 33 with matching problems. This is the ordered first pass.
- MIT 18.065 - Applied matrix bridge Use lectures 3-10 after 18.06 for SVD, PCA, low-rank approximation, matrix norms and solver difficulty.
- Mathematics for Machine Learning Use Chapters 2-4 and §10.2 to check notation or re-derive a result. Do not treat it as a second course.
Also in this section
- MIT 6.042J - Proof strand Study textbook Chapters 1 and 3, §§4.1-4.4 and §§5.1-5.4 with matching Unit 1 problems. Leave the rest of the course.
- Introduction to Applied Linear Algebra Sample Chapters 1-13 and the extra exercises for computational practice in fitting, least squares and pseudoinverses.
- Essence of Linear Algebra Open only when a geometric picture is missing; it does not replace derivation or problem solving.
- NumPy broadcasting and matmul shape rules Read General broadcasting rules and Broadcastable arrays, then
matmulNotes for stacked matrices and one-dimensional promotion. These close the pool's array-semantics gap. - Fundamentals of Numerical Computation: conditioning and operation counts Python edition, section 2.8 through Residual and backward error for the fixed-matrix perturbation bound; section 2.5.3 for triangular-solve and LU flop counts. Use Exercise 2.8.7 for a condition-number proof, not the unseeded Hilbert experiment.