Frequent-Directions Deterministic Streaming Matrix Sketching

Frequent-Directions Deterministic Streaming Matrix Sketching is a deterministic one-pass row-streaming matrix sketching algorithm introduced by Liberty (2013) that maintains an l x m sketch matrix B of an n x m input matrix A by generalizing the Misra-Gries / Space-Saving frequent-items counter decrement rule to singular values and right singular vectors. In the basic algorithm (Algorithm 1), each streaming row a_i in R^m is inserted into an all-zero row of B in R^{l x m}; whenever B has no zero rows, the algorithm computes the SVD B = U Sigma V^T, sets delta_i = sigma_l^2, shrinks all l squared singular values uniformly via bar{Sigma} = sqrt(Sigma^2 - I_l delta_i), and updates B <- bar{Sigma} V^T so that the last row of B is guaranteed to be zero. In the amortized fast variant (Algorithm 2), B is zeroed out in its bottom l/2 rows by shrinking at threshold delta_i = sigma_{l/2}^2 only once every l/2 row insertions, reducing the total runtime from O(n m l^2) to O(n m l) at space O(m l). Claims 1 and 2 and Theorems 4.1 and 4.2 prove that for every unit vector x in R^m (||x||_2 = 1), 0 <= ||A x||_2^2 - ||B x||_2^2 <= 2 (||A||_F^2 - ||B||_F^2) / l <= 2 ||A||_F^2 / l (with factor 1 for Algorithm 1 and factor 2 for Algorithm 2), guaranteeing A^T A >= B^T B and ||A^T A - B^T B||_2 <= epsilon ||A||_F^2 for l = ceil(2 / epsilon).