Fundamental limits of exact support recovery in high dimensions
Fundamental limits of exact support recovery in high dimensions
复制标题
DOI：
10.3150/20-bej1197
复制
发表时间：
2018-11
期刊：
影响因子：
1.5
通讯作者：
Zhengyuan Gao;Stilian A. Stoev
中科院分区：
文献类型：
--
作者：
Zhengyuan Gao;Stilian A. Stoev
研究了具有加性噪声的高维信号的支撑恢复问题。通过对信号的稀疏度和非零分量的大小进行适当的参数化，我们描述了一个类似于Ingster在1998年研究的信号检测问题的相变现象。具体地说，如果信号的大小高于所谓的强分类边界，我们证明了几类众所周知的过程在维数趋于无穷时实现了渐近完美的支持恢复。这是如此，对于一个非常广泛的类的误差分布轻，快速变化的尾巴，可能有任意的依赖。相反，如果信号低于边界，那么对于非常广泛的一类误差依赖结构，没有阈值估计器（包括具有数据依赖阈值的阈值估计器）可以实现完美的支持恢复。这些结果的证明利用了一种称为相对稳定性的极大值的一定集中现象。我们从相关结构的角度给出了高斯三角形阵列相对稳定现象的完整表征。这个证明使用了经典的Sudakov-Fernique引理和Slepian引理论证以及Ramsey着色定理的奇妙应用。我们注意到，我们对强分类边界的研究是在更精细的，逐点的，而不是极小极大的意义上。我们还建立了阈值过程的贝叶斯最优性和次最优性。因此，我们得到了对数凹密度误差的强分类边界的极小型特征。
We study the support recovery problem for a high-dimensional signal observed with additive noise. With suitable parametrization of the signal sparsity and magnitude of its non-zero components, we characterize a phase-transition phenomenon akin to the signal detection problem studied by Ingster in 1998. Specifically, if the signal magnitude is above the so-called strong classification boundary, we show that several classes of well-known procedures achieve asymptotically perfect support recovery as the dimension goes to infinity. This is so, for a very broad class of error distributions with light, rapidly varying tails which may have arbitrary dependence. Conversely, if the signal is below the boundary, then for a very broad class of error dependence structures, no thresholding estimators (including ones with data-dependent thresholds) can achieve perfect support recovery. The proofs of these results exploit a certain concentration of maxima phenomenon known as relative stability. We provide a complete characterization of the relative stability phenomenon for Gaussian triangular arrays in terms their correlation structure. The proof uses classic Sudakov-Fernique and Slepian lemma arguments along with a curious application of Ramsey's coloring theorem. We note that our study of the strong classification boundary is in a finer, point-wise, rather than minimax, sense. We also establish the Bayes optimality and sub-optimality of thresholding procedures. Consequently, we obtain a minimax-type characterization of the strong classification boundary for errors with log-concave densities.