Simple and Deterministic Matrix Sketches
Talkat Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013) · 2013-09-16..09-19·
summary
An algorithm called deterministic frequent-directions maintains an L-column sketch B so AA^T − BB^T has operator norm ≤ ε||A||_F^2 when L = 2/ε, by SVD’ing the D×L sketch, zeroing small singular directions and shrinking by the median singular value; amortized cost is O(NDL). Experiments show it beats norm-sampling, hashing and random projection on a noisy matrix, handling a 100k×10k in 3 minutes point with L=100. Sketches are mergeable and later work gets rank-k, 1+ε guarantees with L≈k/ε.
AI-written summary · about
chapters (8)
- 0:00Intro
- 0:57Data Matrices
- 2:25Streaming Matrices
- 7:53Frequent Items
- 12:45Frequent Directions
- 16:42Bounding the error
- 19:41Experiments
- 25:52Matrix Approximation
related talks
01h 04mSketching and Randomized Linear Algebra
01h 03mSketching as a Tool for Numerical Linear Algebra
01h 10mSketching for Linear Algebra: Basics of Dimensionality Reduction and CountSketch II
32mRandomized Numerical Linear Algebra: Overview
01h 27mPast, Present and Future of Randomized Numerical Linear Algebra I
59mSketching for Linear Algebra: Basics of Dimensionality Reduction and CountSketch I
01h 04mSketching for Linear Algebra III: Randomized Hadamard, Kernel Methods
01h 03mSampling for Linear Algebra, Statistics, and Optimization I