Optimization II
summary
Claim: an S-sparse x0 in R^n is the unique optimal solution of L1 minimization from m Gaussian measurements when m ≥ (1+ε)(2S log n)+S+1 with failure probability exponentially small. Proof builds a least-squares dual certificate λ solving A_T^T λ = sign(x0)_T via the pseudoinverse, uses independence of A_T and A_{T^c}, bounds ||λ||^2 through inverse-Wishart → inverse-chi-squared tail bound, then applies Gaussian tail bounds to control all off-support entries.
AI-written summary · about
chapters (6)
related talks
01h 23mImplicit Regularization II
56mSparsifying Generalized Linear Models
45mHigh Dimensional Robust Sparse Regression
31mPlanted Geometric Matching Problems
01h 11mOptimization and Sampling Under Symmetry: Part 1 -- Examples
01h 06mLP/SDP Hierarchies and Sum of Squares Proofs 4
42mDimensionality Reduction Via Sparse Matrices
40mThe Trimmed Lasso: Sparse Recovery Guarantees And Practical Optimization