This paper has been withdrawn by Phuc Tran

No PDF available, click to view other formats

Abstract:Let $A$ be a full ranked $ n\times n$ matrix, with singular values $\sigma_1 (A) \ge \dots \ge \sigma_n (A) >0$. The condition number $\kappa(A):= \sigma_1(A)/\sigma_n(A)=\|A\|\cdot \|A\|^{-1}$ is a key parameter in the analysis of algorithms taking $A$ as input. In practice, matrices (representing real data) are often perturbed by noise. Technically speaking, the real input would be a noisy variant $\tilde A =A +E$ of $A$, where $E$ represents the noise. The condition number $\kappa (\tilde A)$ will be used instead of $\kappa (A)$. Thus, it is of importance to measure the impact of noise on the condition number.
In this paper, we focus on the case when the noise is random. We introduce the notion of regional stability, via which we design a new framework to estimate the perturbation of the extremal singular values and the condition number of a matrix. Our framework allows us to bound the perturbation of singular values through the perturbation of singular spaces. We then bound the latter using a novel contour analysis argument, which, as a co-product, provides an improved version of the classical Davis-Kahan theorem in many settings.
Our new estimates concerning the least singular value $\sigma_n(A)$ complement well-known results in this area, and are more favorable in the case when the ground matrix $A$ is large compared to the noise matrix $E$.

Submission history

From: Phuc Tran [view email]
[v1] Fri, 20 Mar 2026 08:42:36 UTC (53 KB)
[v2] Mon, 6 Apr 2026 14:52:49 UTC (53 KB)
[v3] Tue, 8 Sep 2026 12:02:35 UTC (1 KB) (withdrawn)