Basis pursuit denoising

In applied mathematics and statistics, basis pursuit denoising (BPDN) refers to a mathematical optimization problem of the form

${\displaystyle \min _{x}\left({\frac {1}{2}}\|y-Ax\|_{2}^{2}+\lambda \|x\|_{1}\right),}$

where ${\displaystyle \lambda }$ is a parameter that controls the trade-off between sparsity and reconstruction fidelity, ${\displaystyle x}$ is an ${\displaystyle N\times 1}$ solution vector, ${\displaystyle y}$ is an ${\displaystyle M\times 1}$ vector of observations, ${\displaystyle A}$ is an ${\displaystyle M\times N}$ transform matrix and ${\displaystyle M<N}$. This is an instance of convex optimization.

Some authors refer to basis pursuit denoising as the following closely related problem:

${\displaystyle \min _{x}\|x\|_{1}{\text{ subject to }}\|y-Ax\|_{2}^{2}\leq \delta ,}$

which, for any given ${\displaystyle \lambda }$, is equivalent to the unconstrained formulation for some (usually unknown a priori) value of ${\displaystyle \delta }$. The two problems are quite similar. In practice, the unconstrained formulation, for which most specialized and efficient computational algorithms are developed, is usually preferred. The unconstrained formulation is NP-hard.^[1]

Either types of basis pursuit denoising solve a regularization problem with a trade-off between having a small residual (making ${\displaystyle y}$ close to ${\displaystyle Ax}$ in terms of the squared error) and making ${\displaystyle x}$ simple in the ${\displaystyle \ell _{1}}$-norm sense. It can be thought of as a mathematical statement of Occam's razor, finding the simplest possible explanation (i.e. one that yields ${\displaystyle \min _{x}\|x\|_{1}}$) capable of accounting for the observations ${\displaystyle y}$.

Exact solutions to basis pursuit denoising are often the best computationally tractable approximation of an underdetermined system of equations.^{[citation needed]} Basis pursuit denoising has potential applications in statistics (see the LASSO method of regularization), image compression and compressed sensing.

When ${\displaystyle \delta =0}$, this problem becomes basis pursuit.

Basis pursuit denoising was introduced by Chen and Donoho in 1994,^[2] in the field of signal processing. In statistics, it is well known under the name LASSO, after being introduced by Tibshirani in 1996.

Solving basis pursuit denoising

The problem is a convex quadratic problem, so it can be solved by many general solvers, such as interior-point methods. For very large problems, many specialized methods that are faster than interior-point methods have been proposed.

Several popular methods for solving basis pursuit denoising include the in-crowd algorithm (a fast solver for large, sparse problems^[3]), homotopy continuation, fixed-point continuation (a special case of the forward–backward algorithm^[4]) and spectral projected gradient for L1 minimization (which actually solves LASSO, a related problem).