Basis pursuit denoising

Basis pursuit denoising is the mathematical optimization problem of the form: $\min_x \frac{1}{2}\|y-Ax\|^2_2+\lambda\|x\|_1.$

where λ is a parameter that controls the trade-off between sparsity and reconstruction fidelity, x is a $N \times 1$ solution vector, y is a $M \times 1$ vector of observations, A is a $M \times N$ transform matrix and M < N.

Basis pursuit denoising solves a regularization problem with a trade-off between having a small residual (making y close to Ax in the L2 sense) and making x simple in the L1 sense. It can be thought of as a mathematical statement of Occam's razor, finding the simplest possible explanation (low $\|x\|_1.$) capable of accounting for the observations (low $\|y-Ax\|^2_2$).

Exact solutions to basis pursuit denoising are often the best computationally tractable approximation of an underdetermined system of equations. Basis pursuit denoising thus has potential applications in statistics (c.f. the LASSO method of regularization), image compression and compressed sensing.

As $\lambda \rightarrow 0$, this problem becomes basis pursuit.

Solving basis pursuit denoising

Several popular methods for solving basis pursuit denoising include the in-crowd algorithm (the fastest solver for large, sparse problems), , and (which actually solves LASSO, a related problem).