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

${\displaystyle {\begin{aligned}\|x\|_{1}&=|x_{1}|+|x_{2}|+\ldots +|x_{n}|\\&=(x_{1}^{+}+x_{1}^{-})+(x_{2}^{+}+x_{2}^{-})+\ldots +(x_{n}^{+}+x_{n}^{-})\end{aligned}}}$ 

where ${\displaystyle x_{i}^{+},x_{i}^{-}\geq 0}$ . This construction is derived from the constraint ${\displaystyle x_{i}=x_{i}^{+}-x_{i}^{-}}$ , where the value of ${\displaystyle |x_{i}|}$  is intended to be stored in ${\displaystyle x_{i}^{+}}$  or ${\displaystyle x_{i}^{-}}$  depending on whether ${\displaystyle x_{i}}$  is greater or less than zero, respectively. Although a range of ${\displaystyle x_{i}^{+}}$  and ${\displaystyle x_{i}^{-}}$  values can potentially satisfy this constraint, solvers using the simplex algorithm will find solutions where one or both of ${\displaystyle x_{i}^{+}}$  or ${\displaystyle x_{i}^{-}}$  is zero, resulting in the relation ${\displaystyle |x_{i}|=(x_{i}^{+}+x_{i}^{-})}$ .

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

${\displaystyle {\begin{aligned}&{\text{Find a vector}}&&(\mathbf {x^{+}} ,\mathbf {x^{-}} )\\&{\text{that minimizes}}&&\mathbf {1} ^{T}\mathbf {x^{+}} +\mathbf {1} ^{T}\mathbf {x^{-}} \\&{\text{subject to}}&&A\mathbf {x^{+}} -A\mathbf {x^{-}} =\mathbf {y} \\&{\text{and}}&&\mathbf {x^{+}} ,\mathbf {x^{-}} \geq \mathbf {0} .\end{aligned}}}$ 

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

• 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

• Shaobing Chen, David Donoho: Basis Pursuit
• Terence Tao: Compressed Sensing. Mahler Lecture Series (slides)