L_p Row Sampling by Lewis Weights

on YouTube ↗01h 02m

" summary

Claims a practical method to sample rows so A' preserves ||Ax||_p for all x by sampling with Lewis weights, shows existence and fast computation, and proves L1 concentration with Rademacher comparison and Khinchin bounds. Algorithms run in input-sparsity time (NNZ(A)+poly(d)); iterative weight computation contracts and converges rapidly for 0<p<4. Output sizes: ~d log d rows for p=1, d log d log log d for 1<p<2, and bounds matching prior lp estimates otherwise.

AI-written summary · about

" chapters (28)

1. 0:00Intro
2. 1:47DATA
3. 2:55SUBSAMPLING MATRICES
4. 5:42LINEAR MODEL
5. 6:48DISTANCE MINIMIZATION
6. 8:18ROW SAMPLING Pick some frescaled rows of A
7. 10:57ON GRAPHS
8. 13:08PREVIOUS POLY-TIME ALGORITHMS
9. 14:52GENERAL MATRICES
10. 17:24OUR RESULTS
11. 20:13IMPORTANCE SAMPLING
12. 22:30MATRIX-CHERNOFF BOUNDS
13. 24:52WHAT IS LEVERAGE SCORE
14. 26:11ISSUE WITHL
15. 28:08WHAT DOES WORK
16. 31:19SPLITTING BASED VIEW
17. 35:29MATRIX CONCENTRATION
18. 37:34SPLITTING ROWS
19. 41:03RECURSIVE DEFINITION FOR L
20. 43:40SUMMARY
21. 44:17COMPUTING LEWIS WEIGHTS
22. 45:51FASTER ALGORITHM
23. 50:08CONVERGENCE FOR L
24. 53:12OVERALL SCHEME
25. 55:24PROOFS OF KNOWN RESULTS
26. 57:07RADAMACHER PROCESSES
27. 58:18TRANSFORMATION
28. 58:57EACH ENTRY

" related talks

• 48mRandomized Numerical Linear AlgebraPetros Drineas · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 35mSampling for Subset Selection and ApplicationsAmit Deshpande · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 01h 26mStreaming, Sketching and Sufficient Statistics IIGraham Cormode · Big Data Boot Camp 2013
• 37mLow-rank Matrix Completion: Adaptive Sampling Can Help When, How?Rachel Ward · Optimization, Statistics and Uncertainty
• 01h 04mSampling Big Ideas in Sublinear AlgorithmsEdith Cohen · Sublinear Algorithms Boot Camp 2024
• 01h 13mSketching High-Dimensional DataJelani Nelson · Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)
• 48mInput-sparsity Time Algorithms for Embeddings and Regression ProblemsMichael Mahoney · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 01h 04mNew Algorithms for Heavy Hitters in Data StreamsDavid P. Woodruff · Real-Time Decision Making