Recent Advances in Positive Semidefinite Matrix Approximation
summary
Shows how PSD structure yields sublinear-time low-rank approximation: a 1+ε Frobenius-error factorization is possible without reading all N^2 entries by treating A = B^T B, sampling columns using k^2/ε columns (adaptive or ridge leverage sampling), and forming a projection-cost-preserving sketch via row+column sampling to a ~√(n k) core. Algorithm accesses roughly n·k·poly(1/ε) entries, runs in ~n k^2 / poly(ε) time, and faces lower bounds tied to fast matrix multiplication for kernel-generated A.
AI-written summary · about
chapters (17)
- 0:00Intro
- 0:33POSITIVE SEMIDEFINITE MATRICES
- 3:12HANDLING LARGE PSD MATRICES
- 4:09PSD MATRIX APPROXIMATION
- 7:00SUBLINEAR TIME BARRIER FOR GENERAL MATRICES
- 7:53WHAT ABOUT FOR PSD MATRICES?
- 8:47EVERY PSD MATRIX IS A GRAM MATRIX
- 10:56FACTOR MATRIX LOW-RANK APPROXIMATION
- 12:30LOW-RANK APPROXIMATION VIA ADAPTIVE SAMPUNG
- 15:24SUBLINEAR TIME ALGORITHM
- 17:34NYSTRÖM ALGORITHM
- 18:09LIMITATIONS OF COLUMN SAMPLING
- 19:33COLUMN AND ROW SAMPUNG
- 20:53FINAL ALGORITHM
- 21:59SUBLINEAR TIME LOW-RANK APPROXIMATION
- 24:06OPEN QUESTIONS
- 25:00EXPLOITING ADDITIONAL STRUCTURE
related talks
35mTesting Positive Semidefiniteness and Eigenvalue Approximation
48mTesting Positive Semidefiniteness and Eigenvalue Approximation
01h 27mPast, Present and Future of Randomized Numerical Linear Algebra I
01h 04mSketching and Randomized Linear Algebra
31mSimple and Deterministic Matrix Sketches
01h 03mSampling for Linear Algebra, Statistics, and Optimization I
48mRandomized Numerical Linear Algebra
01h 06mLP/SDP Hierarchies and Sum of Squares Proofs 4