Implementation of rONE-L1

Among the many things that got my interest in the following paper, here is the tidbit:

It is shown that rONE-L1 is faster than AMP and NESTA when the number of measurements is just enough to exactly reconstruct the original sparse signal using l_1 minimization.

wow. Faster than AMP, here is the attendant paper and code:

Orthonormal Expansion $\ell_1$-Minimization Algorithms for Compressed Sensing by Zai Yang, Cishen Zhang, Jun Deng, Wenmiao Lu. The abstract reads:

Compressed sensing aims at reconstructing sparse signals from significantly reduced number of samples, and a popular reconstruction approach is $\ell_1$-norm minimization. In this correspondence, a method called orthonormal expansion is presented to reformulate the basis pursuit problem for noiseless compressed sensing. Two algorithms are proposed based on convex optimization: one exactly solves the problem and the other is a relaxed version of the first one. The latter can be considered as a modified iterative soft thresholding algorithm and is easy to implement. Numerical simulation shows that, in dealing with noise-free measurements of sparse signals, the relaxed version is accurate, fast and competitive to the recent state-of-the-art algorithms. Its practical application is demonstrated in a more general case where signals of interest are approximately sparse and measurements are contaminated with noise.

The rOne-L1 code is here. Thanks Zai.

Liked this entry ? subscribe to the Nuit Blanche feed, there's more where that came from