Basis pursuit is the mathematical optimization problem of the form

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 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 problems can be converted to linear programming problems in polynomial time and vice versa, making the two types of problems polynomially equivalent.[1]

Equivalence to Linear Programming

edit

A basis pursuit problem can be converted to a linear programming problem by first noting that

 

where  . This construction is derived from the constraint  , where the value of   is intended to be stored in   or   depending on whether   is greater or less than zero, respectively. Although a range of   and   values can potentially satisfy this constraint, solvers using the simplex algorithm will find solutions where one or both of   or   is zero, resulting in the relation  .

From this expansion, the problem can be recast in canonical form as:[1]

 

See also

edit

Notes

edit
  1. ^ a b 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

edit
  • 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
edit