Basis pursuit

This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. Please help improve this article by introducing more precise citations. (April 2020) (Learn how and when to remove this message)

Basis pursuit is the mathematical optimization problem of the form

${\displaystyle \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. Basis pursuit is NP-hard.^[1]

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