Low-rank Matrix Completion: Adaptive Sampling Can Help When, How?

on YouTube ↗37m

" summary

Low-rank matrix completion uses a first two-phase sampling pass: take uniform samples, estimate large row/column leverage scores from sampled row norms, then do leverage-score weighted sampling and finish with nuclear-norm (or factorized) recovery. Theory shows worst-case sample count matches uniform sampling but can drop to about n r log^2 n (or lower in power-law/coherent cases), with dependence on condition number in the proofs; simulations on 400×400 rank-10 matrices confirm substantial gains for coherent matrices and modest sensitivity to kappa.

AI-written summary · about

" chapters (13)

1. 0:00Intro
2. 1:20Low-rank matrix completion problem
3. 2:37Need additional structure: incoherence
4. 6:39Uniform-sampling matrix completion
5. 10:41A closer look at matrix leverage scores
6. 12:37Leveraged sampling
7. 17:002-phase low-rank matrix completion
8. 18:49A typical simulation result
9. 21:19An alternative 2-phase algorithm
10. 23:52Theory for two-phase algorithm
11. 28:53Simulations for two-phase algorithm
12. 33:23Summary
13. 34:45Future directions

" related talks

• 32mRandomized Numerical Linear Algebra: OverviewPetros Drineas · Randomized Numerical Linear Algebra and Applications 2018
• 48mRandomized Numerical Linear AlgebraPetros Drineas · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 01h 03mSampling for Linear Algebra, Statistics, and Optimization IMichael Mahoney · Foundations of Data Science Boot Camp 2018
• 23mLow-Rank Matrix Recovery Through Rank-One ProjectionsTony Cai · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 35mSampling for Subset Selection and ApplicationsAmit Deshpande · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 33mRandomized Least Squares Optimization and its Incredible Utility for Large-Scale Tensor Decomp...Tamara Kolda · Extroverted Sublinear Algorithms 2024
• 47mCausal Matrix Completion: Applications to Offline Causal Reinforcement LearningAnish Agarwal · Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
• 01h 02mSampling for Linear Algebra, Statistics, and Optimization IIMichael Mahoney · Foundations of Data Science Boot Camp 2018