Optimal Spectral Recovery Of A Planted Vector In A Subspace
summary
Recovery targets a structured vector hidden in a random D-dimensional subspace by observing an N×D basis matrix whose rows are IID samples that are Gaussian except in one fixed direction U where entries follow distribution mu. A practical algorithm forms a degree-4 spectral matrix (entries are constant-degree polynomials in Y) and takes its top (or bottom for dense ±1) eigenvector; success is controlled by ||v||_4^4 - 3N (sparsity threshold at about 1/3), and a matching low-degree polynomial lower bound rules out any constant-degree spectral method in the conjectured hard regime.
AI-written summary · about
chapters (9)
- 0:00Intro
- 0:31Planted Vector Problem
- 3:13Prior Work
- 4:51A Helpful Reformulation
- 11:20Upper Bound (Algorithm)
- 13:58Upper Bound: Proof Idea
- 20:50Proof: Failure of Spectral Methods
- 21:51Low-Degree Polynomial Lower Bounds
- 24:15Summary
related talks
01h 05mRecovering Hidden Sparsity via Sum of Squares
23mLow-Rank Matrix Recovery Through Rank-One Projections
44mSome Problems of Robust High-dimensional Statistics
01h 02mTheory and Big Data
39mThe Overlap Gap Property in Principal Submatrix Recovery
39mFast Spectral Algorithms from Sum-of-Squares Analyses
49mSpectral Algorithms for Learning Latent Variable Models
01h 31mUnsupervised Learning