Basis pursuit denoising
||This article may be too technical for most readers to understand. (November 2013)|
where is a parameter that controls the trade-off between sparsity and reconstruction fidelity, is an solution vector, is an vector of observations, is an transform matrix and . This is an instance of convex optimization and also of quadratic programming.
Some authors refer to basis pursuit denoising as the following closely related problem:
which, for any given , is equivalent to the unconstrained formulation for some (usually unknown a priori) value of . The two problems are quite similar, but most specialized numerical algorithms can only solve the unconstrained formulation.
Either type of basis pursuit denoising solves a regularization problem with a trade-off between having a small residual (making close to in terms of an distance) and making simple in the sense. It can be thought of as a mathematical statement of Occam's razor, finding the simplest possible explanation () capable of accounting for the observations ().
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 (c.f. the LASSO method of regularization), image compression and compressed sensing.
As (or when ), this problem becomes basis pursuit.
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).
|This applied mathematics-related article is a stub. You can help Wikipedia by expanding it.|