Geometric bias in eigenspace perturbation under random heterogeneous noise

Technical Summary: Geometric Bias in Eigenspace Perturbation under Random Heterogeneous Noise

Problem Statement
Spectral methods, which rely on the stability of principal eigenspaces under random perturbations, are fundamental to extracting low-dimensional structure from high-dimensional noisy data. Classically, the stability of these eigenspaces is quantified by the Davis-Kahan and Wedin theorems. These theorems bound the eigenspace error using the operator norm of the noise and the relevant spectral gaps. While these worst-case bounds are sharp for arbitrary deterministic perturbations, the authors argue they are "wasteful" in the setting of low-rank signals corrupted by random noise. Specifically, classical bounds fail to capture the fine-grained interaction between the signal geometry and the noise distribution when the noise is heterogeneous (i.e., entries have independent but non-identically distributed variances).

The paper addresses the spectral perturbation of signal-plus-noise matrices $\tilde{A} = A + E$, where $A$ is a deterministic rank-$r$ signal and $E$ is a symmetric random noise matrix with an arbitrary, inhomogeneous variance profile $\Sigma = (\sigma_{ij}^2)$. The central problem is to understand how the variance profile induces a systematic, deterministic geometric bias in the empirical eigenvectors that is invisible to classical perturbation bounds.

Methodology
The authors employ a combination of random matrix theory techniques and deterministic analysis to derive non-asymptotic perturbation bounds. Key methodological components include:

1. Quadratic Vector Equation (QVE): The analysis leverages the QVE framework developed for general Wigner-type matrices. The authors utilize the deterministic solution $\Phi(z)$ to the QVE to approximate the resolvent (Green's function) $G(z) = (zI - E)^{-1}$ of the noise matrix.
2. Isotropic Local Laws: The paper establishes fine-grained isotropic local laws, which provide high-probability bounds on the difference between the random resolvent $G(z)$ and its deterministic approximation $\Phi(z)$ for arbitrary deterministic vectors.
3. Expansion of the Deterministic Approximation: By expanding $\Phi(z)$ for large $z$ (in the outlier regime), the authors isolate the deterministic contribution of the variance profile. Specifically, the expansion $\Phi(z) \approx z^{-1}I + z^{-3}R + \varepsilon(z)$ reveals that the diagonal matrix $R = \text{diag}(R_1, \dots, R_n)$, where $R_i = \sum_j \sigma_{ij}^2$, governs the bias.
4. Blockwise Eigenvector Equations: The proof strategy involves projecting the eigenvector equation $\tilde{A}\tilde{u}_s = \tilde{\lambda}_s \tilde{u}_s$ onto non-target signal directions and the null space. This decomposition separates the error into stochastic fluctuations (controlled by local laws) and deterministic bias terms (controlled by the alignment between signal eigenspaces and the variance profile).

Key Contributions and Results
The paper derives near-optimal, non-asymptotic perturbation bounds for the leading eigenspaces in both the operator norm and the $2 \to \infty$ norm. The primary contributions are:

• Identification of Geometric Bias: The authors demonstrate that under heterogeneous noise, empirical eigenvectors suffer a systematic bias determined by the matrix $V = U^T R U$, where $U$ contains the population eigenvectors. Even if population eigenvectors are orthogonal in the standard inner product, they are generally not orthogonal with respect to the variance-weighted inner product induced by $R$.
• Decomposition of Error Terms: The derived bounds explicitly separate three distinct contributions:
  1. The standard signal-to-noise ratio term (proportional to $\|E\|/\lambda_k$).
  2. Stochastic fluctuations controlled by isotropic local laws (proportional to $M_D/\delta_k$).
  3. A deterministic geometric bias term ($B_k$) determined by the alignment between the signal eigenspaces and the row-wise variance profile.
• Explicit Bias Formulas: For the top-$k$ eigenspace, the bias term $B_k$ is shown to depend on quantities like $\|V_{JI}\|$ (interaction between the top-$k$ block and the remaining positive spikes) and $\|V_{NK}\|$ (interaction with negative spikes), scaled by spectral gaps. The bounds show that in homogeneous settings ($R = cI$), these bias terms vanish, recovering known results up to logarithmic factors.
• Sharpness and Numerical Validation: The paper provides numerical experiments on a rank-2 model confirming that the geometric bias is a deterministic effect, not a random artifact. The empirical alignment of eigenvectors matches the theoretical prediction $\Delta / (\lambda_1 \delta_1)$, where $\Delta$ represents the heterogeneity in the variance profile.
• Oracle De-biasing: The authors propose an "oracle" correction procedure that removes the leading $V_{JI}$-bias term. This procedure uses the known population eigenspace to subtract the deterministic contribution predicted by the QVE expansion. While the oracle estimator is not directly implementable (as it requires population parameters), it serves to prove that the bias is removable and distinct from stochastic noise. A "plug-in" version is discussed, though the paper notes its limitations regarding ill-conditioning when spikes are weak or clustered.

Significance and Claims
The paper claims to move beyond worst-case perturbation theory by identifying a specific mechanism—variance-profile induced geometric bias—that classical bounds overlook. The authors state that their results are significant because:

• They provide a more precise characterization of eigenspace stability in heterogeneous noise regimes, which are common in statistical models like stochastic block models with varying edge probabilities.
• They demonstrate that the "wastefulness" of classical bounds in random settings is not merely due to stochastic concentration but also due to a deterministic structural bias.
• The derived bounds are near-optimal and non-asymptotic, separating the noise contributions in a way that allows for potential bias correction strategies.

The authors remain modest regarding the practical implementation of bias correction, noting that the "plug-in" de-biasing procedure is limited by the need to accurately estimate lower-rank spikes and the potential ill-conditioning of the correction matrices when spectral gaps are small. They explicitly state that developing optimal, fully data-driven bias correction methods is left for future work. The paper does not claim to solve all problems in spectral methods but rather to refine the theoretical understanding of eigenspace perturbation under a specific, realistic noise model.