Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Basis pursuit
Summary
Basis pursuit is the mathematical optimization 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 L1 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 is preferred.
Basis pursuit problems can be converted to linear programming problems in polynomial time and vice versa, making the two types of problems polynomially equivalent.
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 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 as:
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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.