Geometric bias in eigenspace perturbation under random heterogeneous noise

Fengkai Liu; Ke Wang; Wanjie Wang

math.STJun 9, 2026

Geometric bias in eigenspace perturbation under random heterogeneous noise

Authors: Fengkai Liu, Ke Wang, Wanjie Wang

Abstract

Spectral methods rely fundamentally on the stability of principal eigenspaces under random perturbations. Classically, this stability is quantified by the Davis-Kahan and Wedin theorems, which 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, they can be wasteful in the low-rank signal-plus-random-noise setting, as they fail to capture the fine-grained interaction between the signal geometry and the noise distribution. In this paper, we study the spectral perturbation of signal-plus-noise matrices corrupted by sparse, random noise with an arbitrary, inhomogeneous variance profile. We demonstrate that under heterogeneous noise variances, the empirical eigenvectors suffer a systematic, deterministic geometric bias that is entirely invisible to classical perturbation bounds. By leveraging the Quadratic Vector Equation (QVE) and establishing fine-grained isotropic local laws, we derive near-optimal, non-asymptotic perturbation bounds for the leading eigenspaces in the operator and $2\to\infty$ norms. The bounds separate the usual signal-to-noise contribution, stochastic fluctuations, and structured geometric bias terms determined by the alignment between the signal eigenspaces and the row-wise variance profile.

Explore similar work

Apr 25, 2026cs.DS

Well-Conditioned Oblivious Perturbations in Linear Space

Perturbing a deterministic

n

-dimensional matrix with small Gaussian noise is a cornerstone of smoothed analysis of algorithms [Spielman and Teng, JACM 2004], as it reduces the condition number of the input to

O(n)

, and with it the complexity of many matrix algorithms. However, when deployed algorithmically, these perturbations are expensive due to the cost of generating and storing

n^2

Gaussian random variables. We propose a perturbation that requires generating and storing

O(n)

random numbers in

O(\log n)

bits of precision, and reduces the condition number of any deterministic matrix to

O(n)

, matching Gaussian perturbations. Our result in particular implies a better complexity for the perturbed conjugate gradient algorithm, showing that we can solve an

n\times n

linear system in linear space to within an arbitrarily small constant backward error using

O(n)

matrix-vector products. In our construction, we introduce the concept of a pattern matrix, which is a dense deterministic matrix that maps all sparse vectors into dense vectors, and we combine it with a sparse perturbation whose entries are dependent and located in a non-uniform fashion. In order to analyze this construction, we develop new techniques for lower bounding the smallest singular value of a random matrix with dependent entries.

Shabarish Chenakkod, Michał Dereziński, Xiaoyu Dong +1

Spectral Preconditioning Optimal Sample Complexity Perturbations Smoothing

Ask PDF

May 27, 2026math.OC

Implicit Regularization in Perturbed Deep Matrix Factorization: Spectral Conditions and Stability

This paper studies the stability of low-rank implicit regularization in perturbed deep matrix factorization, where the target matrix is corrupted by a noise matrix. We first derive sufficient spectral conditions under which gradient descent exhibits a low-rank phase in the noiseless setting. These conditions show how the target spectrum, initialization, and step size jointly determine the existence of a nonempty low-rank interval. We then analyze the perturbed gradient descent dynamics, proving convergence guarantees and quantifying how the perturbation affects iteration complexity and eigenvalue recovery. Finally, we show that the low-rank phase persists under perturbation, with explicit dependence on the perturbation size. Numerical experiments support the theoretical findings.

Jingzhe Wang, Hung-Hsu Chou

Low-Rank Factorization Matrix Factorization Regularization Techniques

Ask PDF

Sep 27, 2024math.NA

Probabilistic Analysis of Least Squares, Orthogonal Projection, and QR Factorization Algorithms Subject to Gaussian Noise

We consider the effect of Gaussian perturbations on least-squares residuals, orthogonal projections, and QR-type algorithms. The problem that motivated our investigations is as follows: suppose that a full column-rank matrix

B\in\mathbb{R}^{m\times n}

has already been computed, and suppose that a new normalized column

q=(x+y)/\|x+y\|_2

is to be appended to

B

, where

x\perp\operatorname{span}(B)

is the ideal orthogonal component and

y

represents the orthogonalization error. How large can the condition number

κ([B,q])

of the resulting matrix

[B,q]

become? While we provide a Weyl-type bound on the singular values of

[B,q]

, in terms of the extremal singular values of

B

and the quantity

\|B^T y\|_2/\|x+y\|_2

, we also derive exact probability laws for norms and projection residuals under Gaussian perturbations. Finally, we use these probability laws to derive probabilistic condition-number bounds for QR-type processes with imperfect orthogonalization and exact normalization.

Ali Lotfi, Julien Langou, Mohammad Meysami

Singular Value Decomposition Orthogonality Least Squares Low-Rank Factorization Universal Factorization Problem Gaussian Noise+1

Ask PDF