Singular Value Decomposition: A Geometric Rediscovery, Where Proofs Become Algorithms

The gist: The singular value decomposition provides a geometric foundation for principal component analysis, kernel methods, and PageRank by revealing that the construction leading to it is an algorithm rather than just a result.

Discovering the decomposition

The process begins by observing how a linear map transforms the unit circle into an ellipse Fix a matrix A ∈ Rm×n and think of it as a map Rn → Rm Feed it the unit circle — all input vectors of length one — and look at where they land An ellipse has two distinguished directions: its axes, the long one and the short one, perpendicular to each other It is natural to ask what input directions A sent to them The examples show that the axes are perpendicular — of course they are, they are the axes of an ellipse The striking column is the last one: their preimages are perpendicular too.

Why the perpendicular pair must exist

The existence of a perpendicular pair whose images are also perpendicular is proven by rotating a frame and measuring the inner product of its images, denoted as f(θ) The claim is that every matrix preserves at least one right angle. This existence is guaranteed by the intermediate value theorem because f is continuous and f(θ + 90◦) = -f(θ). The analysis of f(θ) shows that it oscillates about zero with a pure sinusoid in 2θ, which must cross zero exactly twice over a half-turn. This crossing corresponds to the frame whose images are perpendicular and lands on the ellipse’s axes.

From two dimensions to n

The planar success is generalized to three dimensions by showing that for a generic orthonormal triple, the axis-preimages form an orthonormal triple. The construction runs by induction, and each step is the hinge applied once. The recursion continues until an orthonormal basis v1,..., vn is produced, and its images are pairwise orthogonal. This process leads to the conclusion that the maximizer's image is orthogonal to the image of the entire hyperplane v⊥1.

The same fact, algebraically

The variational route proves that at a maximizer, ⟨Av1, Aw⟩ = 0 for every w ⊥ v1. This leads to the conclusion that the vector AT Av1 is orthogonal to every w in the hyperplane v⊥1. This implies that A T A v1 = λi v1 for some scalar λi, meaning the maximizer is an eigenvector of A T A with eigenvalue σ2i. This establishes the spectral theorem for AT A by showing that the variational route has already proved it.

The same fact, algebraically

The symmetry hypothesis is used exactly once to show that eigenvectors of a symmetric matrix are perpendicular when their eigenvalues are distinct. This property is applied to the Gram matrix A T A, which is symmetric because (A T A) T = A T. The images of the eigenvectors of AT Avj are orthogonal automatically because ⟨Avi, Avj⟩ = 0 for i ≠ j. This computation shows that the eigenvectors of AT A are the frame central to the entire note.

The same fact, algebraically

The singular values are real because A T A is positive semidefinite, meaning x T(A T A)x = Ax2 ≥ 0. When x is an eigenvector vi, this equals λi = Avi2, so σi:= √λi is a well-defined nonnegative real number. This step confirms that the spectral theorem applies to A T A and supplies non-negative real numbers for the singular values.

The same fact, algebraically

The SVD is revealed as a factorization of a linear map into three motions: rotation, axis-aligned scaling, and another rotation. The decomposition A = UΣV T shows how the map acts by rotating the input to align with the right singular vectors V, stretching them by σi via Σ, and then rotating them into the output frame U.

Four ways to say the same thing

The right singular vectors admit several characterizations, all equivalent: Geometric, Metric, Variational, and Algebraic. The geometric description is the orthonormal input frame whose images stay orthogonal. The metric description is the frame that lands on the principal axes of the image ellipsoid with semi-axis lengths σi.

The polar decomposition

Every matrix is a stretch followed by a rotation, expressed as A = QP where Q = UVT is orthogonal and P = VΣV T is symmetric positive semidefinite. P deforms the input along the right singular directions, and Q then swings the result over to the output frame.

Where it leads: principal component analysis

The matrix (p × p) matrix 1/n-1 A T A is exactly the sample covariance matrix of the features. Its eigenvectors are the right singular vectors of A, which are the principal components, and its eigenvalues give the variances outright as σ2i n-1. The ellipsoid this article has drawn since §1 is, for a data matrix, the shape of the data cloud itself.

Kernel methods: the two Gram matrices

The duality between A T A and AAT is the engine of the kernel trick. Kernel PCA runs the proof of this duality, finding eigenvectors of the small matrix K = ΦΦ T instead of the giant feature space matrix d × d.

Gradient descent and the power method

The eigenvector equation A T A v1 = σ21 v1 is the stopping condition of gradient ascent. This means that an optimizer descending this landscape is re-running the maximality lemma, as its every step of not being able to improve corresponds to a step of the proof.

Low-rank approximation: keeping the largest σi

The Eckart–Young theorem states that truncating the decomposition by keeping k largest singular values yields the best rank-k approximation of A in either norm. This is the mathematical core of image compression, noise filtering, and latent semantic analysis.

Eigenvectors of a graph: PageRank and spectral clustering

PageRank ranks web pages by importance by finding the dominant eigenvector of a column-stochastic matrix P. Spectral clustering uses the eigenvector of the Laplacian L with the second-smallest eigenvalue to partition data into well-separated pieces.

A pattern in what recurred

The maximize-then-recurse construction reappeared as the power method and as PageRank. The lemma that the maximizer’s gradient vanishes tangentially reappeared as an optimizer’s stopping rule. The proof that two Gram matrices are two ends of one map reappeared as the transport at the center of kernel PCA.

Summary

The SVD is completely described by which orthonormal input frame goes to which orthonormal output frame, and by how much each direction stretches.

1. Properly implement principal component analysis (PCA) using singular vectors to find the orthogonal directions of greatest variance in the data, which is precisely what the greedy description of the frame from §2.4 provides for data matrices, ensuring the resulting principal components are derived from a provably maximal stretch.

2. Design an iterative optimization algorithm for finding principal components by using the maximize-and-recurse construction, where the stopping rule is defined by the lemma that the maximizer’s gradient vanishes tangentially, directly translating this into a robust convergence criterion for gradient ascent methods on non-convex loss landscapes.

3. Develop a kernel method engine that leverages the duality between Gram matrices, executing the transport at the heart of kernel PCA by finding eigenvectors of the small matrix and applying them through the lifted feature space map to recover high-dimensional principal components without ever forming the infinite-dimensional feature vectors directly.

4. Implement low-rank approximation for large datasets by using the Eckart–Young theorem, ensuring that truncation results in the best rank-k approximation of A there is under the spectral or Frobenius norm, providing provably optimal noise filtering and latent semantic analysis results.

5. Enhance PageRank algorithms by replacing iterative matrix multiplication with the recursive procedure derived from Part I, where the maximize-and-recurse construction runs as an algorithm to compute the dominant eigenvector of a column-stochastic matrix P.