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 NPhard ?0 norm minimization problem min
x0 subject to Ax = a, Bx ? b and x? ? 1, is completely equivalent to the concave
minimization min xp 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.
Subject
linear programming
linear inequalities
linear equations
l0 minimization
Permanent Link
http://digital.library.wisc.edu/1793/64358Citation
1102
Part of
Related items
Showing items related by title, author, creator and subject.

Characterization of Linear Complementarity Problems as Linear Programs
Mangasarian, Olvi (University of WisconsinMadison Department of Computer Sciences, 1976)It is shown that the linear complementarity problem of finding an nby1 vector x such that Mx + q > 0, x > 0, and xT(Mx+q) = 0, where M is a given nbyn real matrix and q is a given nbyl vector, is solvable if and ... 
Robust Linear Programming Discrimination of Two Linearly Inseparable Sets
Bennett, Kristin P; Mangasarian, Olvi L (University of WisconsinMadison Department of Computer Sciences, 1991) 
Error Bounds for Strongly Convex Programs and (Super) Linearly Convergent Iterative Schemes for the Least 2 Norm Solution of Linear Programs
Mangasarian, Olvi L; DeLeone, Renato (University of WisconsinMadison Department of Computer Sciences, 1986)