More Web Proxy on the site http://driver.im/

research-article

Solving Basis Pursuit: Heuristic Optimality Check and Solver Comparison

Authors:

Dirk A. Lorenz,

Marc E. Pfetsch,

Andreas M. TillmannAuthors Info & Claims

ACM Transactions on Mathematical Software (TOMS), Volume 41, Issue 2

Article No.: 8, Pages 1 - 29

https://doi.org/10.1145/2689662

Published: 04 February 2015 Publication History

Abstract

The problem of finding a minimum ℓ₁-norm solution to an underdetermined linear system is an important problem in compressed sensing, where it is also known as basis pursuit. We propose a heuristic optimality check as a general tool for ℓ₁-minimization, which often allows for early termination by “guessing” a primal-dual optimal pair based on an approximate support. Moreover, we provide an extensive numerical comparison of various state-of-the-art ℓ₁-solvers that have been proposed during the last decade, on a large test set with a variety of explicitly given matrices and several right-hand sides per matrix reflecting different levels of solution difficulty. The results, as well as improvements by the proposed heuristic optimality check, are analyzed in detail to provide an answer to the question which algorithm is the best.

References

[1]

M. Salman Asif. 2008. Primal dual pursuit—A homotopy based algorithm for the dantzig selector. Master's thesis, Georgia Institute of Technology.

[2]

Stephen Becker, Jérôme Bobin, and Emmanuel J. Candès. 2011. NESTA: A fast and accurate first-order method for sparse recovery. SIAM J. Imag Sci. 4, 1, 1--39.

Digital Library

[3]

Ernesto G. Birgin, José M. Martínez, and Marcos Raydán. 2000. Nonmonotone spectral projected gradient methods on convex sets. SIAM J. Optimiz. 10, 4, 1196--1211.

Digital Library

[4]

Stephen Boyd and Lieven Vandenberghe. 2004. Convex Optimization. Cambridge University Press, New York, NY.

Digital Library

[5]

Jian-Feng Cai, Stanley Osher, and Zuowei Shen. 2009. Linearized Bregman iterations for compressed sensing. Math. Comp. 78, 267, 1515--1536.

[6]

Paolo M. Camerini, Luigi Fratta, and Francesco Maffioli. 1975. On improving relaxation methods by modified gradient techniques. Math. Prog. Study 3, 26--34.

[7]

Emmanuel J. Candès, Justin Romberg, and Terence Tao. 2006. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Theory 52, 2, 489--509.

Digital Library

[8]

Giacomo D'Antonio and Antonio Frangioni. 2009. Convergence analysis of deflected conditional approximate subgradient methods. SIAM J. Optimiz 20, 1, 357--386.

Digital Library

[9]

Geoffrey M. Davies, Stéphane G. Mallat, and Zhifeng Zhang. 1994. Adaptive time-frequency decompositions. Opt. Eng. 33, 7, 2183--2191.

[10]

David L. Donoho. 2006. Compressed Sensing. IEEE Trans. Inf. Theory 52, 4, 1289--1306.

Digital Library

[11]

David L. Donoho and Xiaoming Huo. 2001. Uncertainty principles and ideal atomic decomposition. IEEE Trans. Inf. Theory 47, 7, 2845--2862.

Digital Library

[12]

David L. Donoho and Yaakov Tsaig. 2008. Fast solution of &ell;₁-norm minimization problems when the solution may be sparse. IEEE Trans. Inf. Theory 54, 11, 4789--4812.

Digital Library

[13]

Junbo Duan, Charles Soussen, David Brie, Jérôme Idier, and Yu-Ping Wang. 2011. A sufficient condition on monotonic increase of the number of nonzero entry in the optimizer of L1 norm penalized least-square problem. arXiv:1104.3792 {stat.ML}.

[14]

Bradley Efron, Trevor Hastie, Iain Johnstone, and Robert Tibshirani. 2004. Least angle regression. Ann. Stat. 32, 2, 407--499.

[15]

Mário A. T. Figueiredo, Robert D. Nowak, and Stephen J. Wright. 2007. Gradient projection for sparse reconstruction: Applications to compressed sensing and other inverse problems. IEEE J. Select Topics Sig. Proc. 4, 1, 586--597.

[16]

Jean-Jacques Fuchs. 2004. On sparse representations in arbitrary redundant bases. IEEE Trans. Inf. Theory 50, 6, 1341--1344.

Digital Library

[17]

Markus Grasmair, Markus Haltmeier, and Otmar Scherzer. 2011. Necessary and sufficient conditions for linear convergence of &ell;¹-regularization. Commun. Pure Appl. Math. 64, 2, 161--182.

[18]

Michael Held, Philip Wolfe, and Harlan P. Crowder. 1974. Validation of subgradient optimization. Math. Prog. 6, 62--88.

Digital Library

[19]

Victor Klee and George J. Minty. 1972. How good is the simplex algorithm&quest; In Inequalities, (III Proceedings of the 3rd Symposium Dedicated to the Memory of Theodore S. Motzkin). Academic Press, New York, NY, 159--175.

[20]

Torbjörn Larsson, Michael Patriksson, and Ann-Brith Strömberg. 1996. Conditional subgradient optimization -- Theory and applications. Europ. J. Oper. Res. 88, 2, 382--403.

[21]

Churlzu Lim and Hanif D. Sherali. 2005. Convergence and computational analyses for some variable target value and subgradient deflection methods. Computat. Opt. Appl. 34, 3, 409--428.

Digital Library

[22]

Andreas Löbel. 1997. Optimal vehicle scheduling in public transit. Ph.D. Dissertation, Technische Universität Berlin.

[23]

Dirk A. Lorenz. 2013. Constructing test instances for basis pursuit denoising. IEEE Trans. Sign. Process. 61, 5, 2010--2014.

Digital Library

[24]

D. A. Lorenz, M. E. Pfetsch, and A. M. Tillmann. 2014. An infeasible-point subgradient method using adaptive approximate projections. Computat. Optimiz. Appl. 57, 2, 271--306.

Digital Library

[25]

Dirk A. Lorenz, Stefan Schiffler, and Dennis Trede. 2011. Beyond convergence rates: Exact inversion with Tikhonov regularization with sparsity constraints. Inve. Prob. 27, 085009.

[26]

J. Mairal and B. Yu. 2012. Complexity analysis of the Lasso regularization path. In Proceedings of the 29th International Conference on Machine Learning (ICML). J. Langford and J. Pineau (Eds.), Omnipress, Madison, WI, 353--360.

[27]

Dmitry M. Malioutov, Müjdat Çetin, and Alan S. Willsky. 2005. Homotopy continuation for sparse signal representation. In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP'05). Vol. 5, IEEE, New York, NY, 733--736.

[28]

Arkadi S. Nemirovskiy and Boris T. Polyak. 1984. Iterative methods for solving linear ill-posed problems under precise information. I. Izvestiya Akademii Nauk SSSR. Tekhnicheskaya Kibernetika 2, 13--25, 203.

[29]

Yurii Nesterov. 2005. Smooth minimization of non-smooth functions. Math. Prog. 103, 1, 127--152.

Digital Library

[30]

Michael R. Osbourne, Brett Presnell, and Berwin A. Turlach. 2000. A new approach to variable selection in least squares problems. IMA J. Numer. Anal. 20, 3, 389--402.

[31]

Y. C. Pati, R. Rezaiifar, and P. S. Krishnaprasad. 1993. Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition. In Proceedings of the 27th Annual Asilomar Conference on Signals, Systems and Computers. Vol. 1, CA, 40--44.

[32]

Andrzej Ruszczyński. 2006. Nonlinear Optimization. Princeton University Press, Princeton, NJ.

Digital Library

[33]

Naum Z. Shor. 1985. Minimization Methods for Non-Differentiable Functions. Springer, New York, NY.

Digital Library

[34]

Joel A. Tropp. 2004. Greed is good: Algorithmic results for sparse approximation. IEEE Trans. Inf. Theory. 50, 10, 2231--2242.

Digital Library

[35]

Joel A. Tropp. 2006. Just relax: Convex programming methods for identifying sparse signals in noise. IEEE Trans. Inf. Theory 52, 3 (March 2006), 1030--1051.

Digital Library

[36]

Joel A. Tropp and Anna C. Gilbert. 2007. Signal recovery from random measurements via orthogonal matching pursuit. IEEE Trans. Inf. Theory 53, 12, 4655--5666.

Digital Library

[37]

Ewout van den Berg and Michael P. Friedlander. 2008. Probing the Pareto frontier for basis pursuit solutions. SIAM J. Sci. Comput. 31, 2, 890--912.

Digital Library

[38]

Yilun Wang and Wotao Yin. 2010. Sparse signal reconstruction via iterative support detection. SIAM J. Imag. Sci. 3, 3, 462--491.

Digital Library

[39]

Zaiwen Wen, Wotao Yin, Donald Goldfarb, and Yin Zhang. 2010. A fast algorithm for sparse reconstruction based on shrinkage, subspace optimization and continuation. SIAM J. Sci. Comput. 32, 4, 1832--1857.

Digital Library

[40]

Roland Wunderling. 1996. Paralleler und objektorientierter Simplex-Algorithmus. Ph.D. Dissertation, Technische Universität Berlin. In German.

[41]

Allen Y. Yang, Zihan Zhou, Arvind Ganesh, S. Shankar Sastry, and Yi Ma. 2010. A review of fast &ell;₁-minimization algorithms for robust face recognition. arXiv:1007.3753 {cs.CV}.

[42]

Junfeng Yang and Yin Zhang. 2011. Alternating direction algorithms for &ell;₁-problems in compressive sensing. SIAM J. Sci. Comput. 33, 1, 250--278.

Digital Library

[43]

Wotao Yin. 2010. Analysis and generalizations of the linearized Bregman model. SIAM J. Imag. Sci. 3, 4, 856--877.

Digital Library

[44]

Wotao Yin, Stanley J. Osher, Donald Goldfarb, and Jérôme Darbon. 2008. Bregman iterative algorithms for &ell;¹-minimization with applications to compressed sensing. SIAM J. Imag Sci. 1, 1, 143--168.

Digital Library

Cited By

Tillmann ABienstock DLodi ASchwartz A(2024)Cardinality Minimization, Constraints, and Regularization: A SurveySIAM Review10.1137/21M142770X66:3(403-477)Online publication date: 8-Aug-2024
https://doi.org/10.1137/21M142770X
Fan YPesavento M(2024)Tail-STELA for Fast Signal Recovery via Basis Pursuit2024 IEEE 13rd Sensor Array and Multichannel Signal Processing Workshop (SAM)10.1109/SAM60225.2024.10636404(1-5)Online publication date: 8-Jul-2024
https://doi.org/10.1109/SAM60225.2024.10636404
Tausiesakul BAsavaskulkiet K(2023)Soft Thresholding Using Moore–Penrose InverseIEEE Transactions on Instrumentation and Measurement10.1109/TIM.2023.328950672(1-18)Online publication date: 2023
https://doi.org/10.1109/TIM.2023.3289506
Show More Cited By

Index Terms

Solving Basis Pursuit: Heuristic Optimality Check and Solver Comparison
1. Mathematics of computing
  1. Mathematical software

Recommendations

Uniform Uncertainty Principle and Signal Recovery via Regularized Orthogonal Matching Pursuit

This paper seeks to bridge the two major algorithmic approaches to sparse signal recovery from an incomplete set of linear measurements--L1-minimization methods and iterative methods (Matching Pursuits). We find a simple regularized version of ...
Block-sparse signals: uncertainty relations and efficient recovery

We consider efficient methods for the recovery of block-sparse signals--i.e., sparse signals that have nonzero entries occurring in clusters--from an underdetermined system of linear equations. An uncertainty relation for block-sparse signals is derived,...
Stability and Instance Optimality for Gaussian Measurements in Compressed Sensing

In compressed sensing, we seek to gain information about a vector xźźN from dźN nonadaptive linear measurements. Candes, Donoho, Tao et al. (see, e.g., Candes, Proc. Intl. Congress Math., Madrid, 2006; Candes et al., Commun. Pure Appl. Math. 59:1207---...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Mathematical Software

ACM Transactions on Mathematical Software Volume 41, Issue 2

January 2015

173 pages

ISSN:0098-3500

EISSN:1557-7295

DOI:10.1145/2732672

Editor:
Michael A. Heroux
Sandia National Laboratories, USA

Issue’s Table of Contents

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 February 2015

Accepted: 01 March 2014

Revised: 01 November 2013

Received: 01 May 2013

Published in TOMS Volume 41, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Deutsche Forschungsgemeinschaft

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
341
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Tillmann ABienstock DLodi ASchwartz A(2024)Cardinality Minimization, Constraints, and Regularization: A SurveySIAM Review10.1137/21M142770X66:3(403-477)Online publication date: 8-Aug-2024
https://doi.org/10.1137/21M142770X
Fan YPesavento M(2024)Tail-STELA for Fast Signal Recovery via Basis Pursuit2024 IEEE 13rd Sensor Array and Multichannel Signal Processing Workshop (SAM)10.1109/SAM60225.2024.10636404(1-5)Online publication date: 8-Jul-2024
https://doi.org/10.1109/SAM60225.2024.10636404
Tausiesakul BAsavaskulkiet K(2023)Soft Thresholding Using Moore–Penrose InverseIEEE Transactions on Instrumentation and Measurement10.1109/TIM.2023.328950672(1-18)Online publication date: 2023
https://doi.org/10.1109/TIM.2023.3289506
Bilbao IFanari LIradier EAngueira PMontalban J(2023)Sparse Vector Coding for Short-Packet Transmission on Industrial Communications: Reference Architecture and Design ChallengesIEEE Open Journal of the Industrial Electronics Society10.1109/OJIES.2022.32301424(1-13)Online publication date: 2023
https://doi.org/10.1109/OJIES.2022.3230142
Dessole MDell'Orto MMarcuzzi F(2023)The Lawson‐Hanson algorithm with deviation maximization: Finite convergence and sparse recoveryNumerical Linear Algebra with Applications10.1002/nla.249030:5Online publication date: 13-Jan-2023
https://doi.org/10.1002/nla.2490
Tausiesakul B(2022)Soft Homotopy via Moore-Penrose Inverse2022 7th International Conference on Smart and Sustainable Technologies (SpliTech)10.23919/SpliTech55088.2022.9854267(1-5)Online publication date: 5-Jul-2022
https://doi.org/10.23919/SpliTech55088.2022.9854267
Tausiesakul B(2022)Basis Pursuit and Linear Programming Equivalence: A Performance Comparison in Sparse Signal Recovery2022 7th International Conference on Smart and Sustainable Technologies (SpliTech)10.23919/SpliTech55088.2022.9854240(1-6)Online publication date: 5-Jul-2022
https://doi.org/10.23919/SpliTech55088.2022.9854240
Tausiesakul B(2022)Soft Homotopy through Moore-Penrose Inverse2022 IEEE 9th International Conference on Computational Intelligence and Virtual Environments for Measurement Systems and Applications (CIVEMSA)10.1109/CIVEMSA53371.2022.9853651(1-5)Online publication date: 15-Jun-2022
https://doi.org/10.1109/CIVEMSA53371.2022.9853651
Toyoda MTanaka M(2022)Efficient iterative method for SOAV minimization problem with linear equality and box constraints and its linear convergenceJournal of the Franklin Institute10.1016/j.jfranklin.2022.01.014359:5(2206-2228)Online publication date: Mar-2022
https://doi.org/10.1016/j.jfranklin.2022.01.014
Facca EBenzi M(2021)Fast Iterative Solution of the Optimal Transport Problem on GraphsSIAM Journal on Scientific Computing10.1137/20M137015X43:3(A2295-A2319)Online publication date: 22-Jun-2021
https://doi.org/10.1137/20M137015X
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents