On the Condition Number of the Shifted Real Ginibre Ensemble

Giorgio Cipolloni, László Erdös, Dominik Schröder

TL;DR

Real random matrices typically suffer from "worse" numerical stability than their complex counterparts, with condition numbers that decay slowly. This paper proves that simply shifting a real Ginibre matrix by a complex number $z$ causes it to inherit the superior stability of complex matrices, resolving a recent conjecture and providing sharper bounds for numerical algorithms.

What Problem Does This Paper Address?

In numerical linear algebra, the condition number $\kappa(X)$ is a vital metric. It tells you how much an error in your input (like rounding error) will be amplified in your output. High condition numbers mean "ill-conditioned" problems where results are unreliable.

There is a well-known discrepancy in Random Matrix Theory (RMT): if you take a large matrix $X$ with independent Gaussian entries (a Ginibre ensemble), the probability that it is ill-conditioned is much higher if the entries are real than if they are complex. Specifically, the "tail" of the distribution for real matrices decays as $1/t$, while for complex matrices, it decays much faster, as $1/t^2$.

The authors investigate the shifted real Ginibre ensemble $(X - zI)$. They ask: if we take a real matrix and shift it by a complex number $z$, does it start behaving like a complex matrix? This isn't just a theoretical curiosity; it has deep implications for "smoothed analysis," a framework used to explain why certain algorithms (like the simplex method or Gaussian elimination) work well in practice despite poor worst-case theoretical bounds.

Methods

The paper employs a sophisticated blend of mathematical physics and probability theory:

  • Supersymmetric (SUSY) Analysis: This is the "heavy hitter" of the paper. Originating in theoretical physics, the SUSY method allows the authors to reduce a high-dimensional integral over $N \times N$ matrices into a much simpler 3-fold integral. This allows for extremely precise estimates that are difficult to obtain through standard probabilistic tools.
  • Green Function Comparison (GFT): While the primary results are derived for Gaussian entries, the authors use GFT to show that their bounds hold more generally for matrices with other entry distributions (like Bernoulli), provided they have the same first few moments.
  • Numerical Simulations: To validate their theoretical proofs, the authors ran Monte Carlo simulations using 10,000 random matrices of size $100 \times 100$, plotting the complementary cumulative distribution functions (CCDF) to visualize the tail behavior.

Datasets

As a theoretical RMT paper, it does not use external real-world datasets. Instead, it generates:

  • Real Ginibre Matrices: $N \times N$ matrices with i.i.d. real Gaussian entries.
  • Complex Ginibre Matrices: $N \times N$ matrices with i.i.d. complex Gaussian entries.
  • Bernoulli Matrices: Used to test the universality of the results beyond the Gaussian case.

Key Insights and Ideas

  • The $N^{-1/2}$ Threshold: The "magic" happens when the imaginary part of the shift $z$ is significantly larger than $N^{-1/2}$. At this scale, the real matrix "forgets" its real-valued origins and its condition number tail transitions from $1/t$ to the more desirable $1/t^2$.
  • Resolving the Banks et al. Conjecture: A previous work by Banks et al. (2020) conjectured this regularizing effect but provided a bound that was not optimal. This paper provides the sharpest possible bound, confirming the conjecture and refining the scaling.
  • Eigenvector Overlaps: The paper links the condition number of the matrix to the "eigenvector condition number" (or overlaps). It shows that complex shifts prevent the "fat tails" of eigenvector instability that plague real matrices near the real axis.
  • Algorithmic Impact: The authors demonstrate that this isn't just abstract math. In tests of the Conjugate Gradient (CG) algorithm, real matrices with real shifts converged significantly slower and with more fluctuation than those with complex shifts.

Key Results

  • Theorem 2.1: Provides a precise lower tail estimate for the smallest singular value $\sigma_1(X - z)$. It includes an exponential suppression factor $\exp(-\frac{1}{2}N\eta^2)$ (where $\eta$ is the imaginary part of $z$) that explicitly captures the transition between symmetry classes.
  • Condition Number Tail: The probability $P(\kappa(X - z) \ge t)$ is shown to transition from $\sim 1/t$ to $\sim 1/t^2$ as the shift $z$ moves away from the real axis.
  • Improved Eigenvector Bounds: The authors derive an improved upper bound on the eigenvalue condition numbers, showing they scale as $N^{3/2} \sqrt{\log N}$ in the worst case, though they note that in practice, the scaling is likely even better (linear in $N$).

Limitations and Future Work

  • Deterministic Matrix $A$: Most of the paper focuses on the case where the "perturbation" is a simple shift $zI$. The authors propose Conjecture 2.4, suggesting that this regularizing effect should hold for any deterministic matrix $A$ added to a real Ginibre matrix, provided $A$ is "sufficiently complex" in a way they quantify via the trace of its anti-Hermitian part.
  • Non-Gaussian Universality: While they provide a path toward universality (Remark 2.3), the most precise results still rely on the Gaussian nature of the entries for the SUSY machinery to work perfectly. Extending the full precision of the SUSY results to general distributions remains a challenge.
  • Closing the $N$ Gap: There is still a small gap between the theoretical upper bound for the eigenvector condition number ($\kappa_v$) and the empirically observed linear scaling. Closing this gap is a noted direction for future research.

Summary updated

Abstract

We derive an accurate lower tail estimate on the lowest singular value $σ_1(X-z)$ of a real Gaussian (Ginibre) random matrix $X$ shifted by a complex parameter $z$. Such shift effectively changes the upper tail behaviour of the condition number $κ(X-z)$ from the slower $\mathbf{P}(κ(X-z)\ge t)\lesssim 1/t$ decay typical for real Ginibre matrices to the faster $1/t^2$ decay seen for complex Ginibre matrices as long as $z$ is away from the real axis. This sharpens and resolves a recent conjecture in [arXiv:2005.08930] on the regularizing effect of the real Ginibre ensemble with a genuinely complex shift. As a consequence we obtain an improved upper bound on the eigenvalue condition numbers (known also as the eigenvector overlaps) for real Ginibre matrices. The main technical tool is a rigorous supersymmetric analysis from our earlier work [arXiv:1908.01653].
BibTeX
@article{cipolloni2022condition,
  author = {Giorgio Cipolloni and László Erdös and Dominik Schröder},
  title = {{On the Condition Number of the Shifted Real Ginibre Ensemble}},
  journal = {SIAM J. Matrix Anal. Appl},
  year = {2022},
  doi = {10.1137/21m1424408},
}
Figure