Equivalence of Minimal L0 and Lp Norm Solutions of Linear Equalities, Inequalities and Linear Programs for Sufficiently Small p

Abstract

For a bounded system of linear equalities and inequalities we show that the NP-hard ?0 norm minimization problem min ||x||0 subject to Ax = a, Bx ? b and ||x||? ? 1, is completely equivalent to the concave minimization min ||x||p subject to Ax = a, Bx ? b and ||x||? ? 1, for a sufficiently small p. A local solution to the latter problem can be easily obtained by solving a provably finite number of linear programs. Computational results frequently leading to a global solution of the ?0 minimization problem and often producing sparser solutions than the corresponding ?1 solution are given. A similar approach applies to finding minimal ?0 solutions of linear programs.