Recovering Hidden Sparsity via Sum of Squares
summary
Planted sparse vectors inside a random Haar subspace can be recovered even when the sparse support fraction mu is constant (not 1/√N) for subspace dimension D = O(√N), by replacing L1/∞ tests with a two-to-four norm certificate and certifying it with low-degree polynomials. The algorithm solves a degree-8 Lasserre (Sum of Squares) SDP that proves a bound on the random subspace (via matrix-concentration style arguments) and then uses a small LP to round the correlated solution to exact recovery when mu is constant.
AI-written summary · about
chapters (9)
- 0:00Introduction and goals
- 1:08Sparsity and hierarchies
- 4:47Dictionary learning overview
- 11:25Planted sparse recovery
- 14:21Additional sparse problems
- 20:25SOS hierarchy mechanics
- 30:14Algorithmic design logic
- 43:40Two to four norm analysis
- 51:43Proof and conclusion
related talks
27mOptimal Spectral Recovery Of A Planted Vector In A Subspace
40mThe Trimmed Lasso: Sparse Recovery Guarantees And Practical Optimization
56mSparsifying Generalized Linear Models
45mSemi-Random Models and Robustness in Unsupervised Learning
48mInput-sparsity Time Algorithms for Embeddings and Regression Problems
44mSome Problems of Robust High-dimensional Statistics
01h 06mLP/SDP Hierarchies and Sum of Squares Proofs 4
29mSum Of Squares Lower Bounds Versus Low-Degree Polynomial Lower Bounds