Simple and Deterministic Matrix Sketches
matrix-sketchingstreaming-algorithmsdimensionality-reductionlinear-algebra
Abstraction: Streaming deterministic algorithm for matrix sketching with 1/ell error bound
Key points:
- Adapts a streaming item-frequency algorithm to matrix sketching; processes n rows of A (n x m) one at a time
- Maintains sketch B with only ell rows (ell << n) such that A^T A ≈ B^T B
- Error bound: for all unit x, 0 ≤ |Ax|² - |Bx|² ≤ 2|A|_f² / ell (Frobenius norm)
- Error decays as O(1/ell) using O(m·ell) space — vs. O(1/sqrt(ell)) for random projection, hashing, or sampling methods
- Amortized O(m·ell) operations per row; fully parallelizable
- Algorithm is deterministic and provably correct, unlike randomized sketching alternatives
Connections: Simons Institute · Matrix Sketching · Streaming Algorithms · Dimensionality Reduction · Pca
Source: http://simons.berkeley.edu/talks/edo-liberty-2013-09-16