Equivalence of Minimal ?_0- and ?_p-Norm Solutions of Linear Equalities, Inequalities and Linear Programs for Sufficiently Small p

摘要

For a bounded system of linear equalities and inequalities, we show that the NP-hard ?_0-norm minimization problem is completely equivalent to the concave ?_p-norm minimization problem, 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.