Compressed sensing and Approximate Message Passing with spatially-coupled Fourier and Hadamard matrices - implementation -

So it continues, Florent Krzakala, Jean Barbier and Christophe Schülke have a version of their seeded 'magic matrices'  expanded to include Hadamard and Fourier blocks instead of random matrices.

Here is the paper: Compressed sensing and Approximate Message Passing with spatially-coupled Fourier and Hadamard matrices by Jean Barbier, Florent Krzakala, Christophe Schülke

We study compressed sensing of real and complex sparse signals using an optimal and computationally efficient procedure based on the combined use of approximate message-passing and spatially-coupled measurement matrices with fast Fourier and Hadamard operators. We compare the performance of our algorithm, that uses deterministic matrices, with the performance of approximate message-passing using purely random Gaussian matrices, for which the asymptotic behavior is exactly given by the density evolution. We show empirically that after proper randomization, the underlying structure of the operators does not significantly affect the performances of the reconstruction, thus allowing a fast and memory efficient reconstruction up to the information theoretic limit.

The results are as impressive as two years ago when they broke the Donoho-Tanner phase transition.
The implementation is on GitHub. The main project page is at: http://aspics.krzakala.org/. Of related interest: Current trends in the statistical physics of disordered systems : From statistical physics to computer science by Florent Krzakala

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.