Basis pursuit
![]() | This article includes a list of references, related reading or external links, but its sources remain unclear because it lacks inline citations. (April 2020) |
Basis pursuit is the mathematical optimization problem of the form
where x is a N × 1 solution vector (signal), y is a M × 1 vector of observations (measurements), A is a M × N transform matrix (usually measurement matrix) and M < N.
It is usually applied in cases where there is an underdetermined system of linear equations y = Ax that must be exactly satisfied, and the sparsest solution in the L1 sense is desired.
When it is desirable to trade off exact equality of Ax and y in exchange for a sparser x, basis pursuit denoising is preferred.
Basis pursuit is equivalent to linear programming.[1]
See also[]
- Compressed sensing
- Group testing
- Lasso (statistics)
- Matching pursuit
- Sparse approximation
- Basis pursuit denoising
Notes[]
- ^ A. M. Tillmann Equivalence of Linear Programming and Basis Pursuit, PAMM (Proceedings in Applied Mathematics and Mechanics) Volume 15, 2015, pp. 735-738, DOI: 10.1002/PAMM.201510351
References & further reading[]
- Stephen Boyd, Lieven Vandenbergh: Convex Optimization, Cambridge University Press, 2004, ISBN 9780521833783, pp. 337–337
- Simon Foucart, Holger Rauhut: A Mathematical Introduction to Compressive Sensing. Springer, 2013, ISBN 9780817649487, pp. 77–110
External links[]
- Shaobing Chen, David Donoho: Basis Pursuit
- Terence Tao: Compressed Sensing. Mahler Lecture Series (slides)
Categories:
- Applied mathematics stubs
- Mathematical optimization
- Constraint programming