Fast l-1 Minimization Algorithms: Homotopy and Augmented Lagrangian Method
-- Implementation from Fixed-Point MPUs to Many-Core CPUs/GPUs

Allen Y. Yang, Arvind Ganesh, Zihan Zhou,
Andrew Wagner, Victor Shia, Shankar Sastry, and Yi Ma

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.


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

MATLAB Benchmark Scripts

 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.
  1. Orthogonal Matching Pursuit: SolveOMP.m
  2. Primal-Dual Interior-Point Method: SolvePDIPA.m
  3. Gradient Projection: SolveL1LS.m
  4. Homotopy: SolveHomotopy.m
  5. Iterative Thresholding: SolveSpaRSA.m
  6. Proximal Gradient: SolveFISTA.m
  7. TFOCS: SolveTFOCS.m
  8. SesopPCD: SolveSesopPCD.m
  9. Primal Augmented Lagrange Multiplier: SolvePALM.m
  10. 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

Fixed-Point l-1 Minimization for Mobile Platforms

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

Other Public l-1 Minimization Libraries

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

[Return to Home]