CS: l_0, What Is It Good For ?

In Wikimization, one can read a presentation by Christine Law with an interesting ability to perform large subsampling using a reconstruction code using the l_0 norm as opposed to all other schemes using the l_1 or l_p norm (with p less than 1 but not equal to zero). Actually, not all schemes are using l_1 or l_p I mentioned earlier the article by G. Hosein Mohimani, Massoud Babaie-Zadeh and Christian Jutten entitled Fast Sparse Representation based on Smoothed l0 norm. They now have a new paper entitled A fast approach for overcomplete sparse decomposition based on smoothed L0 norm. The abstract reads:

In this paper, a fast algorithm for overcomplete sparse decomposition, called SL0, is proposed. The algorithm is essentially a method for obtaining sparse solutions of underdetermined systems of linear equations, and its applications include underdetermined Sparse Component Analysis (SCA), atomic decomposition on overcomplete dictionaries, compressed sensing, and decoding real field codes. Contrary to previous methods, which usually solve this problem by minimizing the L1 norm using Linear Programming (LP) techniques, our algorithm tries to directly minimize the L0 norm. It is experimentally shown that the proposed algorithm is about two to three orders of magnitude faster than the state-of-the-art interior-point LP solvers, while providing the same (or better) accuracy.

They also have set up a website entitled: Smoothed L0 (SL0) Algorithm for Sparse Decomposition where they introduce their algorithm and attendant code:

What is the SL0 algorithm?

SL0 (Smoothed L0) is an algorithm for finding the sparsest solutions of an underdetermined system of linear equations As=x. One of its main applications is in Compressive Sensing (CS).

SL0 is a very fast algorithm. For example, it is about 2 to 3 orders of magnitude faster than L1-magic.

SL0 tries to directly minimize the L0 norm. This is contrary to most of other existing algorithms (e.g. Basis Pursuit), which replace L0 norm by other cost functions (like L1). Note also that the equivalence of minimizing L1 and L0 is only assymptotic, and does not always hold (for a counter-example, see here).

The code for SL0.m can now be found on the authors' site here. Back in April, G. Hosei Mohimani initially forwarded me the code implementing the algorithm. It is also available here but it should be considered an older version. I have changed the local code site accordingly by pointing to this new site. The reconstruction section of the Big Picture has also been changed and points to this new site as well.