For most large underdetermined systems of linear equations the minimal l1-norm solution is also the sparsest solution
For most large underdetermined systems of linear equations the minimal l1-norm solution is also the sparsest solution
复制标题
DOI：
10.1002/cpa.20132
复制
发表时间：
2006-06-01
影响因子：
3
通讯作者：
Donoho, DL
中科院分区：
文献类型：
--
作者：
Donoho, DL
我们考虑线性方程\(y = \Phi x\)，其中\(y\)是\(\mathbb{R}^n\)中的给定向量，\(\Phi\)是给定的\(n\times m\)矩阵，且\(n < m\)。使得对于较大的\(n\)以及除了可忽略部分之外的所有\(V\)，以下性质成立：对于每个可以由系数向量\(x^{(0)}\in\mathbb{R}^m\)表示为\(y = \Phi x^{(0)}\)且非零元素少于\(\rho\cdot n\)的\(y\)，\(\ell_1\)最小化问题\(\min\lVert x\rVert_1\)，约束条件为\(\Phi x = y\)的解\(x^{(1)}\)是唯一的且等于\(x^{(0)}\)。相比之下，在这种具有挑战性的情况下，稀疏求解此类系统的启发式尝试——贪心算法和阈值法——效果不佳。这些技术包括在巴拿赫空间理论中使用随机比例嵌入和近似球形截面，以及随机威沙特矩阵特征值的偏差界。（c）2006威利期刊公司
We consider linear equations y = phi x where y is a given vector in R-n and phi is a given n x m matrix with n < m 0 so that for large n and for all Vs except a negligible fraction, the following property holds: For every y having a representation y = phi x(0) by a coefficient vector x(0) epsilon R-m. with fewer than rho center dot n nonzeros, the solution x(1) of the l(1)-minimization problemmin parallel to x parallel to(1) subject to phi x = yis unique and equal to x(0). In contrast, heuristic attempts to sparsely solve such systems-greedy algorithms and thresholding-perform poorly ill this challenging setting. The techniques include the use of random proportional embeddings and almost-spherical sections in Banach space theory, and deviation bounds for the eigenvalues of random Wishart matrices. (c) 2006 Wiley Periodicals, Inc.