Compressed Sensing: Alternating l_1 Reconstruction Algorithm.

Laurent Duval pointed out to this presentation by Stephane Chretien on Tighter relaxations for the sparsest recovery problem where he presents a new reconstruction called Alternating l_1 reconstruction algorithm:

The main problem addressed in subsequent works and still of great interest now is the one of increasing the value of k for which every k-signal can be reconstructed exactly for a given pair (n,m). We now present a generalization of the l_1 relaxation which we call the Alternating l_1 relaxation.

Using Lemarechal and Oustry’s guidance given in “Semidefinite relaxations of combinatorial optimization problems”. He uses "Lagrangian duality as a convenient framework for building convex relaxations to hard nonconvex optimization problems" and then goes on to explain his method. He then makes a comparison with the reweighted L1 method (mentioned here in Reweighted L1 and a nice summary on Compressed Sampling). Could we just hope it's faster than reweighted l1, please... pretty please?

I have added it to the list of reconstruction algorithms in the big picture section in the categories of code not implemented yet.