“Basis pursuit denoising”的意思、由来-开放百科全书

词条

Basis pursuit denoising

释义

Solving basis pursuit denoising
References
External links

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

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. In practice, the unconstrained formulation, for which most specialized and efficient computational algorithms are developed, is usually preferred.

Either types of basis pursuit denoising solve a regularization problem with a trade-off between having a small residual (making close to in terms of the squared error) and making simple in the -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 ) 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.{{citation needed|date=January 2014}} 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.

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^[1]), homotopy continuation, fixed-point continuation (a special case of the [https://web.archive.org/web/20140216231347/http://www.ugcs.caltech.edu/~srbecker/wiki/Forward_Backward_Algorithm forward backward algorithm]) and spectral projected gradient for L1 minimization (which actually solves LASSO, a related problem).

References

1. ^See The In-Crowd Algorithm for Fast Basis Pursuit Denoising, IEEE Trans Sig Proc 59 (10), Oct 1 2011, pp. 4595 - 4605, , demo MATLAB code available

External links

A list of [https://web.archive.org/web/20150502191143/http://www.ugcs.caltech.edu/~srbecker/wiki/Category:Solvers BPDN solvers] at the [https://web.archive.org/web/20150504060355/http://ugcs.caltech.edu/~srbecker/wiki/Main_Page sparse- and low-rank approximation wiki].

1 : Mathematical optimization

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。