Mathematical optimization problem
In applied mathematics and statistics, basis pursuit denoising (BPDN) refers to a mathematical optimization problem of the form
 formula_1
where formula_2 is a parameter that controls the trade-off between sparsity and reconstruction fidelity, formula_3 is an formula_4 solution vector, formula_5 is an formula_6 vector of observations, formula_7 is an formula_8 transform matrix and formula_9. This is an instance of convex optimization.
Some authors refer to basis pursuit denoising as the following closely related problem:
 formula_10
which, for any given formula_2, is equivalent to the unconstrained formulation for some (usually unknown "a priori") value of formula_12. 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. 
Either types of basis pursuit denoising solve a regularization problem with a trade-off between having a small residual (making formula_5 close to formula_14 in terms of the squared error) and making formula_3 simple in the formula_16-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 formula_17) capable of accounting for the observations formula_5.
Exact solutions to basis pursuit denoising are often the best computationally tractable approximation of an underdetermined system of equations. Basis pursuit denoising has potential applications in statistics (see the LASSO method of regularization), image compression and compressed sensing.
When formula_19, this problem becomes basis pursuit.
Basis pursuit denoising was introduced by Chen and Donoho in 1994, 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), homotopy continuation, fixed-point continuation (a special case of the forward–backward algorithm) and spectral projected gradient for L1 minimization (which actually solves LASSO, a related problem).
References.
 ;templatestyles src="Reflist/styles.css" / ;