Sampling for Subset Selection and Applications
Talkat Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013) · 2013-09-16..09-19·
summary
Shows that picking roughly k/ε rows (or O(k/ε) columns) by adaptive sampling or volume sampling yields a 1+ε low-rank approximation in time about n·d·k/ε (linear in nonzeros), improving on additive JL-style guarantees. Gives efficient volume-sampling algorithms (poly(k,d) or nd·k^2/ε^2 for approximate sampling), connects volume sampling to determinantal point processes and to leverage-score and deterministic sparsification approaches, and lists concrete uses: Nystrom kernel speedups, CUR decompositions, kmeans++ initialization and Lasserre SDP rounding.
AI-written summary · about
chapters (14)
- 0:00Intro
- 0:42Sample? why? when?
- 1:20Outline
- 2:15Data = structure + noise
- 4:04Singular vectors and SVD
- 4:31Low-rank matrix approximation
- 6:10Dimension reduction
- 8:19Adaptive sampling and volume sampling
- 12:35Why can we do volume sampling efficiently?
- 17:46Deterministic row/column subset selection
- 20:06From volume sampling to DPPs
- 24:37k-means++ clustering
- 26:52Guruswami-Sinop rounding of Lasserre SDPs
- 31:56Summary
related talks
01h 26mStreaming, Sketching and Sufficient Statistics II
37mLow-rank Matrix Completion: Adaptive Sampling Can Help When, How?
01h 09mSketching High-Dimensional Data
01h 03mSketching as a Tool for Numerical Linear Algebra
01h 13mSketching High-Dimensional Data
01h 10mSketching High-Dimensional Data
01h 10mSketching High-Dimensional Data
52mCoresets and Their Applications to Design Sublinear Algorithms