On the condition number of the shifted real Ginibre ensemble. (English) Zbl 1496.15025
Summary: We derive an accurate lower tail estimate on the lowest singular value \(\sigma_1(X-z)\) of a real Gaussian (Ginibre) random matrix \(X\) shifted by a complex parameter \(z\). Such shift effectively changes the upper tail behavior of the condition number \(\kappa(X-z)\) from the slower \((\kappa(X-z)\geq 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 [J. Banks et al., “Overlaps, eigenvalue gaps, and pseudospectrum under real Ginibre and absolutely continuous perturbations”, Preprint, 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 [G. Cipolloni et al., Probab. Math. Phys. 1, No. 1, 101–146 (2020; Zbl 1485.15041)].
MSC:
| 15B52 | Random matrices (algebraic aspects) |
| 15A12 | Conditioning of matrices |
| 60B20 | Random matrices (probabilistic aspects) |
| 68W40 | Analysis of algorithms |
| 65F35 | Numerical computation of matrix norms, conditioning, scaling |
Citations:
Zbl 1485.15041Software:
numericaluniversalityReferences:
| [1] | J. Alt, L. Erdös, and T. Krüger, Spectral radius of random matrices with independent entries, Probab. Math. Phys., 2 (2019), pp. 221-280, https://doi.org/10.2140/pmp.2021.2.221. |
| [2] | D. Armentano, C. Beltrán, P. Bürgisser, F. Cucker, and M. Shub, A stable, polynomial-time algorithm for the eigenpair problem, J. Eur. Math. Soc. (JEMS), 20 (2018), pp. 1375-1437, https://doi.org/10.4171/JEMS/789. · Zbl 1401.65034 |
| [3] | J.-M. Azaïs and M. Wschebor, Upper and lower bounds for the tails of the distribution of the condition number of a Gaussian matrix, SIAM J. Matrix Anal. Appl., 26 (2004/05), pp. 426-440, https://doi.org/10.1137/S0895479803429764. · Zbl 1088.15007 |
| [4] | Z. D. Bai, Circular law, Ann. Probab., 25 (1997), pp. 494-529, https://doi.org/10.1214/aop/1024404298. · Zbl 0871.62018 |
| [5] | Z. D. Bai and Y. Q. Yin, Limiting behavior of the norm of products of random matrices and two problems of Geman-Hwang, Probab. Theory Related Fields, 73 (1986), pp. 555-569, https://doi.org/10.1007/BF00324852. · Zbl 0586.60021 |
| [6] | J. Banks, J. Garza-Vargas, A. Kulkarni, and N. Srivastava, Pseudospectral shattering, the sign function, and diagonalization in nearly matrix multiplication time, in 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), 2020, pp. 529-540. |
| [7] | J. Banks, A. Kulkarni, S. Mukherjee, and N. Srivastava, Gaussian regularization of the pseudospectrum and Davies’ conjecture, Comm. Pure Appl. Math., 74 (2021), pp. 2114-2131. · Zbl 1480.15014 |
| [8] | J. Banks, J. G. Vargas, A. Kulkarni, and N. Srivastava, Overlaps, Eigenvalue Gaps, and Pseudospectrum Under Real Ginibre and Absolutely Continuous Perturbations, preprint, https://arxiv.org/abs/2005.08930, 2020. |
| [9] | F. A. Berezin, Introduction to Superanalysis, Math. Phys. Appl. Math. 9, A. A. Kirillov, ed., D. Reidel, Dordrecht, 1987, https://doi.org/10.1007/978-94-017-1963-6. · Zbl 0659.58001 |
| [10] | C. Bordenave, P. Caputo, D. Chafaï, and K. Tikhomirov, On the spectral radius of a random matrix: An upper bound without fourth moment, Ann. Probab., 46 (2018), pp. 2268-2286, https://doi.org/10.1214/17-AOP1228. · Zbl 1393.05130 |
| [11] | C. Bordenave, D. Chafaï, and D. García-Zelada, Convergence of the spectral radius of a random matrix through its characteristic polynomial, Probab. Theory Related Fields, 182 (2022), pp. 1163-1181. · Zbl 1492.30022 |
| [12] | A. Borodin and C. D. Sinclair, The Ginibre ensemble of real random matrices and its scaling limits, Comm. Math. Phys., 291 (2009), pp. 177-224, https://doi.org/10.1007/s00220-009-0874-5. · Zbl 1184.82004 |
| [13] | P. Bourgade and G. Dubach, The distribution of overlaps between eigenvectors of Ginibre matrices, Probab. Theory Related Fields, 177 (2020), pp. 397-464, https://doi.org/10.1007/s00440-019-00953-x. · Zbl 1451.60015 |
| [14] | J. T. Chalker and B. Mehlig, Eigenvector statistics in non-Hermitian random matrix ensembles, Phys. Rev. Lett., 81 (1998), pp. 3367-3370, https://doi.org/10.1103/PhysRevLett.81.3367. |
| [15] | Z. Chen and J. J. Dongarra, Condition numbers of Gaussian random matrices, SIAM J. Matrix Anal. Appl., 27 (2005), pp. 603-620, https://doi.org/10.1137/040616413. · Zbl 1107.15016 |
| [16] | G. Cipolloni, L. Erdös, and D. Schröder, Density of small singular values of the shifted real Ginibre ensemble, Ann. Henri Poincaré, (2022), https://doi.org/10.1007/s00023-022-01188-8. · Zbl 1485.15041 |
| [17] | G. Cipolloni, L. Erdös, and D. Schröder, Edge universality for non-Hermitian random matrices, Probab. Theory Related Fields, 179 (2021), pp. 1-28, https://doi.org/10.1007/s00440-020-01003-7. · Zbl 1461.60008 |
| [18] | G. Cipolloni, L. Erdös, and D. Schröder, Fluctuation around the circular law for random matrices with real entries, Electron. J. Probab., 26 (2021), 24, https://doi.org/10.1214/21-EJP591. · Zbl 1477.60016 |
| [19] | G. Cipolloni, L. Erdös, and D. Schröder, Optimal lower bound on the least singular value of the shifted Ginibre ensemble, Probab. Math. Phys., 1 (2020), pp. 101-146, https://doi.org/10.2140/pmp.2020.1.101. · Zbl 1485.15041 |
| [20] | P. A. Deift, G. Menon, S. Olver, and T. Trogdon, Universality in numerical computations with random data, Proc. Natl. Acad. Sci. USA, 111 (2014), pp. 14973-14978, https://doi.org/10.1073/pnas.1413446111. · Zbl 1355.65019 |
| [21] | J. W. Demmel, The probability that a numerical analysis problem is difficult, Math. Comp., 50 (1988), pp. 449-480, https://doi.org/10.2307/2008617. · Zbl 0657.65066 |
| [22] | A. Edelman, Eigenvalues and condition numbers of random matrices, SIAM J. Matrix Anal. Appl., 9 (1988), pp. 543-560, https://doi.org/10.1137/0609045. · Zbl 0678.15019 |
| [23] | A. Edelman and B. D. Sutton, Tails of condition number distributions, SIAM J. Matrix Anal. Appl., 27 (2005), pp. 547-560, https://doi.org/10.1137/040614256. · Zbl 1093.15010 |
| [24] | Y. V. Fyodorov, On statistics of bi-orthogonal eigenvectors in real and complex Ginibre ensembles: Combining partial Schur decomposition with supersymmetry, Comm. Math. Phys., 363 (2018), pp. 579-603, https://doi.org/10.1007/s00220-018-3163-3. · Zbl 1448.60022 |
| [25] | S. Ge, The Eigenvalue Spacing of IID Random Matrices and Related Least Singular Value Results, Ph.D. thesis, UCLA, 2017, https://escholarship.org/uc/item/1n542603. |
| [26] | S. Geman, The spectral radius of large random matrices, Ann. Probab., 14 (1986), pp. 1318-1328, http://links.jstor.org/sici?sici=0091-1798(198610)14:4<1318:TSROLR>2.0.CO;2-O&origin=MSN. · Zbl 0605.60037 |
| [27] | V. L. Girko, The circular law, Teor. Veroyatn. Primen., 29 (1984), pp. 669-679. · Zbl 0565.60034 |
| [28] | H. H. Goldstine and J. von Neumann, Numerical inverting of matrices of high order. II, Proc. Amer. Math. Soc., 2 (1951), pp. 188-202, https://doi.org/10.2307/2032484. · Zbl 0043.12301 |
| [29] | A. Greenbaum, Behavior of slightly perturbed Lanczos and conjugate-gradient recurrences, Linear Algebra Appl., 113 (1989), pp. 7-63, https://doi.org/10.1016/0024-3795(89)90285-1. · Zbl 0662.65032 |
| [30] | A. Greenbaum and Z. Strakoš, Predicting the behavior of finite precision Lanczos and conjugate gradient computations, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 121-137, https://doi.org/10.1137/0613011. · Zbl 0755.65037 |
| [31] | W. Hackbusch, Iterative Solution of Large Sparse Systems of Equations, Appl. Math. Sci. 95, Springer, Cham, 2016, https://doi.org/10.1007/978-3-319-28483-5. · Zbl 1347.65063 |
| [32] | M. R. Hestenes and E. Stiefel, Methods of conjugate gradients for solving linear systems, J. Research Nat. Bur. Standards, 49 (1952), pp. 409-436 (1953). · Zbl 0048.09901 |
| [33] | V. Jain, A. Sah, and M. Sawhney, On the real Davies’ conjecture, Ann. Probab., 49 (2021), pp. 3011-3031. · Zbl 1486.15013 |
| [34] | P. Littelmann, H.-J. Sommers, and M. R. Zirnbauer, Superbosonization of invariant random matrix ensembles, Comm. Math. Phys., 283 (2008), pp. 343-395, https://doi.org/10.1007/s00220-008-0535-0. · Zbl 1156.82008 |
| [35] | K. Luh and S. O’Rourke, Eigenvectors and controllability of non-Hermitian random matrices and directed graphs, Electron. J. Probab., 26 (2021), 16, https://doi.org/10.3390/mca26010016. · Zbl 1470.15033 |
| [36] | B. Mehlig and J. T. Chalker, Statistical properties of eigenvectors in non-Hermitian Gaussian random matrix ensembles, J. Math. Phys., 41 (2000), pp. 3233-3256, https://doi.org/10.1063/1.533302. · Zbl 0977.82023 |
| [37] | A. Sankar, D. A. Spielman, and S.-H. Teng, Smoothed analysis of the condition numbers and growth factors of matrices, SIAM J. Matrix Anal. Appl., 28 (2006), pp. 446-476, https://doi.org/10.1137/S0895479803436202. · Zbl 1179.65033 |
| [38] | D. A. Spielman and S.-H. Teng, Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time, J. ACM, 51 (2004), pp. 385-463, https://doi.org/10.1145/990308.990310. · Zbl 1192.90120 |
| [39] | T. Tao and V. Vu, Random matrices: The circular law, Commun. Contemp. Math., 10 (2008), pp. 261-307, https://doi.org/10.1142/S0219199708002788. · Zbl 1156.15010 |
| [40] | L. N. Trefethen and M. Embree, Spectra and Pseudospectra, Princeton University Press, Princeton, NJ, 2005. · Zbl 1085.15009 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
