.png){kind=icon}
返回
Sparse nonnegative solution of underdetermined linear equations by linear programming
.png){kind=icon}
OA
AI
DOI：10.1073/pnas.0502269102.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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.
Keyword:
neighborly polytopes
cyclic polytopes
combinatorial optimization
convex hull of Gaussian samples
positivity constraints in ill-posed problems
期刊
P
IF:
9.1
论文数:
10.8W
被引数:
73.5W
机构
暂无机构信息
引用论文
.png){kind=icon}
查看更多内容