SAHD: Going off the Grid - Benjamin Recht

From the SAHD workshop:

Ben Recht - Going off the Grid ( Slides )

Near Minimax Line Spectral Estimation by Gongguo Tang, Badri Narayan Bhaskar and Benjamin Recht

This paper establishes a nearly optimal algorithm for estimating the frequencies and amplitudes of a mixture of sinusoids from noisy equispaced samples. We derive our algorithm by viewing line spectral estimation as a sparse recovery problem with a continuous, in nite dictionary. We show how to compute the estimator via semide nite programming and provide guarantees on its mean-square error rate. We derive a complementary minimax lower bound on this estimation rate, demonstrating that our approach nearly achieves the best possible estimation error. Furthermore, we establish bounds on how well our estimator localizes the frequencies in the signal, showing that the localization error tends to zero as the number of samples grows. We verify our theoretical results in an array of numerical experiments, demonstrating that the semide nite programming approach outperforms two classical spectral estimation techniques

but also:

• Compressed Sensing off the grid - Gongguo Tang,  Badri Narayan Bhaskar, Parikshit Shah, Benjamin Recht
• Atomic Norm Denoising with applications to Line Spectral Estimation -  Badri Narayan Bhaskar, Benjamin Recht 
• Atomic Norm Denoising with applications to Line Spectral Estimation -  Badri Narayan Bhaskar, Gongguo Tang, Benjamin Recht

Related:

• Sunday Morning Insight: The 200 Year Gap.
• Robust Near-Separable Nonnegative Matrix Factorization Using Linear Optimization - implementation -
• Robustness Analysis of HottTopixx, a Linear Programming Model for Factoring Nonnegative Matrices - implementation -
• Hott Topixx: Factoring nonnegative matrices with linear programs - implementation -
• Blind Deconvolution using Convex Programming - implementation -

Thank you to the organizers of SAHD, David Brady, Robert Calderbank,Lawrence Carin, Ingrid Daubechies,David Dunson, Mauro Maggioni, Sayan Mukherjee, Guillermo Sapiro and Rebecca Willett for making these videos available.
Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.