Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

A time continuation based fast approximate algorithm for compressed sensing related optimization


Authors: Farzin Barekat and Stanley Osher
Journal: Math. Comp. 84 (2015), 2791-2822
MSC (2010): Primary 49M29, 65K10, 90C25; Secondary 49L99
DOI: https://doi.org/10.1090/mcom/2972
Published electronically: May 28, 2015
MathSciNet review: 3378848
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper we introduce a fast approximate algorithm to optimize an augmented version of the Basis Pursuit problem and subsequently find the solution to the compressed sensing problem. Our methodology is to first solve the Lagrangian dual formulation of the problem and then use the result to find an approximate solution to the primal problem. Although we emphasize that our algorithm finds an approximate solution, numerical experiments show that our algorithm perfectly recovers the solution when the solution is relatively sparse with respect to the number of measurements. In these scenarios, the recovery is extremely fast compared to other available methods. Numerical experiments also demonstrate that the algorithm exhibits a sharp phase transition in success rate of recovery of the solution to compressed sensing problems as sparsity of solution varies. The algorithm proposed here is parameter free (except a tolerance parameter due to numerical machine precision), and very easy to implement.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 49M29, 65K10, 90C25, 49L99

Retrieve articles in all journals with MSC (2010): 49M29, 65K10, 90C25, 49L99


Additional Information

Farzin Barekat
Affiliation: Mathematics Department, University of California at Los Angeles, Los Angeles, California 90095-1555
Email: fbarekat@math.ucla.edu

Stanley Osher
Affiliation: Mathematics Department, University of California at Los Angeles, Los Angeles, California 90095-1555
Email: sjo@math.ucla.edu

DOI: https://doi.org/10.1090/mcom/2972
Keywords: Augmented $\ell^1$ minimization, homotopy methods, compressed sensing, exact regularization property
Received by editor(s): February 1, 2014
Published electronically: May 28, 2015
Additional Notes: This research was supported by DOE DE-FG02-05ER25710:005, ONR N00014-11-1-0749, and ONR N00014-11-1-7-11.
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society