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

arXiv: https://arxiv.org/abs/2001.04620 · HTML: https://mlsanity.com/paper/2001.04620/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Jan 2020.

## Built on by (most cited first, 9 of 9)

- [Inference for Heteroskedastic PCA with Missing Data](https://mlsanity.com/paper/2107.12365/) (2021)
- [Subspace Recovery from Heterogeneous Data with Non-isotropic Noise](https://mlsanity.com/paper/2210.13497/) (2022)
- [Approximate message passing from random initialization with applications to mathbbZ2 synchronization](https://mlsanity.com/paper/2302.03682/) (2023)
- [Deflated HeteroPCA: Overcoming the curse of ill-conditioning in heteroskedastic PCA](https://mlsanity.com/paper/2303.06198/) (2023)
- [Optimal Estimation and Computational Limit of Low-rank Gaussian Mixtures](https://mlsanity.com/paper/2201.09040/) (2022)
- [Matrix Denoising with Doubly Heteroscedastic Noise: Fundamental Limits and Optimal Spectral Methods](https://mlsanity.com/paper/2405.13912/) (2024)
- [Boosted Control Functions: Distribution generalization and invariance in confounded models](https://mlsanity.com/paper/2310.05805/) (2023)
- [Minimax Estimation of Linear Functions of Eigenvectors in the Face of Small Eigen-Gaps](https://mlsanity.com/paper/2104.03298/) (2021)
- [Counting Cycles with AI: Counting Cycles with AI: Computationally Efficient Equivalent Forms with Applications](https://mlsanity.com/paper/2505.17964/) (2025)

## Abstract (arXiv)

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 ℓ2 analysis. We investigate how to address these challenges in a setting where the unknown n× 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(√n/polylog (n)) times smaller than the requirement in prior theory), which goes significantly beyond what generic matrix perturbation theory has to offer.