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

Barekat, Farzin; Osher, Stanley

doi:10.1090/mcom/2972

A time continuation based fast approximate algorithm for compressed sensing related optimization
HTML articles powered by AMS MathViewer

by Farzin Barekat and Stanley Osher;

Math. Comp. 84 (2015), 2791-2822

DOI: https://doi.org/10.1090/mcom/2972

Published electronically: May 28, 2015

PDF | Request permission

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

Jonathan Barzilai and Jonathan M. Borwein, Two-point step size gradient methods, IMA J. Numer. Anal. 8 (1988), no. 1, 141–148. MR 967848, DOI 10.1093/imanum/8.1.141
Amir Beck and Marc Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci. 2 (2009), no. 1, 183–202. MR 2486527, DOI 10.1137/080716542
Stephen R. Becker, Emmanuel J. Candès, and Michael C. Grant, Templates for convex cone problems with applications to sparse signal recovery, Math. Program. Comput. 3 (2011), no. 3, 165–218. MR 2833262, DOI 10.1007/s12532-011-0029-5
Martin Burger, Michael Möller, Martin Benning, and Stanley Osher, An adaptive inverse scale space method for compressed sensing, Math. Comp. 82 (2013), no. 281, 269–299. MR 2983025, DOI 10.1090/S0025-5718-2012-02599-3
Emmanuel J. Candes and Terence Tao, Decoding by linear programming, IEEE Trans. Inform. Theory 51 (2005), no. 12, 4203–4215. MR 2243152, DOI 10.1109/TIT.2005.858979
S. Chen and D. Donoho, Basis Pursuit, Conference on Signals, Systems and Computers., v1, (1994), pp. 41–44.
Scott Shaobing Chen, David L. Donoho, and Michael A. Saunders, Atomic decomposition by basis pursuit, SIAM Rev. 43 (2001), no. 1, 129–159. Reprinted from SIAM J. Sci. Comput. 20 (1998), no. 1, 33–61 (electronic) [ MR1639094 (99h:94013)]. MR 1854649, DOI 10.1137/S003614450037906X
J. Darbon, On convex finite-dimensional variational methods in imaging sciences and Hamilton-Jacobi equations,UCLA CAM report 13-59, (2013).
J. Darbon and S. Osher, Initial Value Problems for Hamilton-Jacobi Equations and Sparsity for Linear Systems via $\ell ^1$ Related Optimization, (2013), preprint.
Bradley Efron, Trevor Hastie, Iain Johnstone, and Robert Tibshirani, Least angle regression, Ann. Statist. 32 (2004), no. 2, 407–499. With discussion, and a rejoinder by the authors. MR 2060166, DOI 10.1214/009053604000000067
Michael P. Friedlander and Paul Tseng, Exact regularization of convex programs, SIAM J. Optim. 18 (2007), no. 4, 1326–1350. MR 2373304, DOI 10.1137/060675320
Elaine T. Hale, Wotao Yin, and Yin Zhang, Fixed-point continuation for $l_1$-minimization: methodology and convergence, SIAM J. Optim. 19 (2008), no. 3, 1107–1130. MR 2460734, DOI 10.1137/070698920
Ming-Jun Lai and Wotao Yin, Augmented $\ell _1$ and nuclear-norm models with a globally linearly convergent algorithm, SIAM J. Imaging Sci. 6 (2013), no. 2, 1059–1091. MR 3062582, DOI 10.1137/120863290
S. G. Mallat, Z. Zhang, Matching pursuits with time-frequency dictionaries, IEEE Transactions on Signal Processing, Issue 12, (1993), pp. 3397–3415.
Yu. E. Nesterov, A method for solving the convex programming problem with convergence rate $O(1/k^{2})$, Dokl. Akad. Nauk SSSR 269 (1983), no. 3, 543–547 (Russian). MR 701288
Y. C. Pati, R. Rezaiifar, P. S. Krishnaprasad, Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition, Proceedings of the 27th Annual Asilomar Conference on Signals, Systems, and Computers, (1993), pp. 40–44.
Frank Schöpfer, Exact regularization of polyhedral norms, SIAM J. Optim. 22 (2012), no. 4, 1206–1223. MR 3023770, DOI 10.1137/11085236X
Robert Tibshirani, Regression shrinkage and selection via the lasso, J. Roy. Statist. Soc. Ser. B 58 (1996), no. 1, 267–288. MR 1379242
Joel A. Tropp and Anna C. Gilbert, Signal recovery from random measurements via orthogonal matching pursuit, IEEE Trans. Inform. Theory 53 (2007), no. 12, 4655–4666. MR 2446929, DOI 10.1109/TIT.2007.909108
David L. Donoho and Yaakov Tsaig, Fast solution of $l_1$-norm minimization problems when the solution may be sparse, IEEE Trans. Inform. Theory 54 (2008), no. 11, 4789–4812. MR 2589865, DOI 10.1109/TIT.2008.929958
Layne T. Watson, Theory of globally convergent probability-one homotopies for nonlinear programming, SIAM J. Optim. 11 (2000/01), no. 3, 761–780. MR 1814041, DOI 10.1137/S105262349936121X
Layne T. Watson and Raphael T. Haftka, Modern homotopy methods in optimization, Comput. Methods Appl. Mech. Engrg. 74 (1989), no. 3, 289–305. MR 1020627, DOI 10.1016/0045-7825(89)90053-4
Yi Yang, Michael Möller, and Stanley Osher, A dual split Bregman method for fast $\ell ^1$ minimization, Math. Comp. 82 (2013), no. 284, 2061–2085. MR 3073192, DOI 10.1090/S0025-5718-2013-02700-7
Wotao Yin, Analysis and generalizations of the linearized Bregman model, SIAM J. Imaging Sci. 3 (2010), no. 4, 856–877. MR 2735964, DOI 10.1137/090760350
M. R. Osborne, Brett Presnell, and B. A. Turlach, A new approach to variable selection in least squares problems, IMA J. Numer. Anal. 20 (2000), no. 3, 389–403. MR 1773265, DOI 10.1093/imanum/20.3.389