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

Paul Agron

cs.LGOct 6, 2026

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

Authors: Paul Agron

Abstract

This article is a geometric rediscovery of the singular value decomposition, with a further claim: the construction it builds is the machinery behind much of machine learning. The same argument that answers an idle question about ellipses is the algorithm behind principal component analysis, kernel methods, and PageRank, and it is not only the results that transfer but the proofs themselves, run as procedures. The usual introduction states $A = UΣV^T$ and justifies it via the spectral theorem applied to $A^T A$ . This is correct but unilluminating, since it assumes a powerful theorem to reach a result that is, in the end, about ellipses. Part I reverses the order. A linear map sends the unit circle to an ellipse; one asks which input directions map to its axes, and finds, example after example, that they are perpendicular. In the plane this can be watched: rotate a frame, track how far its images are from perpendicular, and a sign change forces a frame where they are exactly perpendicular, which is also where the map stretches hardest. Maximizing the stretch and recursing generalizes this to n dimensions, with singular values falling out in order, and the construction proves the spectral theorem rather than assuming it. Part II puts each construction to work: maximize-and-recurse becomes the power method and PageRank; the lemma locating the maximizer becomes the stopping rule of gradient descent; the duality between $A^T A$ and $A A^T$ becomes the transport at the heart of kernel PCA. Each connection is stated with its boundary, saying what the decomposition supplies and where another idea takes over. Prerequisites are the standard sophomore sequence, and the worked examples are small enough to check by hand.

Figures & tables

Panel of Figure 1 — Figure 1: The unit circle maps to an ellipse under $A=\left(\begin{smallmatrix}2&1\\ -0.5&1.5\end{smallmatrix}\right)$ . The ellipse’s axes point along $\mathbf{u}_{1}$ (long, length $\sigma_{1}$ ) and $\mathbf{u}_{2}$ (short, length $\sigma_{2}$ ). Their preimages $\mathbf{v}_{1},\mathbf{v}_{2}$ — the input directions $A$ sent to the axes — are marked on the circle. The question of § 1.1 is whether those preimages are perpendicular.

Panel of Figure 2 — Figure 2: Sweeping the frame. Each panel shows an orthonormal input frame (left, always perpendicular) and its image under $A=\left(\begin{smallmatrix}2&1\\ -0.5&1.5\end{smallmatrix}\right)$ (right, generally not). The number below each image is the angle between $A\mathbf{v}_{1}$ and $A\mathbf{v}_{2}$ ; the shaded wedge makes it visible. As $\theta$ increases the wedge narrows to $70^{\circ}$ , then widens back through $90^{\circ}$ — the highlighted panel, where the right angle survives — and on past $110^{\circ}$ . The plot below tracks $f(\theta)$ over the full half-turn: a pure sinusoid in $2\theta$ with no vertical offset, crossing zero exactly twice, at $34.10^{\circ}$ and $-55.90^{\circ}$ . Those two crossings are $90^{\circ}$ apart and describe the same pair of lines.

Panel of Figure 3 — Figure 3: The three-dimensional experiment. The unit sphere (left) maps under $A=\left(\begin{smallmatrix}1&2&0\\ 0&1&1\\ 1&0&1\end{smallmatrix}\right)$ to an ellipsoid (right). The ellipsoid’s three axes $\sigma_{i}\mathbf{u}_{i}$ are mutually perpendicular; their preimages $\mathbf{v}_{i}$ — the input directions $A$ sends to those axes — form an orthonormal triple. The phenomenon of § 1.1 survives intact into three dimensions.

Panel of Figure 4 — Figure 4: The same sweep, watching length instead of angle. Each panel shows $\mathbf{v}_{1}$ at angle $\theta$ and its image $A\mathbf{v}_{1}$ , with the image ellipse faint behind it. Since $\mathbf{v}_{1}$ is a unit vector its image always lands on the ellipse; what changes is how far around, and so how long the arrow is. The first five panels climb — $1.69,1.82,2.06,2.22$ — until at $\theta=34.10^{\circ}$ the arrow reaches the long axis and $\|A\mathbf{v}_{1}\|=\sigma_{1}$ . The last panel jumps to $\theta=-55.90^{\circ}$ , the other extremum, where the arrow sits on the short axis and $\|A\mathbf{v}_{1}\|=\sigma_{2}$ . Below, $g(\theta)=\|A\mathbf{v}_{1}\|^{2}$ (solid) is plotted against $f(\theta)$ (dashed, the same curve as in Figure 2 ). The zeros of $f$ fall exactly at the peak and trough of $g$ — which is what $dg/d\theta=2f$ says: $f$ is the slope of $g$ .

Panel of Figure 5 — Figure 5: Two proofs, two ends of the map. Left: the input-side construction of §§ 2 – 2.5 — maximize $\|A\mathbf{v}\|$ over the sphere, landing on the eigenvectors $\mathbf{v}_{i}$ of $A^{\mathsf{T}}A$ . Right: the output-side construction — the ellipsoid’s axes are its extremal radii, where the radius meets the surface at a right angle (marked), and these are the eigenvectors $\mathbf{u}_{i}$ of $AA^{\mathsf{T}}$ . The arrow $A$ links the two: $A\mathbf{v}_{i}=\sigma_{i}\mathbf{u}_{i}$ . Same variational instinct — extremize a length — applied at opposite ends.

Panel of Figure 6 — Figure 6: The two proofs as one square. Down the left, the input-side construction lands on the eigenvectors of $A^{\mathsf{T}}A$ ; down the right, the output-side construction lands on the eigenvectors of $AA^{\mathsf{T}}$ . Across the top, $A$ carries sphere to ellipsoid; across the bottom, $A\mathbf{v}_{i}=\sigma_{i}\mathbf{u}_{i}$ identifies the two frames as the same decomposition seen from opposite corners. The SVD is the square commuting.

Panel of Figure 7 — Figure 7: The unit circle and its image. The frame $\mathbf{v}_{1},\mathbf{v}_{2}$ at $34.10^{\circ}$ is the one whose images stay perpendicular; those images land on the ellipse’s axes, with lengths $\sigma_{1}=2.2575$ and $\sigma_{2}=1.5504$ . The input frame sits at $34.10^{\circ}$ and the output frame at $10.90^{\circ}$ : a gap of $23.20^{\circ}$ . The two panels are different copies of $\mathbb{R}^{2}$ ; the only link between them is the pairing $\mathbf{v}_{i}\mapsto\sigma_{i}\mathbf{u}_{i}$ .

	$\sigma_{1}$	$\sigma_{2}$	$\mathbf{v}_{1}$ angle	$\mathbf{u}_{1}$ angle	gap $UV^{\mathsf{T}}$
Generic $\left(\begin{smallmatrix}2&1\\ -0.5&1.5\end{smallmatrix}\right)$	$2.2575$	$1.5504$	$34.10^{\circ}$	$10.90^{\circ}$	$23.20^{\circ}$
Shear $\left(\begin{smallmatrix}1&1\\ 0&1\end{smallmatrix}\right)$	$1.6180$	$0.6180$	$58.28^{\circ}$	$31.72^{\circ}$	$26.57^{\circ}$

Table 1: Neither matrix has aligned frames; both rotate by roughly

25^{\circ}

between input and output. Alignment

U=V

would require

A

symmetric positive definite (§ 7 ), and neither matrix is symmetric.

Explore similar work

May 10, 2026math.NA

Accelerating Power Method with Fast Sketching for Stronger Low-Rank Approximation

The power method is one of the most fundamental tools for extracting top principal components from data through low-rank matrix approximation. Yet, when the target rank is large, the cost of matrix multiplication associated with this procedure becomes a major bottleneck. We develop an algorithmic and theoretical framework for accelerating the power method using fast sketching, which is a popular paradigm in randomized linear algebra. Our framework leads to simple and provably efficient methods for singular value decomposition, low-rank factorization, and Nyström approximation, which attain strong numerical performance on benchmark problems. The key novelty in our analysis is the use of regularized spectral approximation, a property of fast sketching methods which proves more flexible in generalizing power method guarantees than traditional arguments.

Shabarish Chenakkod, Michał Dereziński

University of Michigan, Ann Arbor, MI 48105.

Low-Rank Structure Principal Component Analysis Approximation

Ask PDF

Jul 24, 2026math.NA

Singular value soft-thresholding via the polar decomposition

Singular value soft-thresholding can be computed via a reduction to the matrix polar decomposition, which allows one to exploit GPU-friendly algorithms for computing the polar decomposition. Empirically, there is a significant speed-up on GPUs compared to the standard approach using the SVD. We leave the investigation of robustness to future work, but note that due to the discontinuous nature of the sign function, the reduction to the polar decomposition is likely only suitable for low-accuracy applications.

Stephen Becker

University of Colorado Boulder, USA

Singular Value Decomposition Sign Value

Ask PDF

May 27, 2026math.OC

Manifold-based Algorithms for the Hadamard Decomposition

Given a matrix

X

, and two ranks

r_1

and

r_2

, the Hadamard decomposition (HD) looks for two low-rank matrices,

X_1

of rank

r_1

and

X_2

of rank

r_2

, both of the same size as

X

, such that

X\approx X_1\circ X_2

, where

\circ

is the Hadamard (element-wise) product. In most cases, HD is more expressive than standard low-rank approximations such as the truncated singular value decomposition (TSVD), as it can represent higher-rank matrices with the same number of parameters; this is because the rank of

X_1 \circ X_2

is generically equal to

r_1 r_2

. In this paper, we first present some theoretical insights for HD, in particular a useful reformulation

X\approx WH^\top

where

W

and

H

have

r_1 r_2

columns and belong to certain manifolds. These allow us to develop three new algorithms for computing HD. The first one uses the representation

X\approx X_1\circ X_2

and relies on the Manopt toolbox. The other two rely on the reformulation

X\approx WH^\top

: one is a block projected gradient method, and the other is a manifold-based gradient descent algorithm that does not require projection onto the feasible set. The last two algorithms are particularly effective for handling large sparse data. We also propose new initializations that allow us to improve the accuracy of the HD. We compare our algorithms and initialization strategies with the TSVD and with the state of the art. Numerical results show that the new methods are efficient and competitive on both synthetic and real data.

Nicolas Gillis, Subhayan Saha, Stefano Sicilia +1

Department of Mathematics and Operational Research, University of Mons, Mons, Belgium. · SS is a member of the Gruppo Nazionale Calcolo Scientifico-Istituto Nazionale di Alta Matematica (GNCS-INdAM).

Randomized Hadamard Transforms Singular Value Decomposition Low-Rank Structure Decomposition

Ask PDF