Basis pursuit

Basis pursuit is the mathematical optimization problem of the form

$\min _{x}\|x\|_{1}\quad {\text{subject to}}\quad y=Ax,$

where x is a N-dimensional solution vector (signal), y is a M-dimensional 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 L₁ 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.

See also

• Basis pursuit denoising
• Compressed sensing
• Frequency spectrum
• Group testing
• Lasso (statistics)
• Least-squares spectral analysis
• Matching pursuit
• Sparse approximation

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)