Noisy Estimation of Simultaneously Structured Models

on YouTube ↗45m

" summary

Examines recovery of models that are simultaneously structured (e.g. low-rank and sparse or lifted phase retrieval) and shows that naively minimizing a convex combination of norms needs far more measurements than the object’s true degrees of freedom. A provable barrier is M below the minimum dim(T_i) (not the intersection dimension), so convex relaxations can require M ≈ nR instead of O(KR). For denoising the risk lower bound scales like min(K^2, N); a simple nonconvex two-step thresholding attains O(K) performance.

AI-written summary · about

" chapters (18)

1. 0:00Intro
2. 0:36Models with low-dimensional structure
3. 2:13Typical (low-dimensional) structures
4. 3:20Typical structures
5. 3:34Sparse and low-rank matrices: applications
6. 6:13Estimating structured models
7. 8:32Example: Sparse vectors and x.
8. 11:20Example: Low-rank matrices and ||X ||.
9. 12:53This talk: Simultaneous structures
10. 14:17Pareto optimal front
11. 16:02Decomposable norms
12. 20:29How many measurements are needed?
13. 23:02Proof sketch
14. 25:57Denoising for simultaneous structures
15. 29:06Bounds on simultaneous MSE risk
16. 32:58MSE risk for sparse and low-rank case
17. 34:52Numerical experiments
18. 39:47Discussion

" related talks

• 23mLow-Rank Matrix Recovery Through Rank-One ProjectionsTony Cai · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 52mConstrained Subset Selection Problems under Diversity MeasuresMohit Singh · Hyperbolic Polynomials and Hyperbolic Programming
• 46mCan Non-Convex Optimization be Robust?Rong Ge · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 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)
• 31mTowards Lower Bounds for Efficient Robust Estimation From Worst Case AssumptionsJerry Li · Rigorous Evidence for Information-Computation Trade-offs
• 45mHigh Dimensional Robust Sparse RegressionConstantine Caramanis · Sublinear Algorithms and Nearest-Neighbor Search
• 01h 30mHigh-Dimensional Statistics IIMartin Wainwright · Big Data Boot Camp 2013
• 49mRobust PCA via Non-convex Methods: Provable BoundsAnimashree Anandkumar · Semidefinite Optimization, Approximation and Applications 2014