Sparse nonnegative solution of underdetermined linear equations by linear programming
Sparse nonnegative solution of underdetermined linear equations by linear programming
复制标题
DOI：
10.1073/pnas.0502269102
复制
发表时间：
2005-07-05
影响因子：
11.1
通讯作者：
Tanner, J
中科院分区：
文献类型：
--
作者：
Donoho, DL;Tanner, J
考虑一个欠定线性方程组y = Ax，其中y和d × n矩阵A是已知的.我们寻找满足y = Ax的非零最少的非负ex。一般来说，这个问题是NP难。然而，对于许多矩阵A，存在阈值现象：如果稀疏解足够稀疏，则可以通过线性规划找到它。我们用凸多面体的理论来解释这一点。设a（j）表示A的第j列，1
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