Adaptive Sparse Recovery with Limited Adaptivity

on YouTube ↗42m

" summary

Shows nearly tight measurement bounds for r-round adaptive sparse recovery: for constant rounds r the paper proves lower bounds of about Ω(k log^{1/r} n) and gives an algorithm matching that up to a log k and log k factor, so two rounds already need about k·√(log n) measurements and more rounds trade off as log^{1/r} n. Key tools are Gaussian hashing, reduction to high–SNR sparse recovery, and an information-theoretic analysis using mutual information level sets*. Caveat: the lower bound assumes k not too large (roughly below exponential thresholds) and the upper bound incurs a small iterated-log overhead.

AI-written summary · about

" chapters (16)

1. 0:00Start
2. 0:44Sparsity
3. 1:53Sparse Recovery / Compressive Sensing
4. 3:32Standard Sparse Recovery Framework
5. 6:47Prior Work
6. 8:17Results in adaptive sparse recovery. C = 0(1)
7. 12:31Well-understood setting 1
8. 13:361-sparse recovery non-adaptive lower bound
9. 15:331-sparse recovery changes in adaptive setting
10. 21:01l proof outline
11. 21:24Extending to general k
12. 22:14What lemma do we want for general k?
13. 29:30Wrapping up the lower bound for R=2
14. 31:11Standard sparse recovery approach
15. 32:40Basic approach: R=2
16. 35:50Triple Gaussian hashing

" related talks

• 28mCombinatorial Problems in Support Recovery for 1-bit Compressed SensingArya Mazumdar · Application-Driven Coding Theory 2024
• 40mThe Trimmed Lasso: Sparse Recovery Guarantees And Practical OptimizationBoaz Nadler · Statistics in the Big Data Era 2022
• 19mSupport Recovery in Universal One-bit Compressed SensingSoumyabrata Pal, Arya Mazumdar · ITCS 2022
• 38mAll-or-Nothing Statistical and Computational Phase Transitions in Sparse Spiked Matrix EstimationCynthia Rush · Rigorous Evidence for Information-Computation Trade-offs
• 26mLearning Sparse Data with Near-optimal Speed and Efficiency from a Variety of Measurement ProcessesSidharth Jaggi · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 44mSome Problems of Robust High-dimensional StatisticsGilad Lerman · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 23mLow-Rank Matrix Recovery Through Rank-One ProjectionsTony Cai · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 45mNoisy Estimation of Simultaneously Structured ModelsMaryam Fazel · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)