Equivalence of Linear Programming and Basis Pursuit
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.
@inproceedings{Tillmann2015,
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}
}
