Sparse nonnegative solution of underdetermined linear equations by linear programming

AUTOR(ES)

Donoho, David L.

FONTE

National Academy of Sciences

RESUMO

Consider an underdetermined system of linear equations y = Ax with known y and d × n matrix A. We seek the nonnegative x 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 aj denote the jth column of A, 1 ≤ j ≤ n, let a0 = 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 ajs 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.

Documentos Relacionados

• Two derivative-free methods for solving underdetermined nonlinear systems of equations
• FUNCTIONAL EQUATIONS IN THE THEORY OF DYNAMIC PROGRAMMING. II. NONLINEAR DIFFERENTIAL EQUATIONS
• DYNAMIC PROGRAMMING APPLIED TO CONTROL PROCESSES GOVERNED BY GENERAL FUNCTIONAL EQUATIONS*
• A NEW APPROACH TO THE NUMERICAL SOLUTION OF A CLASS OF LINEAR AND NONLINEAR INTEGRAL EQUATIONS OF FREDHOLM TYPE*
• LINEAR AND NONLINEAR SEMIDEFINITE PROGRAMMING