Equivalence of Linear Programming and Basis Pursuit

Corresponding Author

Andreas M. Tillmann

[email protected]

TU Darmstadt, Research Group Optimization, Dolivostr. 15, D-64293 Darmstadt, Germany

phone +49 6151 1670868. During GAMM 2015, the author was with the Institute for Mathematical Optimization at TU Braunschweig, Pockelsstr. 14, D-38106 Braunschweig, Germany (on leave from TU Darmstadt).Search for more papers by this author

Andreas M. Tillmann,

Corresponding Author

Andreas M. Tillmann

[email protected]

TU Darmstadt, Research Group Optimization, Dolivostr. 15, D-64293 Darmstadt, Germany

First published: 21 October 2015

https://doi.org/10.1002/pamm.201510351

Citations: 8

About

PDF

Tools

Share a link

Email
Wechat
Bluesky

Abstract

In this note, we show that linear programming and the prominent Basis Pursuit problem (i.e., minimizing the ℓ₁-norm of a vector x subject to an underdetermined linear equation system Ax = b) are theoretically equivalent, and briefly discuss possible ramifications regarding computational complexity and practical applicability. (© 2015 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)

References

[1] D. A. Lorenz, M. E. Pfetsch, and A. M. Tillmann, ACM Transactions on Mathematical Software 41(2), Art. No. 8 (2015).
Google Scholar
[2] A. M. Tillmann, Computational Aspects of Compressed Sensing, Doctoral dissertation, TU Darmstadt, Germany, 2013.
Google Scholar
[3] R. H. Bartels, A. R. Conn, and J. W. Sinclair, SIAM Journal of Numerical Analysis 15(2), 224–241 (1978).
Google Scholar
[4] E. J. Candès and T. Tao, IEEE Transactions on Information Theory 51(12), 4203–4215 (2005).
Google Scholar
[5] M. Grötschel, L. Lovász, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, 2nd edition, Algorithms and Combinatorics, Vol. 2 (Springer, Heidelberg, Germany, 1993).
Google Scholar
[6] C. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity (Prentice-Hall, Upper Saddle River, NJ, USA, 1982).
Google Scholar
[7] A. Schrijver, Theory of Linear and Integer Programming, Wiley-Interscience Series in Discrete Mathematics and Optimization (John Wiley & Sons, New York, NY, USA, 1986).
Google Scholar
[8] R. E. Bixby and M. J. Saltzman, Operations Research Letters 15(4), 169–178 (1994).
Google Scholar
[9] D. L. Donoho and Y. Tsaig, IEEE Transactions on Information Theory 54(11), 4789–4812 (2008).
Google Scholar

Citing Literature

Volume15, Issue1

Special Issue:86th Annual Meeting of the International Association of Applied Mathematics and Mechanics (GAMM), Lecce 2015; Editors: G. Zavarise, P. Cinnella and M. Campiti

October 2015

Pages 735-738

Equivalence of Linear Programming and Basis Pursuit

Abstract

References

Citing Literature

References

Information

About Wiley Online Library

Help & Support

Opportunities

Connect with Wiley

Equivalence of Linear Programming and Basis Pursuit

Abstract

References

Citing Literature

References

Related

Information