Basis pursuit denoising
Encyclopedia
Basis pursuit denoising is the mathematical optimization problem of the form:
where
is a parameter that controls the trade-off between sparsity and reconstruction fidelity, 
is a 
solution vector, 
is a 
vector of observations, 
is a 
transform matrix and 
.
Basis pursuit denoising solves a regularization
problem with a trade-off between having a small residual (making
close to 
in the 
sense) and making 
simple in the 
sense. It can be thought of as a mathematical statement of Occam's razor
, finding the simplest possible explanation (low
) capable of accounting for the observations (low 
).
Exact solutions to basis pursuit denoising are often the best computationally tractable approximation of an underdetermined system of equations. Basis pursuit denoising thus has potential applications in statistics (c.f. the LASSO method of regularization
), image compression
and compressed sensing
.
As
, this problem becomes basis pursuit.
where
is a parameter that controls the trade-off between sparsity and reconstruction fidelity, is a solution vector, is a vector of observations, is a transform matrix and .Basis pursuit denoising solves a regularization
Regularization (mathematics)
In mathematics and statistics, particularly in the fields of machine learning and inverse problems, regularization involves introducing additional information in order to solve an ill-posed problem or to prevent overfitting...
problem with a trade-off between having a small residual (making
close to in the sense) and making simple in the sense. It can be thought of as a mathematical statement of Occam's razorOccam's razor
Occam's razor, also known as Ockham's razor, and sometimes expressed in Latin as lex parsimoniae , is a principle that generally recommends from among competing hypotheses selecting the one that makes the fewest new assumptions.-Overview:The principle is often summarized as "simpler explanations...
, finding the simplest possible explanation (low
) capable of accounting for the observations (low ).Exact solutions to basis pursuit denoising are often the best computationally tractable approximation of an underdetermined system of equations. Basis pursuit denoising thus has potential applications in statistics (c.f. the LASSO method of regularization
Regularization (mathematics)
In mathematics and statistics, particularly in the fields of machine learning and inverse problems, regularization involves introducing additional information in order to solve an ill-posed problem or to prevent overfitting...
), image compression
Image compression
The objective of image compression is to reduce irrelevance and redundancy of the image data in order to be able to store or transmit data in an efficient form.- Lossy and lossless compression :...
and compressed sensing
Compressed sensing
Compressed sensing, also known as compressive sensing, compressive sampling and sparse sampling, is a technique for finding sparse solutions to underdetermined linear systems...
.
As
, this problem becomes basis pursuit.