L1 Homotopy: A MATLAB Toolbox for Homotopy Algorithms in L1 Norm Minimization Problems -implementation -

Salman Asif sent me the following:

Dear Igor,

Thanks for mentioning our paper on your blog. You announced it before I had put it on my website, amazing!

I have uploaded the paper on my website and the code related to iterative and adaptive reweighting in the homotopy toolbox.

Paper can be found @ http://users.ece.gatech.edu/~sasif/Research/AR_rwtL1_2012.pdf

and code @ http://users.ece.gatech.edu/~sasif/homotopy/

Thanks,

-Salman

Thanks Salman ! The page for the implementation is L1 Homotopy: A MATLAB Toolbox for Homotopy Algorithms in L1 Norm Minimization Problems

The paper is: Fast and Accurate Algorithms for Re-Weighted l_1-Norm Minimization by M. Salman Asif and Justin Romberg. The abstract reads:

To recover a sparse signal from an underdetermined system, we often solve a constrained `1-norm minimization problem. In many cases, the signal sparsity and the recovery performance can be further improved by replacing the `1 norm with a “weighted” `1 norm. Without any prior information about nonzero elements of the signal, the procedure for selecting weights is iterative in nature. Common approaches update the weights at every iteration using the solution of a weighted `1 problem from the previous iteration.

In this paper, we present two homotopy-based algorithms that efficiently solve reweighted `1 problems. First, we present an algorithm that quickly updates the solution of a weighted `1 problem as the weights change. Since the solution changes only slightly with small changes in the weights, we develop a homotopy algorithm that replaces the old weights with the new ones in a small number of computationally inexpensive steps. Second, we propose an algorithm that solves a weighted `1 problem by adaptively selecting the weights while estimating the signal. This algorithm integrates the reweighting into every step along the homotopy path by changing the weights according to the changes in the solution and its support, allowing us to achieve a high quality signal reconstruction by solving a single homotopy problem.

We compare the performance of both algorithms, in terms of reconstruction accuracy and computational complexity, against state-of-the-art solvers and show that our methods have smaller computational cost.

In addition, we will show that the adaptive selection of the weights inside the homotopy often yields reconstructions of higher quality.

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.