Dimensionality Reduction

Describe one cup of coffee and you might list its acidity, sweetness, body, aroma, bitterness, aftertaste. That is six numbers for a single cup — a point in six-dimensional space. Add a few more notes and you are in a space no human eye can ever picture.

This is the everyday reality of data. A photo is thousands of pixels; a customer is dozens of behaviors; a gene profile is tens of thousands of measurements. Each new feature is another axis, and past three axes our intuition simply stops.

Dimensionality reduction is the art of folding all those axes down to two or three — few enough to draw — while keeping the part that matters: which points are close, which clusters apart, what the data is shaped like. The trick is deciding what to keep and what to throw away.

Below is a cloud of 3D points seen from above. You have to flatten it onto a single line (a 1D shadow). The question PCA answers: which direction keeps the most spread — the most information?

<p class="hint">{{hint}}</p>
<canvas id="cv" width="320" height="320"></canvas>
<div class="ctl">
  <label>{{label_angle}} <span id="ang">0</span>&deg;</label>
  <input id="slider" type="range" min="0" max="179" value="0">
</div>
<div class="status" id="status">{{status_init}}</div>
<div class="btns">
  <button id="find" type="button">{{btn_find}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
canvas { background: #f3f6f9; border: 1px solid #cdd9e3; border-radius: 10px; display: block; touch-action: none; }
.ctl { margin: .7rem 0 .3rem; font-size: .9rem; color: #1d3557; }
.ctl label { font-weight: 600; }
input[type=range] { width: 100%; margin-top: .3rem; }
.status { font-size: 1rem; font-weight: 700; margin: .4rem 0; min-height: 1.4em; color: #1d3557; }
.status.best { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Spin the projection line and watch the variance kept rise and fall. Checking a given direction is cheap: project every point, measure the spread. Finding the best direction by hand is fiddly — but press Find best axis (PCA) and the computer lands on the principal component, the line that preserves the most variance. That single best direction is exactly what PCA computes from the data's covariance.

How hard is it to compress dimensions well?

• Linear reduction (PCA) is tractable. Introduced by Karl Pearson (1901) and formalized by Harold Hotelling (1933), PCA finds the directions of greatest variance as the eigenvectors of the covariance matrix. Computing them is an eigenvalue / singular-value-decomposition problem solvable in polynomial time — about $O(n \cdot d^{2} + d^{3})$ for n points in d dimensions. Cheap, exact, and unique up to sign.
• The catch is the curse of dimensionality. As d grows, points spread out until distances all look the same and "nearest neighbor" loses meaning. Keeping more axes preserves information but costs storage, noise and compute; keeping fewer is readable but lossy. That information-versus-cost tradeoff is the heart of the problem.
• Nonlinear reduction is harder. Methods like t-SNE (van der Maaten & Hinton, 2008) and UMAP (McInnes et al., 2018) can unfold curved structure PCA misses, but they optimize a non-convex objective — no single exact answer, results depend on initialization and parameters, and naive versions cost $O(n^{2})$.

So the polite version (linear, variance-preserving) is a clean polynomial-time eigenvalue computation, while the faithful version (nonlinear, neighbor-preserving) is an approximate optimization with all the trouble that brings — the same kind of landscape you meet in non-convex optimization.

Reducing dimensions is one of the quietest workhorses in all of data science:

• Visualization: biologists squeeze tens of thousands of gene measurements per cell into a 2D map where cell types fall into visible clusters.
• Compression and denoising: keep the top components of an image or signal and you store far less while discarding mostly noise.
• Faster, leaner models: fewer input axes mean less overfitting and quicker training — reduction is a standard preprocessing step before classifiers and neural-network training.
• Embeddings everywhere: word, image and user embeddings are high-dimensional vectors routinely projected down for search, clustering and exploration.

Whenever you've seen a tidy 2D scatter of something that obviously had way more than two properties, dimensionality reduction did the folding — and the choice of what to keep shaped what you saw.

Dimensionality reduction is a bargain we strike with our own eyes: we cannot see ten axes, so we fold them into two and accept a little loss in exchange for a picture we can actually read. PCA makes that bargain precise and cheap — the best linear view is just the top eigenvectors of the covariance, found in polynomial time.

But "best" always means "best at preserving something," and the moment we want curved structure faithfully unrolled, we step into non-convex optimization with no perfect answer. The next time a complicated dataset collapses into a clean, readable plot, remember: a lot was thrown away on purpose — and choosing what to keep was the whole game. It is a close cousin of compression, where keeping the signal and dropping the rest is the entire point.