Basis pursuit
Encyclopedia
Basis pursuit is the mathematical optimization problem of the form:
where x is a N × 1 solution vector, y is a M × 1 vector of observations, A is a M × N transform matrix and M < N.
It is usually applied in cases where there is an underdetermined system of linear equations y = Ax that must be satisfied exactly, and the sparsest solution in the L1 sense is desired.
Basis pursuit can be thought of as a least squares
problem with an L1 regularizer
.
When it is desirable to trade off exact congruence of Ax and y in exchange for a sparser x, basis pursuit denoising is preferred.
where x is a N × 1 solution vector, y is a M × 1 vector of observations, A is a M × N transform matrix and M < N.
It is usually applied in cases where there is an underdetermined system of linear equations y = Ax that must be satisfied exactly, and the sparsest solution in the L1 sense is desired.
Basis pursuit can be thought of as a least squares
Least squares
The method of least squares is a standard approach to the approximate solution of overdetermined systems, i.e., sets of equations in which there are more equations than unknowns. "Least squares" means that the overall solution minimizes the sum of the squares of the errors made in solving every...
problem with an L1 regularizer
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...
.
When it is desirable to trade off exact congruence of Ax and y in exchange for a sparser x, basis pursuit denoising is preferred.