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 ·
Reweighted L1norm (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 Download:
Homotopy
package ·
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 warmstart vector () to
the desired solution. Further details in Section IV of this paper. o
Index of files
in this package o
Package also available at Github ·
Version 1.1 (zip)
released July 2012 ·
Version 1.0 (zip)
released April 2009 ¨
BPDN/LASSO ·
BPDN homotopy
with positivity constraint ¨
Dantzig
selector (PDPursuit) ·
DS homotopy
with positivity constraints ¨
Dynamic update homotopy ·
Sequential measurements
One measurement at a time
Multiple measurements ·
Timevarying signal ¨
Reweighted L1 ·
Iterative reweighting ·
Adaptive reweighting ¨
Streaming signal recovery ·
Lapped orthogonal bases ·
L1regularization with linear
dynamic model (L1 with Kalman filter…) Related
papers: ·
M. Salman Asif and Justin Romberg, Sparse signal recovery for streaming signals using L1homotopy, 
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 
L1homotopy: A
versatile homotopy program that can solve a variety
of dynamic updating problems ·
M. Salman
Asif and Justin Romberg, Fast and accurate algorithms for reweighted
L1norm minimization, submitted to
IEEE Transactions on Signal Processing, July 2012. 
Results presented in the paper: blocks
and heavisine at 40 dB SNR 
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 Tsparse Gaussian (randn) and +/1 Spikes at 30 and 40 dB SNR. (‘randn’ signals when reconstructed with one
iteration of ‘adaptive reweighting’ (ARWH) alone do not match the quality of
those reconstructed with five iterations of ‘iterative reweighting’ (IRWH)
(see results for sTyperandn_xx_adpWonly1). However, one or two iterations of
IRWH after solving ARWH 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] L1 Homotopy ©
2013 M. Salman Asif and Justin Romberg 

BPDN
homotopy path 
Dantzig
selector homotopy path 
Last updated:
06/09/2013 
