basis pursuit denoising

{{Short description|Mathematical optimization problem}}

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

: $\backslash min\_x\; \backslash left(\backslash frac\{1\}\{2\}\; \backslash |y\; -\; Ax\backslash |^2\_2\; +\; \backslash lambda\; \backslash |x\backslash |\_1\backslash right),$

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

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

: $\backslash min\_x\; \backslash |x\backslash |\_1\; \backslash text\{\; subject\; to\; \}\; \backslash |y\; -\; Ax\backslash |^2\_2\; \backslash le\; \backslash delta,$

which, for any given $\backslash lambda$, is equivalent to the unconstrained formulation for some (usually unknown a priori) value of $\backslash 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.{{Cite journal |last=Natarajan |first=B. K. |date=April 1995 |title=Sparse Approximate Solutions to Linear Systems |url=https://epubs.siam.org/doi/abs/10.1137/S0097539792240406 |journal=SIAM Journal on Computing |volume=24 |issue=2 |pages=227–234 |doi=10.1137/S0097539792240406 |issn=0097-5397|url-access=subscription }}

Either types of basis pursuit denoising solve a regularization problem with a trade-off between having a small residual (making $y$ close to $Ax$ in terms of the squared error) and making $x$ simple in the $\backslash 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 $\backslash min\_x\; \backslash |x\backslash |\_1$) capable of accounting for the observations $y$.

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 (see the LASSO method of regularization), image compression and compressed sensing.

When $\backslash delta\; =\; 0$, this problem becomes basis pursuit.

Basis pursuit denoising was introduced by Chen and Donoho in 1994,{{cite book |first1=Shaobing |last1=Chen |first2=D. |last2=Donoho |chapter=Basis pursuit |title=Proceedings of 1994 28th Asilomar Conference on Signals, Systems and Computers |year=1994 |volume=1 |pages=41–44 |doi=10.1109/ACSSC.1994.471413 |isbn=0-8186-6405-3 |s2cid=96447294 }} in the field of signal processing. In statistics, it is well known under the name LASSO, after being introduced by Tibshirani in 1996.