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  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   Index of files in this package

o   Dependency graph

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,
submitted to IEEE Transactions on Signal Processing, June 2013. [supplementary results]

-         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.

(‘randnsignals  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

 

 

 

Description: Description: Description: Description: Description: Description: image001

         

BPDN homotopy path

 

    Description: Description: Description: Description: Description: Description: image003

 

Dantzig selector homotopy path

 

Last updated: 06/09/2013