Tackling small eigen-gaps: Fine-grained eigenvector estimation and inference under heteroscedastic noise

Abstract

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 ${\ell }_2$ analysis. We investigate how to address these challenges in a setting where the unknown $n\times n$ 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 optimal 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(\sqrt{n/\mathrm{poly}\log (n)})$ times smaller than the requirement in prior theory), which goes significantly beyond what generic matrix perturbation theory has to offer.

arXiv commentaccepted to IEEE Transactions on Information Theory, 2021; 69 pages

References in corpus (20)

• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• Asymptotic normality and optimalities in estimation of large Gaussian graphical models
• Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
• Eigenvector statistics in non-Hermitian random matrix ensembles
• Minimax risk of matrix denoising by singular value thresholding
• Inference and Uncertainty Quantification for Noisy Matrix Completion
• Localization from Incomplete Noisy Distance Measurements
• Inference for High-Dimensional Sparse Econometric Models
• The distribution of the Lasso: Uniform control over sparse balls and adaptive parameter tuning
• The Lasso with general Gaussian designs with applications to hypothesis testing
• Non-Hermitean De-Localization: Multiple Scattering and Bounds
• Uncertainty Quantification for Matrix Compressed Sensing and Quantum Tomography Problems
• De-biased sparse PCA: Inference and testing for eigenstructure of large covariance matrices
• Eigenvector Under Random Perturbation: A Nonasymptotic Rayleigh-Schrödinger Theory
• Outlier eigenvalue fluctuations of perturbed iid matrices
• Adapting to Unknown Noise Distribution in Matrix Denoising
• Inference for Heteroskedastic PCA with Missing Data
• Minimax Estimation of Linear Functions of Eigenvectors in the Face of Small Eigen-Gaps