Neighborly Polytopes And Sparse Solution Of Underdetermined Linear Equations
Neighborly Polytopes And Sparse Solution Of Underdetermined Linear Equations
复制标题
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
D. Donoho
中科院分区：
文献类型：
--
作者：
D. Donoho
考虑一个d×n矩阵A，其中d<；n。解y=Ax中的x的问题是欠定的，并且有许多可能的解(如果有的话)。在几个领域中，人们感兴趣的是找到最稀疏的解--具有最少非零点的解--但通常这涉及到组合优化。设Ai表示A的第i列，1≤i≤n.取R中2n个点(±ai)的凸壳构成的商多面体P与A相联系，如果k+1个元素(±ai)的每个子集k+1 L=1都是P的一个面的顶点，则称P为中心对称的k-邻域的.证明了如果P是k邻域的，则当系统y=Ax存在至多k个非零点的解时，该解也是满足y=Ax的凸优化问题Min‖x‖1的唯一解；反之亦然。用极小化方法研究稀疏解与凸多面体的邻域性之间的完全等价性，立即在每个领域都给出了新的结果。一方面，我们利用关于`极小化的已知结果，得到了新的邻域中心对称多面体族；另一方面，通过利用中心对称多面体的邻域性的已知极限，我们得到了对`最小化寻找稀疏解的能力的新限制。最近还研究了`和稀疏优化之间较弱的等价概念。这些等价于商多面体的其他有趣性质。因此，假设A的列处于一般位置。考虑具有k<；d/2个非零点的向量，它们同时是y=Ax的最稀疏解和最小`解。当且仅当商多面体P具有与正则交叉多面体C一样多的k维面时，这些构成具有k个非零点的所有向量的分数1−当且仅当商多面体P具有与正则交叉多面体C相同的k维面的至少1个−。结合最近关于随机投影的交叉多面体的面数的工作，我们了解到对于大的d，具有d个方程和4d/3个未知数的绝大多数线性方程组具有以下性质：如果存在小于0.49d个非零点的解，则它是唯一的最小`解。概述了数字通信中的风格化应用；对于大的n，如果严重错误的符号和位置是随机的，并且不受恶意对手选择的.11n严重错误的影响，则可以使用长度为n的码字传输n/4条信息，并且对所接收的码字中的0.49n个严重错误具有免疫力。接收器使用`最小化。
Consider a d × n matrix A, with d < n. The problem of solving for x in y = Ax is underdetermined, and has many possible solutions (if there are any). In several fields it is of interest to find the sparsest solution – the one with fewest nonzeros – but in general this involves combinatorial optimization. Let ai denote the i-th column of A, 1 ≤ i ≤ n. Associate to A the quotient polytope P formed by taking the convex hull of the 2n points (±ai) in R. P is centrosymmetric and is called (centrally) k-neighborly if every subset of k + 1 elements (±ilail) k+1 l=1 are the vertices of a face of P . We show that if P is k-neighborly, then if a system y = Ax has a solution with at most k nonzeros, that solution is also the unique solution of the convex optimization problem min ‖x‖1 subject to y = Ax; the converse holds as well. This complete equivalence between the study of sparse solution by ` minimization and neighborliness of convex polytopes immediately gives new results in each field. On the one hand, we get new families of neighborly centrosymmetric polytopes, by exploiting known results about sparsity of ` minimization; on the other, we get new limits on the ability of ` minimization to find sparse solutions, by exploiting known limits on neighborliness of centrally symmetric polytopes. Weaker notions of equivalence between ` and sparse optimization have also been studied recently. These are equivalent to other interesting properties of the quotient polytope. Thus, suppose the columns of A are in general position. Consider the vectors having k < d/2 nonzeros that are simultaneously the sparsest solution of y = Ax and the minimal ` solution. These make up a fraction 1 − of all vectors with k nonzeros if and only if the quotient polytope P has at least 1− as many k-dimensional faces as the regular cross polytope C. Combining this with recent work on face numbers of randomly-projected cross-polytopes, we learn that for large d, the overwhelming majority of systems of linear equations with d equations and 4d/3 unknowns have the following property: if there is a solution with fewer than .49d nonzeros, it is the unique minimum ` solution. A stylized application in digital communication is sketched; for large n, it is possible to transmit n/4 pieces of information using a codeword of length n with immunity to .49n gross errors in the received codeword, if the signs and sites of the gross errors are random, and with immunity to .11n gross errors chosen by a malicious opponent. The receiver uses ` minimization.