Sparse Polynomial Interpolation: Compressed Sensing, Super-resolution, or Prony?
Talkat Hierarchies, Extended Formulations and Matrix-Analytic Techniques (2017) · 2017-11-06..11-09·
summary
Compares three concrete methods for sparse polynomial interpolation: polynomial as atomic measure on torus, evaluate at z0^beta equals beta moment explains why evaluations → moments, and then contrasts Prony (root-finding extraction), naive l1 compressed sensing (fails when A lacks RIP), and super-resolution. Main claims: total-variation minimization (an infinite-dimensional LP) recovers the exact discrete measure when atoms are sufficiently separated and enough moments are known; solve via a truncated SDP (moment matrices PSD) and then extract atoms with a Prony step; experiments show comparable robustness and measurement counts.
AI-written summary · about
chapters (9)
- 0:00Start
- 0:02Alt or Super Resolution for Sparse Interpolation
- 4:29Prony Method
- 7:33Naive Compressed Sensing
- 8:36Restricted Isometry Property
- 10:03What Is Super-Resolution
- 10:19Super-Resolution
- 11:29Super-Resolution Theory
- 13:37Spot Interpolation
related talks
58mTensor Decomposition, Sparse Representations and Applications
26mLearning Sparse Data with Near-optimal Speed and Efficiency from a Variety of Measurement Processes
29mCompressive Sensing
01h 06mAnalytic Methods for Supervised Learning III
01h 05mRecovering Hidden Sparsity via Sum of Squares
01h 03mSampling for Linear Algebra, Statistics, and Optimization I
12mIterative Methods and High-Dimensional Statistics
01h 06mLP/SDP Hierarchies and Sum of Squares Proofs 4