EMaC : Robust Spectral Compressed Sensing via Structured Matrix Completion - implementation -

I love it when there is an implementation, it gets even more interesting when the paper shows phase transitions. Quite simply, the authors send the signal that while theoretical developments are OK, the only way to really compare all these solvers is to show how each of those perform as regards to the acid test of the sharp phase transitions. Here is a new example of that: 

Robust Spectral Compressed Sensing via Structured Matrix Completion by Yuxin Chen, Yuejie Chi

The paper explores the problem of spectral compressed sensing, which aims to recover a spectrally sparse signal from a small random subset of its n time domain samples. The signal of interest is assumed to be a superposition of r multi-dimensional complex sinusoids, while the underlying frequencies can assume any \emph{continuous} values on the unit interval. Conventional compressed sensing paradigms suffer from the {\em basis mismatch} issue when imposing a discrete dictionary on the Fourier representation. To address this problem, we develop a novel algorithm, called Enhanced Matrix Completion (EMaC), based on structured matrix completion that does not require prior knowledge of the model order. The algorithm starts by arranging the data into a low-rank enhanced form exhibiting multi-fold Hankel structure, and then attempts recovery via nuclear norm minimization. Under mild incoherence conditions, EMaC allows perfect recovery as soon as the number of samples exceeds the order of rlog3(n), and is stable against bounded noise. Even if a constant portion of samples are corrupted with arbitrary magnitude, EMaC can still allow accurate recovery, provided that the sample complexity exceeds the order of r2log3(n). Along the way, our results demonstrate the power of convex relaxation in completing a low-rank multi-fold Hankel matrix from a minimal number of observed entries. The performance of our algorithm and its applicability to super resolution are further validated by numerical experiments.

The implementation is on Yuejie Chi's publication page.


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.