Introduction

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.

Try It: Image Compression

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">
  Each cell is a pixel (0=black, 255=white). SVD decomposes the image matrix into singular values sorted by importance. Drag the slider to choose how many to keep.
</p>
<div class="controls">
  <label>Rank: <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-<span id="rank-label">1</span> approximation</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// SVD of an 8x8 grayscale image matrix using the power-iteration / Gram-Schmidt
// approach for small matrices. Produces singular values σ₁≥σ₂≥... and
// rank-k approximation A_k = Σᵢ₌₁ᵏ σᵢ uᵢ vᵢᵀ.

const ROWS = 8, COLS = 8;

// A synthetic 8x8 "face-like" pattern: bright forehead, dark eye region, bright cheeks
const IMG = [
  [200,210,220,230,230,220,210,200],
  [190,200,215,225,225,215,200,190],
  [170,180,190, 60, 60,190,180,170],
  [160,175,185, 55, 55,185,175,160],
  [180,190,200,210,210,200,190,180],
  [150,160,100,170,170,100,160,150],
  [130,150,160,165,165,160,150,130],
  [110,130,145,150,150,145,130,110]
];

// --- tiny linear algebra helpers (no external libs) ---
function dot(a, b) { return a.reduce((s,v,i) => s + v*b[i], 0); }
function norm(v) { return Math.sqrt(dot(v, v)); }
function scale(v, s) { return v.map(x => x*s); }
function add(a, b) { return a.map((v,i) => v + b[i]); }
function sub(a, b) { return a.map((v,i) => v - b[i]); }
function matVec(M, v) { return M.map(row => dot(row, v)); }
function matTVec(M, v) { return M[0].map((_,j) => M.reduce((s,row,i) => s + row[j]*v[i], 0)); }

// Power iteration to find the largest singular triplet of A (deflating previous)
function topSingularTriplet(A) {
  let v = A[0].map((_,j) => j===0?1:0);
  for (let iter = 0; iter < 200; iter++) {
    let u = matVec(A, v);  const nu = norm(u); u = scale(u, 1/nu);
    let w = matTVec(A, u); const nw = norm(w); v = scale(w, 1/nw);
  }
  const u = (() => { let t = matVec(A, v); const n = norm(t); return scale(t, 1/n); })();
  const sigma = dot(u, matVec(A, v));
  return { u, v, sigma };
}

// Compute full thin SVD of IMG up to rank=COLS
function computeSVD(matrix) {
  const maxRank = Math.min(ROWS, COLS);
  let residual = matrix.map(r => [...r]); // deep copy
  const Us = [], Vs = [], Sigmas = [];
  for (let k = 0; k < maxRank; k++) {
    const { u, v, sigma } = topSingularTriplet(residual);
    if (sigma < 0.01) break;
    Us.push(u); Vs.push(v); Sigmas.push(sigma);
    // deflate: residual -= sigma * u * vT
    for (let i = 0; i < ROWS; i++)
      for (let j = 0; j < COLS; j++)
        residual[i][j] -= sigma * u[i] * v[j];
  }
  return { Us, Vs, Sigmas };
}

// Rank-k reconstruction
function reconstruct(Us, Vs, Sigmas, k) {
  const out = Array.from({length:ROWS}, () => new Float64Array(COLS));
  for (let t = 0; t < k; t++)
    for (let i = 0; i < ROWS; i++)
      for (let j = 0; j < COLS; j++)
        out[i][j] += Sigmas[t] * Us[t][i] * Vs[t][j];
  return out;
}

function clamp(v) { return Math.max(0, Math.min(255, Math.round(v))); }
function gray(v) { return `rgb(${v},${v},${v})`; }

function renderGrid(id, data) {
  const el = document.getElementById(id);
  el.innerHTML = '';
  for (let i = 0; i < ROWS; i++)
    for (let j = 0; j < COLS; j++) {
      const d = document.createElement('div');
      d.className = 'cell';
      d.style.background = gray(clamp(data[i][j]));
      el.appendChild(d);
    }
}

function frobenius(A, B) {
  let s = 0;
  for (let i = 0; i < ROWS; i++) for (let j = 0; j < COLS; j++) { const d = A[i][j]-B[i][j]; s+=d*d; }
  return Math.sqrt(s);
}

const { Us, Vs, Sigmas } = computeSVD(IMG);
const maxRank = Sigmas.length;

// Set slider max to actual rank
const slider = document.getElementById('rank');
slider.max = maxRank;

// Render bars
const barsEl = document.getElementById('sv-bars');
Sigmas.forEach((s, i) => {
  const wrap = document.createElement('div'); wrap.className = 'sv-bar-wrap';
  const bar = document.createElement('div'); bar.className = 'sv-bar'; bar.id = 'bar-'+i;
  bar.style.height = Math.round((s / Sigmas[0]) * 34) + 'px';
  const num = document.createElement('div'); num.className = 'sv-num'; num.textContent = Math.round(s);
  wrap.append(bar, num); barsEl.appendChild(wrap);
});

// Render original once
renderGrid('orig-grid', IMG);

function update() {
  const k = parseInt(slider.value);
  document.getElementById('rank-val').textContent = k;
  document.getElementById('rank-label').textContent = k;

  const approx = reconstruct(Us, Vs, Sigmas, k);
  renderGrid('approx-grid', approx);

  // Compression ratio: original needs ROWS*COLS values; rank-k needs k*(ROWS+COLS+1)
  const origSize = ROWS * COLS;
  const compSize = k * (ROWS + COLS + 1);
  const ratio = (compSize / origSize * 100).toFixed(0);
  document.getElementById('ratio-display').textContent =
    fmt('Storage: %compSize% vs %origSize% values (%ratio%% of original)', { compSize: compSize, origSize: origSize, ratio: ratio });

  const err = frobenius(IMG, approx);
  document.getElementById('error-display').textContent =
    fmt('Reconstruction error (Frobenius norm): %err%', { err: err.toFixed(1) });

  // highlight active bars
  Sigmas.forEach((_, i) => {
    document.getElementById('bar-'+i).className = 'sv-bar' + (i < k ? ' active' : '');
  });

  console.log(fmt('rank=%k% sigma1=%v% error=%err%', { k: k, v: Sigmas[0].toFixed(1), err: err.toFixed(2) }));
}

slider.addEventListener('input', update);
update();
Result
Console

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.

The Real Complexity

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⋅min⁡(m,n))O(mn \cdot \min(m,n)) time for an m×nm \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(mnlog⁡k+(m+n)k2)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.

Where It Matters

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Σ+U⊤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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/svd/Content licensed under CC BY-NC 4.0.