Journal
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA
Volume 102, Issue 27, Pages 9446-9451Publisher
NATL ACAD SCIENCES
DOI: 10.1073/pnas.0502269102
Keywords
neighborly polytopes; cyclic polytopes; combinatorial optimization; convex hull of Gaussian samples; positivity constraints in ill-posed problems
Categories
Ask authors/readers for more resources
Consider an underdetermined system of linear equations y = Ax with known y and d x n matrix A. We seek the nonnegativex with the fewest nonzeros satisfying y = Ax. in general, this problem is NP-hard. However, for many matrices A there is a threshold phenomenon: if the sparsest solution is sufficiently sparse, it can be found by linear programming. We explain this by the theory of convex polytopes. Let a(j) denote the jth column of A, 1 <= j <= n, let a(0) = 0 and P denote the convex hull of the aj. We say the polytope P is outwardly k-neighborly if every subset of k vertices not including 0 spans a face of P. We show that outward k-neighborliness is equivalent to the statement that, whenever y = Ax has a nonnegative solution with at most k nonzeros, it is the nonnegative solution to y = Ax having minimal sum. We also consider weak neighborliness, where the overwhelming majority of k-sets of a,5 not containing 0 span a face of P. This implies that most nonnegative vectors x with k nonzeros are uniquely recoverable from y = Ax by linear programming. Numerous corollaries follow by invoking neighborliness results. For example, for most large n by 2n underdetermined systems having a solution with fewer nonzeros than roughly half the number of equations, the sparsest solution can be found by linear programming.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available