L1 Homotopy: A MATLAB Toolbox for Homotopy Algorithms in L1 Norm Minimization Problems
Introduction: This package is a collection of MATLAB routines for solving some L1 norm minimization problems using homotopy techniques. These problems are usually encountered in the recovery of sparse signals from linear incoherent measurements. This package contains scripts for solving the following optimization problems: · Basis pursuit denoising (BPDN) / LASSO · Dantzig selector · L1 decoding, robust L1 decoding · Re-weighted L1-norm (iterative and adaptive reweighting) In addition to solving these problems for any given set of parameters, we have some dynamic algorithms to update their solution when · New measurements are sequentially added to the system · The unknown signal varies over time and we get a new measurement vector Download: Homotopy package · Version 1.1 (zip) released July 2012 · Version 1.0 (zip) released April 2009 ¨ BPDN/LASSO · BPDN homotopy with positivity constraint ¨ Dantzig selector (PD-Pursuit) · DS homotopy with positivity constraints ¨ Dynamic update homotopy · Sequential measurements One measurement at a time Multiple measurements · Time-varying signal ¨ Re-weighted L1 · Iterative reweighting · Adaptive reweighting Related papers: · M. Salman Asif and Justin Romberg, Fast and accurate algorithms for re-weighted L1-norm minimization, submitted to IEEE Transactions on Signal Processing, July 2012. - Results presented in the paper: blocks and heavisine at 40 dB SNR (While cleaning up the code for release, I realized that the results should have been blocks, heavisine. The difference is because of the way I averaged the results for 100 experiments. Instead of computing , I computed where mean is over the results of 100 experiments and normalized error norm is the ratio of the error norm to the signal norm.) - For largescale examples (grayscale images) use SpaRSA_adpW.m, which is a simple modification of SpaRSA code [link] where we update the definition of psi (weights) at every continuation step. Full images for the results presented in the paper: barbara, boats, and cameraman. (Top row: reconstructed images. Bottom row: difference between original and reconstructed images, amplified by 10 times.) - Additional results (zip) include o Experiments with T-sparse Gaussian (randn) and +/-1 Spikes at 30 and 40 dB SNR. (‘randn’ signals when reconstructed with one iteration of ‘adaptive reweighting’ (ARW-H) alone do not match the quality of those reconstructed with five iterations of ‘iterative reweighting’ (IRW-H) (see results for sTyperandn_xx_adpWonly1). However, one or two iterations of IRW-H after solving ARW-H improve the results at a negligible additional cost (see the results for sTyperandn_xx_adpWonly0). o Additional experiments for Blocks and HeaviSine signals at 30 dB SNR. o Grayscale images reconstructed via adaptive reweighting inside SpaRSA. · M. Salman Asif and Justin Romberg, Dynamic updating for L1 minimization, IEEE Journal of selected topics in signal processing, April 2010. Other sparse recovery softwares and links: · l1_magic [link] · CVX [link] · WaveLab [link] · GPSR [link] · FPC_AS [link] · SpaRSA [link] · YALL1 [link] · NESTA [link] · SPGL1 [link] License: L1 Homotopy © 2009, 2012 M. Salman Asif and Justin Romberg This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. <http://www.gnu.org/licenses/>.
BPDN homotopy path	Dantzig selector homotopy path
Last updated: 07/31/2012