Fast l1 Minimization Algorithms: Homotopy and Augmented Lagrangian Method (ALM)

© Copyright Notice: It is important that you read and understand the copyright of the following software packages as specified in the individual items. The copyright varies with each package due to its author(s). The packages should NOT be used for any commercial purposes without direct consent of their author(s).

This project is partially supported by NSF TRUST Center at UC Berkeley, ARO MURI W911NF-06-1-0076, ARL MAST-CTA W911NF-08-2-0004.

Publications

Allen Yang, Arvind Ganesh, Zihan Zhou, Shankar Sastry, and Yi Ma. Fast L1-Minimization Algorithms for Robust Face Recognition. (preprint)
Allen Yang, Arvind Ganesh, Shankar Sastry, and Yi Ma. Fast l1-Minimization Algorithms and An Application in Robust Face Recognition: A Review. ICIP 2010.
Victor Shia, Allen Yang, Shankar Sastry, Andrew Wagner, and Yi Ma. Fast l1-Minimization and Parallelization for Face Recognition. Asilomar 2011.

MATLAB Benchmark Scripts

L-1 Benchmark Package: http://people.eecs.berkeley.edu/~yang/software/l1benchmark/l1benchmark.zip

The package contains a consolidated implementation of nine l-1 minimization algorithms in MATLAB. Each function uses a consistent set of parameters (e.g., stopping criterion and tolerance) to interface with our benchmark scripts.

Orthogonal Matching Pursuit: SolveOMP.m
Primal-Dual Interior-Point Method: SolvePDIPA.m
Gradient Projection: SolveL1LS.m
Homotopy: SolveHomotopy.m
Iterative Thresholding: SolveSpaRSA.m
Proximal Gradient: SolveFISTA.m
TFOCS: SolveTFOCS.m
SesopPCD: SolveSesopPCD.m
Primal Augmented Lagrange Multiplier: SolvePALM.m
Dual Augmented Lagrange Multiplier: SolveDALM.m; SolveDALM_fast.m

The package also contains a script to generate the synthetic data shown in the paper [1].

Single-Core l-1 Minimization Library in C

Homotopy and ALM algorithms implemented in C with MATLAB wrapper: http://people.eecs.berkeley.edu/~yang/software/l1benchmark/L1-Homotopy-ALM.zip

Fixed-Point l-1 Minimization for Mobile Platforms

Fixed-point Homotopy algorithm implemented in Java: http://people.eecs.berkeley.edu/~yang/software/l1benchmark/fixed_point_homotopy_java.zip

Many-Core l-1 Minimization Library in C/CUDA

Coming soon ...

Other Public l-1 Minimization Libraries

SparseLab: http://sparselab.stanford.edu/

Orthogonal Matching Pursuit (OMP): SolveOMP
Primal-Dual Basis Pursuit (BP): SolveBP.m
Lasso : SolveLasso.m
Polytope Faces Pursuite (PFP): SolvePFP.m

l1magic: http://www.acm.caltech.edu/l1magic/

Primal-Dual Basis Pursuit (BP): l1eq_pd.m

L1LS: http://www.stanford.edu/boyd/l1_ls/

Truncated Newton Interior-Point Method: l1_ls.m

GPSR: http://www.lx.it.pt/~mtf/GPSR/

Gradient Projection Sparse Representation: GPSR_BB

l1-Homotopy: http://users.ece.gatech.edu/~sasif/homotopy/

Homotopy Method: BPDN_homotopy_function.m

SpaRSA: http://www.lx.it.pt/~mtf/SpaRSA/

Iterative Shrinkage-Thresholding Algorithm: SpaRSA.m

FISTA: http://www.eecs.berkeley.edu/~yang/software/l1benchmark/

Fast IST Algorithm: SolveFISTA.m

FISTA for wavelet-based denoising:

http://iew3.technion.ac.il/~becka/papers/wavelet_FISTA.zip

NESTA: http://www.acm.caltech.edu/~nesta/

Nesterov's Algorithm: NESTA.m

YALL1: http://www.caam.rice.edu/~optimization/L1/YALL1/

Alternating Direction Method: yall1.m

Bregman Iterative Regularization: http://www.caam.rice.edu/~optimization/L1/bregman/

Fixed-Point Continuation and Active Set: FPC_AS.m

Approximate Message Passing: http://www.ukamilov.com/
Templates for convex cone solvers (TFOCS): http://tfocs.stanford.edu/download/

Publications Allen Yang, Arvind Ganesh, Zihan Zhou, Shankar Sastry, and Yi Ma. Fast L1-Minimization Algorithms for Robust Face Recognition. (preprint) Allen Yang, Arvind Ganesh, Shankar Sastry, and Yi Ma. Fast l1-Minimization Algorithms and An Application in Robust Face Recognition: A Review. ICIP 2010. Victor Shia, Allen Yang, Shankar Sastry, Andrew Wagner, and Yi Ma. Fast l1-Minimization and Parallelization for Face Recognition. Asilomar 2011.
MATLAB Benchmark Scripts L-1 Benchmark Package: http://people.eecs.berkeley.edu/~yang/software/l1benchmark/l1benchmark.zip The package contains a consolidated implementation of nine l-1 minimization algorithms in MATLAB. Each function uses a consistent set of parameters (e.g., stopping criterion and tolerance) to interface with our benchmark scripts. Orthogonal Matching Pursuit: SolveOMP.m Primal-Dual Interior-Point Method: SolvePDIPA.m Gradient Projection: SolveL1LS.m Homotopy: SolveHomotopy.m Iterative Thresholding: SolveSpaRSA.m Proximal Gradient: SolveFISTA.m TFOCS: SolveTFOCS.m SesopPCD: SolveSesopPCD.m Primal Augmented Lagrange Multiplier: SolvePALM.m Dual Augmented Lagrange Multiplier: SolveDALM.m; SolveDALM_fast.m The package also contains a script to generate the synthetic data shown in the paper [1].

Single-Core l-1 Minimization Library in C Homotopy and ALM algorithms implemented in C with MATLAB wrapper: http://people.eecs.berkeley.edu/~yang/software/l1benchmark/L1-Homotopy-ALM.zip

Fixed-Point l-1 Minimization for Mobile Platforms Fixed-point Homotopy algorithm implemented in Java: http://people.eecs.berkeley.edu/~yang/software/l1benchmark/fixed_point_homotopy_java.zip

Many-Core l-1 Minimization Library in C/CUDA Coming soon ...

Other Public l-1 Minimization Libraries SparseLab: http://sparselab.stanford.edu/ Orthogonal Matching Pursuit (OMP): SolveOMP Primal-Dual Basis Pursuit (BP): SolveBP.m Lasso : SolveLasso.m Polytope Faces Pursuite (PFP): SolvePFP.m l1magic: http://www.acm.caltech.edu/l1magic/ Primal-Dual Basis Pursuit (BP): l1eq_pd.m L1LS: http://www.stanford.edu/boyd/l1_ls/ Truncated Newton Interior-Point Method: l1_ls.m GPSR: http://www.lx.it.pt/~mtf/GPSR/ Gradient Projection Sparse Representation: GPSR_BB l1-Homotopy: http://users.ece.gatech.edu/~sasif/homotopy/ Homotopy Method: BPDN_homotopy_function.m SpaRSA: http://www.lx.it.pt/~mtf/SpaRSA/ Iterative Shrinkage-Thresholding Algorithm: SpaRSA.m FISTA: http://www.eecs.berkeley.edu/~yang/software/l1benchmark/ Fast IST Algorithm: SolveFISTA.m FISTA for wavelet-based denoising: http://iew3.technion.ac.il/~becka/papers/wavelet_FISTA.zip NESTA: http://www.acm.caltech.edu/~nesta/ Nesterov's Algorithm: NESTA.m YALL1: http://www.caam.rice.edu/~optimization/L1/YALL1/ Alternating Direction Method: yall1.m Bregman Iterative Regularization: http://www.caam.rice.edu/~optimization/L1/bregman/ Fixed-Point Continuation and Active Set: FPC_AS.m Approximate Message Passing: http://www.ukamilov.com/ Templates for convex cone solvers (TFOCS): http://tfocs.stanford.edu/download/