Singular Value Decomposition

Every time Netflix decides what to recommend next, every time your phone compresses a photo, every time a search engine finds the document you almost forgot to ask for — the same mathematical idea is quietly at work. It is called Singular Value Decomposition, or SVD.

The idea is surprisingly clean. Any matrix — no matter how large, how rectangular, how tangled — can be broken into three simpler matrices: one that rotates, one that stretches, and one that rotates again. Those stretching factors, the singular values, are sorted from largest to smallest. The first one captures the most important direction in the data; the second captures the next most important; and so on.

Throw away the small singular values and you still have most of the picture. Keep just a handful and you can reconstruct a surprisingly faithful approximation of the original data at a fraction of the storage cost. That is the key to image compression, latent semantic analysis, PCA, and collaborative filtering — the engine that powers recommender systems worldwide.

SVD is not a trick or a shortcut. It is a theorem: every matrix has one, and it is unique (up to signs). It is among the most important results in all of linear algebra.

The grid below represents a small grayscale image — each cell is a pixel brightness from 0 (black) to 255 (white). SVD decomposes the pixel matrix into singular values sorted from most to least important. Use the slider to set how many singular values (the rank of the approximation) to keep in the reconstruction.

<p class="hint">
  {{hint}}
</p>
<div class="controls">
  <label>{{rank_label}}: <span id="rank-val">1</span>
    <input type="range" id="rank" min="1" max="4" value="1">
  </label>
  <span id="ratio-display" class="ratio"></span>
</div>
<div class="grids">
  <div>
    <div class="grid-label">{{original}}</div>
    <div id="orig-grid" class="grid"></div>
  </div>
  <div>
    <div class="grid-label">{{rank_approx_prefix}}<span id="rank-label">1</span> {{rank_approx_suffix}}</div>
    <div id="approx-grid" class="grid"></div>
  </div>
</div>
<div class="sv-row">
  <span class="sv-label">{{singular_values}}</span>
  <div id="sv-bars" class="sv-bars"></div>
</div>
<p id="error-display" class="error-line"></p>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.controls { display: flex; align-items: center; gap: 1rem; margin-bottom: .8rem; flex-wrap: wrap; }
label { font-size: .9rem; font-weight: 600; display: flex; align-items: center; gap: .4rem; }
input[type=range] { width: 160px; cursor: pointer; }
.ratio { font-size: .82rem; color: #555; }
.grids { display: flex; gap: 1.2rem; flex-wrap: wrap; margin-bottom: .8rem; }
.grid-label { font-size: .78rem; color: #666; margin-bottom: .3rem; font-weight: 600; }
.grid { display: grid; grid-template-columns: repeat(8, 28px); gap: 2px; }
.cell { width: 28px; height: 28px; border-radius: 3px; }
.sv-row { display: flex; align-items: center; gap: .5rem; margin-bottom: .4rem; flex-wrap: wrap; }
.sv-label { font-size: .78rem; color: #666; white-space: nowrap; }
.sv-bars { display: flex; align-items: flex-end; gap: 3px; height: 36px; }
.sv-bar-wrap { display: flex; flex-direction: column; align-items: center; gap: 1px; }
.sv-bar { width: 14px; background: #c9ccd1; border-radius: 3px 3px 0 0; transition: background .2s; }
.sv-bar.active { background: #1d3557; }
.sv-num { font-size: .62rem; color: #888; }
.error-line { font-size: .82rem; color: #555; margin: 0; }

// Code not found

Notice that even with rank 1 — a single outer product — the image is already recognizable as a broad gradient. At rank 3 the main shapes are clear. At full rank you get the original back exactly. The compression ratio shows how much storage the low-rank version needs compared to the full matrix. This is essentially how JPEG-style matrix compression works.

SVD is a solved problem in the computational sense — it sits firmly in polynomial time.

• Existence and uniqueness: proved by Eugenio Beltrami (1873) and Camille Jordan (1874) independently. Every real or complex matrix has an SVD. The singular values are unique; the singular vectors are unique up to signs and rotations within repeated-value subspaces.
• Computing it: the standard algorithm runs in $O(mn \cdot \min(m,n))$ time for an $m \times n$ matrix. The matrix is first reduced to bidiagonal form (via Householder reflections), then the bidiagonal SVD is found by the QR algorithm — a globally convergent iterative method that typically needs only a handful of passes.
• Approximation: if you only need the top k singular values, randomized SVD (Halko, Martinsson & Tropp, 2011) gets an excellent approximation in $O(mn \log k + (m+n)k^{2})$ time — far faster for large sparse matrices.
• In contrast: many uses of SVD — like finding the optimal low-rank completion of a matrix with missing entries — are NP-hard in general. But computing the SVD of a fully known matrix is easy.

The reason SVD is so powerful is that it solves the problem of finding the best rank-k approximation of a matrix in the Frobenius norm. The Eckart–Young–Mirsky theorem (1936) proves that truncating to the top k singular values gives exactly that best approximation. No other rank-k matrix is closer. This is why SVD underpins dimensionality reduction and PCA.

SVD is one of those rare tools that shows up in almost every corner of computing and science:

• Image and video compression: keeping only the top-k singular values reduces storage dramatically. JPEG-style codecs use related matrix decompositions at their core.
• Recommender systems: Netflix's original prize-winning algorithm factored a huge user–movie rating matrix with SVD to predict missing ratings — effectively "filling in" what a user would think of a film they have never watched.
• Principal Component Analysis (PCA): PCA is exactly SVD of the mean-centered data matrix. The singular vectors are the principal components; the singular values tell you how much variance each captures.
• Noise reduction: in signal processing and MRI imaging, truncating small singular values removes noise while keeping the signal — the noise lives in the smallest directions.
• Pseudoinverse and least squares: the Moore–Penrose pseudoinverse $A^+ = V \Sigma^+ U^\top$ solves overdetermined or underdetermined systems — the backbone of linear regression.
• Latent Semantic Analysis (LSA): in search engines, SVD finds the hidden "topics" connecting words and documents, improving retrieval far beyond simple keyword matching.
• Spacecraft attitude control: NASA uses SVD to determine satellite orientation from star-tracker measurements, computing the optimal rotation between two sets of unit vectors (Wahba's problem).

Understanding SVD means understanding the geometry of data. It connects directly to matrix multiplication, dimensionality reduction, and the mathematical foundations of machine learning.

Singular value decomposition is one of the few results in mathematics that is simultaneously theoretically beautiful and immediately practical. It tells you the exact best way to approximate any matrix at any rank — not approximately best, not close enough, but provably optimal. And it can be computed efficiently for any matrix, no matter its shape.

Every time you adjust a slider and watch a blurry image snap into focus, you are watching the Eckart–Young theorem in action: each singular value you add is the single most valuable piece of information that was missing. The algorithm knows the right order.

That combination — proven optimality, polynomial runtime, universal applicability — is rare in computation. Most hard problems force you to choose between "fast" and "correct." SVD offers both. It is, in the best sense of the word, a solved problem: we know exactly how to do it, and we know why it works.