Restricted Eigenvalue Properties for Correlated Gaussian Designs
Restricted Eigenvalue Properties for Correlated Gaussian Designs
复制标题
DOI：
10.5555/1756006.1859929
复制
发表时间：
2010-03
期刊：
影响因子：
--
通讯作者：
Garvesh Raskutti;M. Wainwright;Bin Yu
中科院分区：
文献类型：
--
作者：
Garvesh Raskutti;M. Wainwright;Bin Yu
基于L1松弛的方法，如基追踪法和套索法，在高维稀疏回归中非常流行。这些方法的成功条件现在已经很好地理解了：(1)当且仅当设计矩阵X满足受限零空间性质时，才可能在无噪声环境下精确恢复，以及(2)每当设计满足受限特征值条件时，Lasso估计的平方L2误差以极小极大最优率klogp/n衰减，其中k是带有加性高斯噪声的p维回归问题的稀疏性。因此，关键问题是确定设计矩阵X何时满足这些期望的属性。到目前为止，已经有许多结果表明，当X的所有项都是独立的且同分布的(I.I.D.)，或者行是酉时，都满足限制等距性质，这意味着限制零空间和特征值条件。本文直接证明了对于预测器可能高度依赖的相当一般的一类高斯矩阵，约束零空间和特征值条件以高概率成立，因此约束等距条件可以以高概率被违反。通过这种方式，我们的结果将关于L1-松弛的有吸引力的理论保证推广到比完全独立或酉化设计的情形更广泛的一类问题。
Methods based on l1-relaxation, such as basis pursuit and the Lasso, are very popular for sparse regression in high dimensions. The conditions for success of these methods are now well-understood: (1) exact recovery in the noiseless setting is possible if and only if the design matrix X satisfies the restricted nullspace property, and (2) the squared l2-error of a Lasso estimate decays at the minimax optimal rate k log p / n, where k is the sparsity of the p-dimensional regression problem with additive Gaussian noise, whenever the design satisfies a restricted eigenvalue condition. The key issue is thus to determine when the design matrix X satisfies these desirable properties. Thus far, there have been numerous results showing that the restricted isometry property, which implies both the restricted nullspace and eigenvalue conditions, is satisfied when all entries of X are independent and identically distributed (i.i.d.), or the rows are unitary. This paper proves directly that the restricted nullspace and eigenvalue conditions hold with high probability for quite general classes of Gaussian matrices for which the predictors may be highly dependent, and hence restricted isometry conditions can be violated with high probability. In this way, our results extend the attractive theoretical guarantees on l1-relaxations to a much broader class of problems than the case of completely independent or unitary designs.