Monday, August 25, 2014

Turbo Compressed Sensing with Partial DFT Sensing Matrix - implementation -

Junjie just let me know of the following:

Dear Igor,
I'm a reader of your Nuit Blanche blog, and I benefit a lot from it.
Recently we wrote a paper called "Turbo compressed sensing with partial DFT sensing matrix", available at​ .
In that paper, we developed a simple iterative signal recovery algorithm for partial DFT sensing matrix (or more generally sub-sampled row orthogonal matrix). As we know, the state evolution of AMP (approximate message passing) is developed for i.i.d matrix and may not be accurate for a partial DFT sensing matrix, especially when the sparsity level is high. In our paper, we developed a signal recovery algorithm and analyzed its state evolution. Our numerical experiments show that the state evolution matches well with simulation. What is exciting is that the state evolution of our approach is consistent with the theoretical prediction for partial DFT sensing matrix in the following paper:
A. Tulino, G. Caire, S. Verdu, and S. Shamai, “Support recovery with sparsely sampled free random matrices,” IEEE Trans. Inf. Theory, vol. 59, no. 7, pp. 4243–4271, July 2013.
I therefore view our method as an extension of AMP from i.i.d matrix to partial DFT matrix.

I hope you find our paper interesting. Any comment is welcome.
Best regards,


In this letter, we propose a turbo compressed sensing algorithm with partial discrete Fourier transform (DFT) sensing matrices. Interestingly, the state evolution of the proposed algorithm is shown to be consistent with that derived using the replica method. Numerical results demonstrate that the proposed algorithm outperforms the well-known approximate message passing (AMP) algorithm when a partial DFT sensing matrix is involved.
The implementation is on Junjie's 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.

No comments: