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.