Sharp Thresholds for High-Dimensional and Noisy Sparsity Recovery Using l1-Constrained Quadratic Programming (Lasso)
Sharp Thresholds for High-Dimensional and Noisy Sparsity Recovery Using l1-Constrained Quadratic Programming (Lasso)
复制标题
DOI：
10.1109/tit.2009.2016018
复制
发表时间：
2009-05-01
影响因子：
2.5
通讯作者：
Wainwright, Martin J.
中科院分区：
文献类型：
--
作者：
Wainwright, Martin J.
一致地估计向量的稀疏模式的问题是R-p的一个元素，基于在各种环境中出现的被噪声污染的观测，包括信号去噪、稀疏近似、压缩感知和模型选择。我们分析了L(1)-约束二次规划(QP)，也被称为套索，恢复稀疏模式的行为。我们的主要结果是建立了关于问题维度p、β中非零元素个数k和观测个数v的精确条件，这些都是使用套索进行稀疏模式恢复的必要条件和充分条件。我们首先分析了使用确定性设计矩阵和亚高斯加性噪声进行观测的情况，给出了支持恢复和L(无穷)误差界的充分条件，以及不相干的必要性和最小值的界。然后我们转向随机设计的情况，其中设计的每一行都从N(0，Sigma)系综中抽取。对于满足互不相干条件的一类广义高斯系综，我们计算了阈值0<；θ(L)(Sigma)0的显式值，如果n>；2(theta(U)+Delta)klog(p-k)，则套索成功恢复稀疏模式的概率收敛到1，而对于n<；2(theta(L)-Delta)klog(p-k)，则成功恢复的概率收敛到零。对于均匀高斯系综(Sigma=i-p(X)(P))的特殊情况，我们证明了θ(L)=theta(U)=1，从而精确地确定了阈值n=2klog(p-k)。
The problem of consistently estimating the sparsity pattern of a vector beta* is an element of R-p based on observations contaminated by noise arises in various contexts, including signal denoising, sparse approximation, compressed sensing, and model selection. We analyze the behavior of l(1)-constrained quadratic programming (QP), also referred to as the Lasso, for recovering the sparsity pattern. Our main result is to establish precise conditions on the problem dimension p, the number k of nonzero elements in beta* and the number of observations v. that are necessary and sufficient for sparsity pattern recovery using the Lasso. We first analyze the case of observations made using deterministic design matrices and sub-Gaussian additive noise, and provide sufficient conditions for support recovery and l(infinity)-error bounds, as well as results showing the necessity of incoherence and bounds on the minimum value. We then turn to the case of random designs, in which each row of the design is drawn from a N(0, Sigma) ensemble. For a broad class of Gaussian ensembles satisfying mutual incoherence conditions, we compute explicit values of thresholds 0 < theta(l)(Sigma) 0, if n > 2 (theta(u) + delta)k log (p - k), then the Lasso succeeds in recovering the sparsity pattern with probability converging to one for large problems, whereas for n < 2(theta(l) - delta)k log(p - k), then the probability of successful recovery converges to zero. For the special case of the uniform Gaussian ensemble (Sigma = I-p (x) (p)), we show that theta(l) = theta(u) = 1, so that the precise threshold n = 2k log(p - k) is exactly determined.