Suppose rows of a matrix arrive one at a time.

They might be user embeddings, document counts, query features, activations, returns, telemetry, or gradients. The downstream question is familiar: which directions have large variance? Which small subspace explains most of the energy? Can I regress, cluster, whiten, or run PCA without storing every row?

The object those questions keep touching is not the raw matrix (A). It is the covariance-shaped shadow

\[A^\top A.\]

For any unit direction (x),

\[x^\top A^\top A x = \|Ax\|_2^2.\]

That scalar asks a concrete question: if I look through direction (x), how much squared mass did the entire stream place there? A streaming covariance sketch is trying to answer that question for every (x), using a matrix (B) with only a few rows:

\[B^\top B \approx A^\top A.\]

The tiny matrix is not a sample. It is a promise about all directions.

A Sketch Is a Contract

Randomized sketches are often introduced as compression. That is true but too vague. Different sketches keep different promises.

A Gaussian range finder, as in randomized SVD, asks the matrix a few random questions, orthogonalizes the loud responses, and hopes it found the dominant subspace.1 A sparse embedding or CountSketch-style transform uses signed buckets so multiplication can be fast on sparse input, with guarantees that are usually probabilistic and often phrased as preserving norms over a subspace or supporting regression and low-rank approximation.2

Frequent Directions has a different personality. It is deterministic. It receives rows one at a time. It keeps a small dense sketch. And its cleanest guarantee is a covariance guarantee:

\[\left\|A^\top A - B^\top B\right\|_2 \le \frac{\left\|A - A_k\right\|_F^2}{\ell-k}, \qquad \ell > k.\]

Here (\ell) is the number of rows allowed in the sketch, and (A_k) is the best rank-(k) approximation to (A). The numerator is tail energy: mass that does not fit in the first (k) singular directions. The denominator is slack: the sketch rows left after you reserve (k) directions for the signal.

This theorem is beautiful because it says the sketch pays only for what a rank-(k) model could not have kept anyway. If the stream is close to low rank, the covariance shadow can be tiny.

The deterministic detail matters. The guarantee is not “with high probability, unless the seed is unlucky.” It is a worst-case statement about the rows that actually arrived.3

The Move

Frequent Directions is descended from the old streaming frequent-items idea: when a small counter table is full, decrement every counter and delete the zeros.4 That algorithm does not know which item will be important later. It removes one count from many candidates at once, so no item can be under-counted by too much.

Liberty’s original Frequent Directions paper performs the matrix version of that trick.5

Keep a sketch matrix (B). When there is room, append the incoming row. When the sketch is too full, compute an SVD

\[B = U\Sigma V^\top.\]

Then choose a shrink amount (\delta), usually the squared singular value at the cutoff, and replace each singular value by

\[\sigma_i' = \sqrt{\max(\sigma_i^2-\delta, 0)}.\]

Finally rebuild

\[B' = \Sigma' V^\top\]

and keep only the nonzero rows.

In pseudocode:

for each incoming row a:
    append a to B
    if B is full:
        compute singular values and right singular vectors of B
        delta = squared singular value at the cutoff
        subtract delta from every squared singular value
        discard the rows that became zero

The sketch forgets, but it forgets symmetrically. Large directions lose the same squared amount as medium directions. Small directions disappear. The algorithm never has to guess which future row will make a weak direction important; the theorem accounts for the total shrinkage budget.

This is why the name is so good. It does not keep frequent coordinates. It keeps frequent directions.

Why Shrinking Works

A single shrink step is a small tragedy. Every direction loses some mass:

\[\|Bx\|_2^2 - \|B'x\|_2^2 \ge 0.\]

But the loss in any fixed direction is capped by (\delta), because subtracting (\delta) from every squared singular value subtracts at most (\delta) from the quadratic form. Meanwhile the total Frobenius energy removed is larger: many directions are shaved, and at least one is zeroed.

That asymmetry is the proof engine. Per-direction damage grows like the sum of the shrink amounts. Total discarded energy also grows like that sum multiplied by the number of surplus directions. The tail energy of (A) upper-bounds how much discard can happen before a rank-(k) approximation would have had to pay for it.

So the sketch deliberately underestimates covariance. For unit (x), the Frequent Directions analyses give a one-sided form:

\[0 \le \|Ax\|_2^2 - \|Bx\|_2^2 \le \frac{\|A-A_k\|_F^2}{\ell-k}.\]

Spectral norm is just the worst direction version of that statement.

That one-sidedness is useful. An unbiased noisy estimator can be excellent on average and still produce a covariance matrix that is too large in one direction and too small in another. Frequent Directions is biased downward, but its bias is organized.

A Browser-Sized Covariance Lab

The lab below constructs a synthetic stream with a low-rank signal, isotropic noise, and optional drift in the underlying directions. It then computes the exact covariance (A^\top A) in the browser and compares three sketches with the same row budget:

  • Frequent Directions, using repeated eigendecompositions of (B^\top B) as a compact browser implementation of the shrink step.
  • CountSketch-style signed buckets, where each incoming row is assigned to one of (\ell) buckets with a random sign.
  • Uniform reservoir sample, scaled so that its expected covariance has the right magnitude.

The comparison is intentionally unfair in one respect and fair in another. It is unfair because production randomized sketching algorithms have many variants and sharper use cases than this tiny signed-bucket baseline. It is fair because all three are asked the same question:

How close is B'B to the full covariance A'A?

At the default setting, the stream has 800 rows in 28 dimensions, a rank-3 signal, noise level 0.18, 35% directional drift, and a 12-row sketch. A Node audit of the same code gives:

FD spectral error        49.83
CountSketch error      6374.90
Reservoir error        7205.46
FD theorem bound         78.26
FD top-k energy         100%
CountSketch top-k        98.6%
FD shrink steps           61

The important line is not that Frequent Directions wins this toy plot. The important line is the mismatch between the two diagnostics. CountSketch can recover nearly all top-k energy here while still being a poor full-covariance surrogate. PCA capture and covariance spectral error are related, but they are not the same contract.

The implementation is dense and pedagogical. It uses small browser eigensolvers to expose the invariant being checked; production systems would use tuned linear algebra, sparse updates, and mergeable variants.

What to Try

Lower Sketch rows toward (k+1).

The denominator (\ell-k) gets thin, and the bound loosens quickly. The sketch still behaves deterministically, but there is no magic in a memory budget with almost no slack.

Raise Noise.

Tail energy increases. Frequent Directions does not manufacture a low-rank world; it exploits one when the world gives it one. As the spectrum flattens, the covariance shadow needs more rows.

Move Drift upward.

The stream stops having one stable subspace. This is exactly where the covariance contract is clearer than the phrase “find the principal components.” If old and new directions both carry energy, the sketch must represent the combined covariance, not merely chase the latest basis.

Change Seed.

Frequent Directions should be stable in the sense that the theorem does not depend on the seed. The synthetic data generation and randomized baselines do depend on it. That distinction is part of the lesson: deterministic sketching does not remove all randomness from an experiment, but it removes algorithmic randomness from the sketch guarantee.

The Trap in “Top-k Energy”

The top-k panel can be misleading in the most educational way.

In many settings, the signed-bucket sketch captures most of the leading subspace. If the only downstream task is a rough PCA visualization, that may be fine. Randomized numerical linear algebra is a powerful toolbox, not a straw man.6

But covariance error is stricter. A sketch used inside least squares, preconditioning, whitening, anomaly detection, or online feature diagnostics may be asked for more than “roughly the same first three principal axes.” It may need not to invent a huge variance direction that was not in the stream. It may need not to erase a medium direction that later matters for regression.

That is why the spectral norm error is the right villain in this essay:

\[\left\|A^\top A - B^\top B\right\|_2 = \max_{\|x\|_2=1} \left|\,\|Ax\|_2^2 - \|Bx\|_2^2\,\right|.\]

It asks for the worst direction. Frequent Directions was designed for that question.

Centering Is Not a Footnote

The lab sketches (A^\top A) for raw rows. PCA on real data often wants the covariance of centered rows:

\[\sum_i (a_i-\bar a)(a_i-\bar a)^\top.\]

A streaming system must track the mean as well as the second moment. You can combine a running mean with a sketch of centered updates, or keep enough statistics to correct the raw second moment. The sketch theorem does not excuse you from defining the matrix whose covariance you are preserving.

This is also where data engineering enters. If embeddings are normalized, if features have wildly different units, if rare categorical expansions create high-leverage rows, the covariance shadow changes. Frequent Directions keeps a matrix promise; it does not decide whether that matrix is the right object.

Where It Fits

Frequent Directions is most attractive when the stream is large, the dimension is moderate enough for dense sketch rows, and the downstream computation cares about covariance-like geometry:

  • streaming PCA over logs, documents, embeddings, or activations;
  • online feature stores that want compact second-moment summaries;
  • distributed systems where workers can sketch partitions and merge summaries;
  • iterative modeling pipelines where keeping all historical rows is expensive;
  • privacy- or retention-constrained analytics where raw events should expire but aggregate geometry may remain.

The mergeability is important. The SIAM paper emphasizes that Frequent Directions sketches can be combined: sketch chunks separately, stack the sketches, and sketch again.3 That makes the algorithm feel less like a single-threaded streaming trick and more like a systems primitive.

A Small Way to Remember It

Random projections ask:

If I look from a few random angles, do I see the important room?

Frequent Directions asks:

If I must forget, can I charge every forgotten direction to tail energy?

The first question is exploratory. The second is accounting.

That accounting mindset is what makes the algorithm feel almost financial. The sketch maintains a ledger of covariance mass. Every compression step imposes a small haircut across the spectrum. No single direction is allowed to be robbed silently, because the total haircut must show up as discarded Frobenius energy.

The stream is gone. The rows are gone. What remains is a small matrix and a receipt:

for every direction, this is how much variance I might owe you

That is a good shape for memory to have.

Source Notes

The browser lab exports its simulator as FrequentDirectionsLab and as a CommonJS module for Node checks. I audited the default setting, a small-sketch case, a wider dimension case, a high-noise case, and a clamped edge case. The checks require finite errors, a satisfied Frequent Directions covariance bound with numerical tolerance, bounded top-k energy ratios, bounded subspace alignments, sorted exact spectra, and a sketch no larger than the requested row budget.

This is still a toy. The eigensolver is a Jacobi routine written for small browser matrices, not a replacement for LAPACK. The CountSketch baseline is a simple signed row bucket sketch, not the full universe of randomized embedding methods. The point is to make the covariance contract visible enough that the sliders can falsify your intuition before the theorem rescues it.

  1. Nathan Halko, Per-Gunnar Martinsson, and Joel A. Tropp, “Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions”, SIAM Review 53(2), 2011. ↩

  2. Kenneth L. Clarkson and David P. Woodruff, “Low rank approximation and regression in input sparsity time”, STOC, 2013. Their work is part of the sparse embedding lineage that makes randomized sketching practical for large sparse matrices. ↩

  3. Mina Ghashami, Edo Liberty, Jeff M. Phillips, and David P. Woodruff, “Frequent Directions: Simple and Deterministic Matrix Sketching”, SIAM Journal on Computing 45(5), 2016. The paper gives the standard spectral covariance and projection-error guarantees and discusses space optimality and mergeability. ↩ ↩2

  4. Jayadev Misra and David Gries, “Finding repeated elements”, Science of Computer Programming 2(2), 1982. The frequent-items decrement idea is the scalar ancestor of the matrix shrink metaphor; Frequent Directions is not literally the same algorithm, but the analogy is structurally useful. ↩

  5. Edo Liberty, “Simple and Deterministic Matrix Sketching”, KDD, 2013. Liberty presents Frequent Directions as a deterministic row-update sketch inspired by frequent-items algorithms. ↩

  6. Per-Gunnar Martinsson and Joel A. Tropp, “Randomized numerical linear algebra: Foundations and algorithms”, Acta Numerica 29, 2020. ↩