Basis Pursuit Denoising
A Basis Pursuit Denoising is a Mathematics that ...
- AKA: BPD.
- …
- Counter-Example(s):
- See: Basis Pursuit, Sparse Vector, Convex Optimization, Quadratic Programming, Regularization, Occam's Razor, Image Compression.
References
2015
- (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/basis_pursuit_denoising Retrieved:2015-5-11.
- In mathematics and machine learning, basis pursuit denoising (BPDN) is one approach to solving a mathematical optimization problem of the form: : [math]\displaystyle{ \min_x \frac{1}{2}\|y-Ax\|^2_2+\lambda\|x\|_1. }[/math] where [math]\displaystyle{ \lambda }[/math] is a parameter that controls the trade-off between sparsity and reconstruction fidelity, [math]\displaystyle{ x }[/math] is an [math]\displaystyle{ N \times 1 }[/math] solution vector, [math]\displaystyle{ y }[/math] is an [math]\displaystyle{ M \times 1 }[/math] vector of observations, [math]\displaystyle{ A }[/math] is an [math]\displaystyle{ M \times N }[/math] transform matrix and [math]\displaystyle{ M \lt N }[/math]. 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: : [math]\displaystyle{ \min_x \|x\|_1 \;\textrm{subject} \ \textrm{to}\;\;\|y-Ax\|^2_2 \le \delta }[/math] which, for any given [math]\displaystyle{ \lambda }[/math] , is equivalent to the unconstrained formulation for some (usually unknown a priori) value of [math]\displaystyle{ \delta }[/math] . 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 [math]\displaystyle{ y }[/math] close to [math]\displaystyle{ Ax }[/math] in terms of an [math]\displaystyle{ L_2 }[/math] distance) and making [math]\displaystyle{ x }[/math] simple in the [math]\displaystyle{ L_1 }[/math] sense. It can be thought of as a mathematical statement of Occam's razor, finding the simplest possible explanation ([math]\displaystyle{ \min_x \|x\|_1 }[/math] ) capable of accounting for the observations ([math]\displaystyle{ \min_x \|y-Ax\|^2_2 }[/math]).
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 [math]\displaystyle{ \lambda \rightarrow 0 }[/math] (or when [math]\displaystyle{ \delta = 0 }[/math] ), this problem becomes basis pursuit.
- In mathematics and machine learning, basis pursuit denoising (BPDN) is one approach to solving a mathematical optimization problem of the form: : [math]\displaystyle{ \min_x \frac{1}{2}\|y-Ax\|^2_2+\lambda\|x\|_1. }[/math] where [math]\displaystyle{ \lambda }[/math] is a parameter that controls the trade-off between sparsity and reconstruction fidelity, [math]\displaystyle{ x }[/math] is an [math]\displaystyle{ N \times 1 }[/math] solution vector, [math]\displaystyle{ y }[/math] is an [math]\displaystyle{ M \times 1 }[/math] vector of observations, [math]\displaystyle{ A }[/math] is an [math]\displaystyle{ M \times N }[/math] transform matrix and [math]\displaystyle{ M \lt N }[/math]. This is an instance of convex optimization and also of quadratic programming.