Frequent Directions Matrix Sketch

Compressing a Matrix Row by Row

Let $A\in\mathbb R^{n\times d}$ arrive one row at a time. Frequent Directions (FD) retains only an $\ell\times d$ matrix $B$. Think of compressing a stack of measurements whenever it fills: singular directions are found, the same squared amount is shaved from each, and the newly zero direction becomes space for the next row.

For every unit vector $x$, $\lVert Ax\rVert_2^2=x^\top A^\top Ax$ is the full directional energy and $\lVert Bx\rVert_2^2$ is its sketch estimate. FD deterministically controls their difference. With $\ell=2$ and rows $(3,0),(0,1)$, squared singular values are $(9,1)$. Subtracting $\delta=1$ gives $(8,0)$, so the covariance loss is exactly $\operatorname{diag}(1,1)$.

Singular-value shrinkage subtracts a shared threshold from squared singular values. Covariance error means $A^\top A-B^\top B$. Low-rank tail energy is $\lVert A-A_k\rVert_F^2$. Mergeability means sketches of partitions can be stacked and sketched again. Determinism removes random failure probability, not floating-point error.

Shrinkage, Singular Values and the Covariance Invariant

When full, write $B=U\Sigma V^\top$, set $\delta=\sigma_\ell^2$, and update \[ B\leftarrow\sqrt{\max(\Sigma^2-\delta I,0)}\,V^\top. \] For every unit $x$, one compression loses at most $\delta$, because expansion in the right-singular basis gives a convex combination of losses no larger than $\delta$. Frobenius energy falls by at least $\ell\delta$. Summing thresholds as $\Delta=\sum_t\delta_t$ yields \[ 0\le\lVert Ax\rVert_2^2-\lVert Bx\rVert_2^2\le\Delta,\qquad \ell\Delta\le\lVert A\rVert_F^2-\lVert B\rVert_F^2. \] Charging the top $k$ directions proves, for every $k$ strictly smaller than $\ell$, \[ \Delta\le\frac{\lVert A-A_k\rVert_F^2}{\ell-k}. \] Negative rows do not delete old rows: covariance is quadratic, so $a$ and $-a$ both add $aa^\top$. Uncentered input estimates second moments, not centered covariance.

flowchart TD
 A[Insert rows] --> B[Buffer full]
 B --> C[Compute SVD]
 C --> D[Set delta to smallest squared singular value]
 D --> E[Shrink all squared values]
 E --> F[Directional loss at most delta]
 E --> G[Frobenius loss at least ell delta]
 F --> H[Accumulate Delta]
 G --> H
 H --> I[Charge top k directions]
 I --> J[Tail relative covariance bound]
 A --> K{Delete or schema mismatch?}
 K -->|yes| L[Model invalid]
 K -->|no| B
 classDef navy fill:#17365D,color:#fff,stroke:#17365D;
 classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
 classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
 classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
 class A,B,C navy;
 class D,E,F,G,H purple;
 class I,J teal;
 class K,L crimson;

Spectral Error from Accumulated Shrinkage

Because the inequality holds for every unit vector, \[ \lVert A^\top A-B^\top B\rVert_2\le\Delta. \] Thus FD never invents covariance energy in exact arithmetic. The top right-singular vectors of $B$ support streaming PCA, while tail energy determines the meaningful sketch size.

import numpy as np

class FrequentDirections:
    def __init__(self, ell, d):
        if ell < 2 or d < 1:
            raise ValueError("invalid dimensions")
        self.ell, self.d = ell, d
        self.B = np.zeros((ell, d))
        self.used = 0
        self.total_delta = 0.0

    def append(self, row):
        row = np.asarray(row, dtype=float)
        if row.shape != (self.d,) or not np.all(np.isfinite(row)):
            raise ValueError("invalid row")
        if self.used == self.ell:
            self.compress()
        self.B[self.used] = row
        self.used += 1

    def compress(self):
        _, s, vt = np.linalg.svd(self.B, full_matrices=False)
        delta = s[-1] ** 2
        shrunk = np.sqrt(np.maximum(s ** 2 - delta, 0))
        self.B = shrunk[:, None] * vt
        self.total_delta += delta
        self.used = int(np.count_nonzero(shrunk > 1e-12))

    def finish(self):
        if self.used == self.ell:
            self.compress()
        return self.B.copy()

rng = np.random.default_rng(12)
A = rng.normal(size=(60, 8))
A[:, 0] *= 4
fd = FrequentDirections(5, 8)
for row in A:
    fd.append(row)
B = fd.finish()
loss = A.T @ A - B.T @ B
eigs = np.linalg.eigvalsh(loss)
assert eigs[0] > -1e-8
assert eigs[-1] <= fd.total_delta + 1e-8
assert np.linalg.norm(A, "fro")**2 - np.linalg.norm(B, "fro")**2 >= 5*fd.total_delta - 1e-7

zero = FrequentDirections(3, 4)
for _ in range(7):
    zero.append(np.zeros(4))
assert np.allclose(zero.finish(), 0)
try:
    fd.append([1, 2])
    raise AssertionError("invalid row accepted")
except ValueError:
    pass

delete_case = np.array([[2.0, 0.0], [-2.0, 0.0]])
assert np.allclose(delete_case.T @ delete_case, np.diag([8.0, 0.0]))
print("spectral error:", round(float(eigs[-1]), 6))
print("accumulated shrinkage:", round(fd.total_delta, 6))

Streaming PCA and Regression

Teaching: stream a two-direction matrix and compare exact and sketched eigenvalues. Production: sketch centered telemetry rows, merge only compatible shards, and refresh principal components from $B$. Regression requires a theorem matching the response-aware objective; covariance preservation alone is not a universal regression guarantee. Reject FD for row deletions or lifetime sketches that must forget old data.

Invalidating evidence includes spectral error above the tail budget, materially negative covariance-loss eigenvalues, unstable principal angles, poor held-out reconstruction, incompatible feature dictionaries, overflow, or merge-tree sensitivity beyond tolerance.

flowchart TD
 A[Define covariance objective] --> B[Center and version features]
 B --> C[Choose k and ell]
 C --> D[Validate against exact sample]
 D --> E{Error and task quality pass?}
 E -->|yes| F[Deploy compatible shard sketches]
 E -->|no| G[Increase ell or reject]
 F --> H[Monitor spectral error and drift]
 H --> I{Assumptions valid?}
 I -->|yes| H
 I -->|no| G
 classDef navy fill:#17365D,color:#fff,stroke:#17365D;
 classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
 classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
 classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
 class A,B,C navy;
 class D,F purple;
 class E,H teal;
 class G,I crimson;

Implement and Test Frequent Directions

Implement from invariants, keeping exact covariance beside the sketch on small tests.