|
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 ·
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
where o
Instead of solving the optimization
program from scratch, we use a vector
where 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 (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 ¨
Streaming signal recovery ·
Lapped orthogonal bases ·
L1-regularization with linear
dynamic model (L1 with Kalman filter…) Related
papers: ·
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. -
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 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] L1 Homotopy ©
2013 M. Salman Asif and Justin Romberg |
|
|
BPDN
homotopy path |
Dantzig
selector homotopy path |
|
Last updated:
06/09/2013 |
|
