Minimax Estimation of Linear Functions of Eigenvectors in the Face of Small Eigen-Gaps

Abstract

Eigenvector perturbation analysis plays a vital role in various data science applications. A large body of prior works, however, focused on establishing ${\ell }_2$ eigenvector perturbation bounds, which are often highly inadequate in addressing tasks that rely on fine-grained behavior of an eigenvector. This paper makes progress on this by studying the perturbation of linear functions of an unknown eigenvector. Focusing on two fundamental problems -- matrix denoising and principal component analysis -- in the presence of Gaussian noise, we develop a suite of statistical theory that characterizes the perturbation of arbitrary linear functions of an unknown eigenvector. In order to mitigate a non-negligible bias issue inherent to the natural ``plug-in'' estimator, we develop de-biased estimators that (1) achieve minimax lower bounds for a family of scenarios (modulo some logarithmic factor), and (2) can be computed in a data-driven manner without sample splitting. Noteworthily, the proposed estimators are nearly minimax optimal even when the associated eigen-gap is {\em substantially smaller} than what is required in prior statistical theory.

References in corpus (10)

• Guaranteed Matrix Completion via Non-convex Factorization
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• Inference and Uncertainty Quantification for Noisy Matrix Completion
• Near-optimal bounds for phase synchronization
• Normal approximation and concentration of spectral projectors of sample covariance
• Unified ${\ell }_{2\to \infty }$ Eigenspace Perturbation Theory for Symmetric Random Matrices
• Statistically Optimal and Computationally Efficient Low Rank Tensor Completion from Noisy Entries
• Statistical Inferences of Linear Forms for Noisy Matrix Completion
• Asymptotic Theory of Eigenvectors for Random Matrices with Diverging Spikes
• An ${\ell }_p$ theory of PCA and spectral clustering

Cited by in corpus (3)

• Entrywise Estimation of Singular Vectors of Low-Rank Matrices with Heteroskedasticity and Dependence
• Inference for Heteroskedastic PCA with Missing Data
• Tackling small eigen-gaps: Fine-grained eigenvector estimation and inference under heteroscedastic noise