Improved dependence on coherence in eigenvector and eigenvalue estimation error bounds

Hao Yan, Keith LevinAISTATS 2025 · OpenReview

Abstract

Spectral estimators are fundamental in low-rank matrix models, yet their performance has historically been tied to the "coherence" of signal eigenvectors. This paper introduces a new matrix concentration inequality and a vector decomposition technique to establish estimation error bounds that significantly improve upon prior work. We demonstrate that coherence-free performance is achievable for a wide range of noise distributions, matching theoretical minimax lower bounds.

Introduction: The Coherence Problem

In statistical signal processing, recovering a signal matrix $M^*$ from a noisy observation $M = M^* + H$ is a core task. Spectral methods, which utilize the eigenvalues and eigenvectors of $M$, are standard for PCA, community detection, and matrix completion.

A significant challenge in the theoretical analysis of these methods is coherence ($\mu$), a measure of how concentrated a signal's eigenvectors are. Highly coherent ("spiky") signals were previously thought to suffer from significantly higher estimation errors. Most existing literature avoids this by assuming "incoherent" signals. This paper investigates whether this dependence is a fundamental algorithmic limit or a theoretical artifact, proving it is the latter.

Methodology

The authors utilize three primary mathematical innovations to bridge the gap between theory and empirical performance:

  1. The Neumann Trick: Expressing perturbed eigenvectors as an infinite series and controlling the terms precisely.
  2. Refined Combinatorial Analysis: Using graphical tools to analyze high-order moments of the noise matrix, allowing for more accurate bounding of noise impact.
  3. Novel Vector Decomposition: Breaking down unit vectors into $O(\log n)$ components with controlled $\ell_\infty$ norms. This allows the application of concentration results to arbitrary vectors, regardless of their original coherence.

Numerical Validation

The theoretical findings were validated using synthetic simulations across three setups: heteroskedastic Gaussian denoising, low-rank matrix completion, and random rank-one networks (Bernoulli noise).

Log-log plot of estimation error vs. matrix size. The parallel slopes demonstrate a consistent convergence rate across different coherence regimes, supporting the theory that the error rate is independent of coherence.

Key Insights

  • Decoupling Noise Parameters: The error depends on variance ($\sigma^2$) and tail behavior ($B$). Crucially, the impact of variance is shown to be independent of coherence.
  • Coherence-Free Bounds: If noise standard deviation is comparable to its subexponential norm, eigenvalue estimation error becomes entirely independent of coherence.
  • Optimality: The results match known minimax lower bounds under Gaussian noise up to logarithmic factors, suggesting near-optimal bounds.

Results and Discussion

The authors demonstrate that for rank-one matrices, the error $|\lambda - \lambda^*|$ is bounded by $\tilde{O}(\sigma)$ for sub-Gaussian noise, removing the $\sqrt{\mu/n}$ penalty found in previous state-of-the-art bounds.

Eigenvalue estimation error vs. matrix size for varying coherence levels. The overlapping trends confirm that the magnitude of error is largely unaffected by the "spikiness" of the signal.

As shown in the figures, while older theories predicted diverging error rates as coherence increased, experimental results show nearly parallel or overlapping lines. This confirms that spectral estimators are far more robust to coherent signals than previously mathematically guaranteed.

Limitations and Future Work

Current proofs require the noise distribution to be symmetric about zero. While empirical evidence suggests the results hold for asymmetric distributions (e.g., Bernoulli), formal proof remains for future work. Additionally, addressing the "bias" introduced by symmetric noise matrices and further optimizing multi-rank ($r > 1$) bounds regarding the eigen-gap and condition number are identified as key areas for continued research.

Summary updated

Abstract

Spectral estimators are fundamental in low-rank matrix models and arise throughout machine learning and statistics, with applications including network analysis, matrix completion and PCA. These estimators aim to recover the leading eigenvalues and eigenvectors of an unknown signal matrix observed subject to noise. While extensive research has addressed the statistical accuracy of spectral estimators under a variety of conditions, most previous work has assumed that the signal eigenvectors are incoherent with respect to the standard basis. This assumption typically arises because of suboptimal dependence on coherence in one or more concentration inequalities. Using a new matrix concentration result that may be of independent interest, we establish estimation error bounds for eigenvector and eigenvalue recovery whose dependence on coherence significantly improves upon prior work. Our results imply that coherence-free bounds can be achieved when the standard deviation of the noise is comparable to its Orlicz 1-norm (i.e., its subexponential norm). This matches known minimax lower bounds under Gaussian noise up to logarithmic factors.
BibTeX
@inproceedings{yan2025improved,
  author = {Hao Yan and Keith Levin},
  title = {{Improved dependence on coherence in eigenvector and eigenvalue estimation error bounds}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2025},
  url = {https://openreview.net/forum?id=ynLilizbOW},
}
Figure