Going Off the Grid
Talkat Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013) · 2013-09-16..09-19·
summary
Frames sparse sum-of-sinusoids with continuous frequencies as a convex recovery problem using the atomic norm, proves exact and stable recovery under a frequency separation condition (minimum ≈4/N) and shows mean squared error scales like s log n / N (near minimax). Recovery from random subsampling needs about O(s log s log n) samples and the convex program reduces to a semi-definite program that denoises and localizes frequencies more robustly than Prony/SVD roots; lasso on a fixed grid predicts the signal well but mislocalizes frequencies.
AI-written summary · about
chapters (17)
- 0:00Intro
- 0:53We live in a continuous world...
- 3:42Observe a sparse combination of sinusoids
- 9:22Linear Inverse Problems
- 12:12Sparsity
- 15:44Atomic Norms
- 16:56Atomic Norm Minimization
- 17:41Union of Subspaces
- 21:15Robust Recovery (deterministic)
- 23:11Atomic Norm for Spectrum Estimation
- 23:35Which atomic norm for sinusoids?
- 27:13Nearly optimal rates
- 28:59Mean Square Error
- 30:12Localization Guarantees
- 31:40Frequency Localization
- 32:39Incomplete Data/Random Sampling
- 37:22Summary and Future Work
related talks
32mReconstructing Continuous Signals via Leverage Score Sampling
01h 05mRecovering Hidden Sparsity via Sum of Squares
27mOptimal Spectral Recovery Of A Planted Vector In A Subspace
01h 26mStreaming, Sketching and Sufficient Statistics II
39mFast Spectral Algorithms from Sum-of-Squares Analyses
34mA Polynomial Time Algorithm for Lossy Population Recovery
44mSome Problems of Robust High-dimensional Statistics
19mSupport Recovery in Universal One-bit Compressed Sensing