Equivalence of Linear Programming and Basis Pursuit

Andreas Tillmann
GAMM 86th Annual Scientific Conference

In this note, we show that linear programming and the prominent Basis Pursuit problem (i.e., minimizing the L1-norm of a vector x subject to an underdetermined linear equation system Ax = b) are theoretically equivalent, and briefly discuss possible ramifications regarding computational complexity and practical applicability.

» Show BibTeX

author = {A. M. Tillmann},
title = {{Equivalence of Linear Programming and Basis Pursuit}},
booktitle = {{PAMM (Proceedings in Applied Mathematics and Mechanics}},
volume = {15},
number = {1},
pages = {735--738},
year = {2015},
note = {DOI: 10.1002/PAMM.201510351}

Disclaimer Home Visual Computing institute RWTH Aachen University