Frequent Directions Deterministic Row-Update Matrix Sketching via Singular-Value Shrinkage

Let Delta = sum_{i=1}^n delta_i be the total squared singular mass subtracted during FrequentDirections (Algorithms 2.1 and 3.1); the sketch B satisfies three invariants for every unit vector x in R^d: (Property 1) ||Ax||^2 - ||Bx||^2 >= 0 (A^T A >= B^T B), (Property 2) ||Ax||^2 - ||Bx||^2 <= Delta, and (Property 3) Delta*ell <= ||A||_F^2 - ||B||_F^2; bootstrapping Property 3 on the top-k singular vectors y_1, ..., y_k of A yields Delta*(ell - k) <= ||A - A_k||_F^2, proving that for all 0 <= k < ell, 0 <= ||A^T A - B^T B||_2 <= Delta <= ||A - A_k||_F^2 / (ell - k) (Theorem 1.1) and ||A - pi_B^k(A)||_F^2 <= (1 + k/(ell - k))*||A - A_k||_F^2 (Theorem 1.2).

Fast-FrequentDirections (Algorithm 3.1) doubles the sketch buffer to 2*ell x d and triggers SVD plus shrinkage by delta = sigma_ell^2 only once every ell + 1 row insertions (zeroing the last ell + 1 rows), reducing total running time from O(n*d*ell^2) to O((n/ell)*d*ell^2) = O(n*d*ell) with O(d*ell) amortized (and worst-case via active/maintenance double buffering) update time per row (Theorem 1.5, Section 3.2); moreover, sketches B_1, B_2 of A_1, A_2 are mergeable by running Algorithm 3.1 on B' = [B_1; B_2], preserving Properties 1-3 with Delta = Delta_1 + Delta_2 + delta (Section 3.1).

Via packing on the Grassmannian manifold (Kapralov-Talwar / Absil-Edelman-Koev), any matrix sketch B satisfying ||A^T A - B^T B||_2 <= ||A - A_k||_F^2 / (ell - k) (or <= varepsilon*||A - A_k||_F^2 with ell = ceil(k + 1/varepsilon)) requires Omega(d*ell) = Omega(d*k + d/varepsilon) bits of space (Theorems 1.3 and 4.1); furthermore, a one-way communication reduction from the Index problem on B = [I, R; e_{i_1}, ..., e_{i_k}] using the singular value 2 + zeta (where zeta = (sqrt(5) - 1)/2 approx 0.618) of rank-2 pairs Z_ell = (e_{i_ell} + R_{i_ell}, e_{i_ell}) proves that any row-update streaming algorithm outputting a rank-k projection P with ||A - AP||_F^2 <= (1 + varepsilon)*||A - A_k||_F^2 with probability >= 2/3 requires Omega(k*d/varepsilon) bits of space (Theorems 1.4 and 4.2, Lemma 4.1), establishing that FrequentDirections with ell = ceil(k + k/varepsilon) is space-optimal up to logarithmic word-size factors.