Tackling Small Eigen-Gaps: Fine-Grained Eigenvector Estimation and Inference Under Heteroscedastic Noise
Tackling Small Eigen-Gaps: Fine-Grained Eigenvector Estimation and Inference Under Heteroscedastic Noise
复制标题
DOI：
10.1109/tit.2021.3111828
复制
发表时间：
2021-11-01
影响因子：
2.5
通讯作者：
Chen, Yuxin
中科院分区：
文献类型：
--
作者：
Cheng, Chen;Wei, Yuting;Chen, Yuxin
本文旨在解决噪声观察的特征向量估计和低级矩阵的推断时引起的两个基本挑战：1）如何估计当特征差异时（即相关特征和其他特征值之间的间距）时如何估计未知的特征向量。频谱特别小； 2）如何对特征向量的线性功能进行估计和推断 - 一种“细粒”统计推理远远超出了通常的L（2）分析。我们研究了如何在未知NXN矩阵对称的环境中解决这些挑战，而添加噪声矩阵包含独立（和非对称）条目。基于非对称数据矩阵的本征分解，我们提出了未知特征向量的估计和不确定性量化程序，这进一步使我们能够理解未知特征向量的线性函数。提出的程序和随附的理论享有几个重要特征：1）无分布（即，不需要关于噪声分布的先验知识）； 2）适应异性噪声； 3）在高斯噪声下的最小值最佳。在此过程中，我们建立了有效的程序来为未知特征值构建置信区间。即使存在一个小的特征差距（o（根N/poly log（n））比先前理论中的要求小（根N/poly log（n）），所有这些都可以保证，这大大超出了通用矩阵扰动理论所能提供的。 。
This paper aims to address two fundamental challenges arising in eigenvector estimation and inference for a low-rank matrix from noisy observations: 1) how to estimate an unknown eigenvector when the eigen-gap (i. e. the spacing between the associated eigenvalue and the rest of the spectrum) is particularly small; 2) how to perform estimation and inference on linear functionals of an eigenvector-a sort of "fine-grained" statistical reasoning that goes far beyond the usual l(2) analysis. We investigate how to address these challenges in a setting where the unknown nxn matrix is symmetric and the additive noise matrix contains independent (and non-symmetric) entries. Based on eigen-decomposition of the asymmetric data matrix, we propose estimation and uncertainty quantification procedures for an unknown eigenvector, which further allow us to reason about linear functionals of an unknown eigenvector. The proposed procedures and the accompanying theory enjoy several important features: 1) distribution-free (i.e. prior knowledge about the noise distributions is not needed); 2) adaptive to heteroscedastic noise; 3) minimax optimal under Gaussian noise. Along the way, we establish valid procedures to construct confidence intervals for the unknown eigenvalues. All this is guaranteed even in the presence of a small eigen-gap (up to O(root n/poly log(n)) times smaller than the requirement in prior theory), which goes significantly beyond what generic matrix perturbation theory has to offer.