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:
- The Neumann Trick: Expressing perturbed eigenvectors as an infinite series and controlling the terms precisely.
- Refined Combinatorial Analysis: Using graphical tools to analyze high-order moments of the noise matrix, allowing for more accurate bounding of noise impact.
- 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).
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.
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