L1 Homotopy: A MATLAB Toolbox for Homotopy Algorithms in L1 Norm Minimization Problems
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
· Streaming signal recovery
· New measurements are sequentially added to the system
· The unknown signal varies over time and we get a new measurement vector
Version 2.0 (zip)
released June 2013
o A single, versatile homotopy program that can solve a variety of dynamic updating problems.
o We consider the following linear model of observations:
where is a sparse vector of interest, is the system matrix, is the measurement vector, and is the noise; we want to solve the following weighted -norm minimization program:
where is a diagonal matrix with positive weights.
o Instead of solving the optimization program from scratch, we use a vector as the starting point and solve the following homotopy program:
where and is a vector that is sign() on the support of and strictly smaller than 1 elsewhere. As changes from 0 to 1, the solution of homotopy program changes from the warm-start vector () to the desired solution. Further details in Section IV of this paper.
o Package also available at Github
· Version 1.1 (zip) released July 2012
· Version 1.0 (zip) released April 2009
· BPDN homotopy with positivity constraint
¨ Dantzig selector (PD-Pursuit)
· DS homotopy with positivity constraints
¨ Dynamic update homotopy
· Sequential measurements
One measurement at a time
· Time-varying signal
¨ Re-weighted L1
· Iterative reweighting
· Adaptive reweighting
¨ Streaming signal recovery
· Lapped orthogonal bases
· L1-regularization with linear dynamic model (L1 with Kalman filter…)
M. Salman Asif and Justin Romberg, Sparse signal recovery for streaming signals using L1-homotopy
- Streaming signal recovery from streaming measurements using lapped orthogonal basis as sparse representation
- Streaming signal recovery in the presence of a linear dynamic model on signal variations
- L1-homotopy: A versatile homotopy program that can solve a variety of dynamic updating problems
· 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.
- 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.
(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]
BPDN homotopy path
Dantzig selector homotopy path
Last updated: 06/09/2013