Basis pursuit is the
mathematical optimization
Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...
problem of the form
:
where ''x'' is a ''N''-dimensional solution vector (signal), ''y'' is a ''M''-dimensional vector of observations (measurements), ''A'' is a ''M'' × ''N'' transform matrix (usually measurement matrix) and ''M'' < ''N''.
It is usually applied in cases where there is an underdetermined system of linear equations ''y'' = ''Ax'' that must be exactly satisfied, and the
sparsest solution in the ''L''
1 sense is desired.
When it is desirable to trade off exact equality of ''Ax'' and ''y'' in exchange for a sparser ''x'',
basis pursuit denoising
In applied mathematics and statistics, basis pursuit denoising (BPDN) refers to a mathematical optimization problem of the form
: \min_x \left(\frac \, y - Ax\, ^2_2 + \lambda \, x\, _1\right),
where \lambda is a parameter that controls the trade ...
is preferred.
Basis pursuit problems can be converted to
linear programming
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear function#As a polynomial function, li ...
problems in polynomial time and vice versa, making the two types of problems polynomially equivalent.
[A. M. Tillmann ]
Equivalence of Linear Programming and Basis Pursuit
', PAMM (Proceedings in Applied Mathematics and Mechanics) Volume 15, 2015, pp. 735-738, DOI: 10.1002/PAMM.201510351
Equivalence to Linear Programming
A basis pursuit problem can be converted to a linear programming problem by first noting that
:
where
. This construction is derived from the constraint
, where the value of
is intended to be stored in
or
depending on whether
is greater or less than zero, respectively. Although a range of
and
values can potentially satisfy this constraint, solvers using the
simplex algorithm
In mathematical optimization, Dantzig's simplex algorithm (or simplex method) is a popular algorithm for linear programming.
The name of the algorithm is derived from the concept of a simplex and was suggested by T. S. Motzkin. Simplices are n ...
will find solutions where one or both of
or
is zero, resulting in the relation
.
From this expansion, the problem can be recast in
canonical form
In mathematics and computer science, a canonical, normal, or standard form of a mathematical object is a standard way of presenting that object as a mathematical expression. Often, it is one which provides the simplest representation of an obje ...
as:
:
See also
*
Basis pursuit denoising
In applied mathematics and statistics, basis pursuit denoising (BPDN) refers to a mathematical optimization problem of the form
: \min_x \left(\frac \, y - Ax\, ^2_2 + \lambda \, x\, _1\right),
where \lambda is a parameter that controls the trade ...
*
Compressed sensing
Compressed sensing (also known as compressive sensing, compressive sampling, or sparse sampling) is a signal processing technique for efficiently acquiring and reconstructing a Signal (electronics), signal, by finding solutions to Underdetermined ...
*
Frequency spectrum
The power spectrum S_(f) of a time series x(t) describes the distribution of power into frequency components composing that signal. According to Fourier analysis, any physical signal can be decomposed into a number of discrete frequencies, ...
*
Group testing
In statistics and combinatorial mathematics, group testing is any procedure that breaks up the task of identifying certain objects into tests on groups of items, rather than on individual ones. First studied by Robert Dorfman in 1943, group tes ...
*
Lasso (statistics)
In statistics and machine learning, lasso (least absolute shrinkage and selection operator; also Lasso or LASSO) is a regression analysis method that performs both variable selection and regularization in order to enhance the prediction accuracy ...
*
Least-squares spectral analysis
Least-squares spectral analysis (LSSA) is a method of estimating a frequency spectrum, based on a least squares fit of sinusoids to data samples, similar to Fourier analysis. Fourier analysis, the most used spectral method in science, generally ...
*
Matching pursuit
Matching pursuit (MP) is a sparse approximation algorithm which finds the "best matching" projections of multidimensional data onto the span of an over-complete (i.e., redundant) dictionary D. The basic idea is to approximately represent a signal ...
*
Sparse approximation Sparse approximation (also known as sparse representation) theory deals with sparse solutions for systems of linear equations. Techniques for finding these solutions and exploiting them in applications have found wide use in image processing, sign ...
Notes
References & further reading
* Stephen Boyd, Lieven Vandenbergh: ''Convex Optimization'', Cambridge University Press, 2004, , pp. 337–337
* Simon Foucart, Holger Rauhut: ''A Mathematical Introduction to Compressive Sensing''. Springer, 2013, , pp. 77–110
External links
* Shaobing Chen, David Donoho
''Basis Pursuit''*
Terence Tao
Terence Chi-Shen Tao (; born 17 July 1975) is an Australian-American mathematician. He is a professor of mathematics at the University of California, Los Angeles (UCLA), where he holds the James and Carol Collins chair. His research includes ...
''Compressed Sensing'' Mahler Lecture Series (slides)
{{Mathapplied-stub
Mathematical optimization
Constraint programming