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).

References

1. Natarajan, B. K. (April 1995). "Sparse Approximate Solutions to Linear Systems". SIAM Journal on Computing. 24 (2): 227–234. doi:10.1137/S0097539792240406. ISSN   0097-5397.
2. Chen, Shaobing; Donoho, D. (1994). "Basis pursuit". Proceedings of 1994 28th Asilomar Conference on Signals, Systems and Computers. Vol. 1. pp. 41–44. doi:10.1109/ACSSC.1994.471413. ISBN   0-8186-6405-3. S2CID   96447294.
3. See Gill, Patrick R.; Wang, Albert; Molnar, Alyosha (2011). "The In-Crowd Algorithm for Fast Basis Pursuit Denoising". IEEE Transactions on Signal Processing . 59 (10): 4595–4605. Bibcode:2011ITSP...59.4595G. doi:10.1109/TSP.2011.2161292. S2CID   15320645; demo MATLAB code available .
4. "Forward Backward Algorithm". Archived from the original on February 16, 2014.

External links

• A list of BPDN solvers at the sparse- and low-rank approximation wiki.