The conjugate gradient algorithm on a general class of spiked covariance matrices
Authors:
Xiucai Ding and Thomas Trogdon
Journal:
Quart. Appl. Math. 80 (2022), 99-155
MSC (2020):
Primary 65F10, 60B20
DOI:
https://doi.org/10.1090/qam/1605
Published electronically:
November 19, 2021
MathSciNet review:
4360552
Full-text PDF
Abstract |
References |
Similar Articles |
Additional Information
Abstract: We consider the conjugate gradient algorithm applied to a general class of spiked sample covariance matrices. The main result of the paper is that the norms of the error and residual vectors at any finite step concentrate on deterministic values determined by orthogonal polynomials with respect to a deformed Marchenko–Pastur law. The first-order limits and fluctuations are shown to be universal. Additionally, for the case where the bulk eigenvalues lie in a single interval we show a stronger universality result in that the asymptotic rate of convergence of the conjugate gradient algorithm only depends on the support of the bulk, provided the spikes are well-separated from the bulk. In particular, this shows that the classical condition number bound for the conjugate gradient algorithm is pessimistic for spiked matrices.
References
- Zhidong Bai and Jack W. Silverstein, Spectral analysis of large dimensional random matrices, 2nd ed., Springer Series in Statistics, Springer, New York, 2010. MR 2567175, DOI 10.1007/978-1-4419-0661-8
- Z. D. Bai, B. Q. Miao, and G. M. Pan, On asymptotics of eigenvectors of large sample covariance matrix, Ann. Probab. 35 (2007), no. 4, 1532–1572. MR 2330979, DOI 10.1214/009117906000001079
- Z. Bao, X. Ding, J. Wang, and K. Wang, Statistical inference for principal components of spiked covariance matrices, arXiv preprint arXiv:arXiv:2008.11903, 2020.
- Bernhard Beckermann and Arno B. J. Kuijlaars, Superlinear convergence of conjugate gradients, SIAM J. Numer. Anal. 39 (2001), no. 1, 300–329. MR 1860727, DOI 10.1137/S0036142999363188
- Serban T. Belinschi, Hari Bercovici, Mireille Capitaine, and Maxime Février, Outliers in the spectrum of large deformed unitarily invariant models, Ann. Probab. 45 (2017), no. 6A, 3571–3625. MR 3729610, DOI 10.1214/16-AOP1144
- Alex Bloemendal, Antti Knowles, Horng-Tzer Yau, and Jun Yin, On the principal components of sample covariance matrices, Probab. Theory Related Fields 164 (2016), no. 1-2, 459–552. MR 3449395, DOI 10.1007/s00440-015-0616-x
- Alex Bloemendal and Bálint Virág, Limits of spiked random matrices I, Probab. Theory Related Fields 156 (2013), no. 3-4, 795–825. MR 3078286, DOI 10.1007/s00440-012-0443-2
- P. A. Deift, Orthogonal polynomials and random matrices: a Riemann-Hilbert approach, Courant Lecture Notes in Mathematics, vol. 3, New York University, Courant Institute of Mathematical Sciences, New York; American Mathematical Society, Providence, RI, 1999. MR 1677884
- P. Deift, T. Kriecherbauer, K. T.-R. McLaughlin, S. Venakides, and X. Zhou, Uniform asymptotics for polynomials orthogonal with respect to varying exponential weights and applications to universality questions in random matrix theory, Comm. Pure Appl. Math. 52 (1999), no. 11, 1335–1425. MR 1702716, DOI 10.1002/(SICI)1097-0312(199911)52:11<1335::AID-CPA1>3.0.CO;2-1
- P. Deift, S. D. Miller, and T. Trogdon, Stopping time signatures for some algorithms in cryptography, arXiv:1905.08408, 2019.
- Percy Deift and Thomas Trogdon, Universality for eigenvalue algorithms on sample covariance matrices, SIAM J. Numer. Anal. 55 (2017), no. 6, 2835–2862. MR 3723332, DOI 10.1137/17M1110900
- Percy Deift and Thomas Trogdon, Universality for the Toda algorithm to compute the largest eigenvalue of a random matrix, Comm. Pure Appl. Math. 71 (2018), no. 3, 505–536. MR 3762276, DOI 10.1002/cpa.21715
- Percy Deift and Thomas Trogdon, The conjugate gradient algorithm on well-conditioned Wishart matrices is almost deterministic, Quart. Appl. Math. 79 (2021), no. 1, 125–161. MR 4188626, DOI 10.1090/qam/1574
- Percy A. Deift, Alexander R. Its, and Xin Zhou, A Riemann-Hilbert approach to asymptotic problems arising in the theory of random matrix models, and also in the theory of integrable statistical mechanics, Ann. of Math. (2) 146 (1997), no. 1, 149–235. MR 1469319, DOI 10.2307/2951834
- Percy A. Deift, Govind Menon, Sheehan Olver, and Thomas Trogdon, Universality in numerical computations with random data, Proc. Natl. Acad. Sci. USA 111 (2014), no. 42, 14973–14978. MR 3276499, DOI 10.1073/pnas.1413446111
- Xiucai Ding, Spiked sample covariance matrices with possibly multiple bulk components, Random Matrices Theory Appl. 10 (2021), no. 1, Paper No. 2150014, 30. MR 4193187, DOI 10.1142/S2010326321500143
- X. Ding and H. C. Ji, Local laws for multiplication of random matrices and spiked invariant model, arXiv:2010.16083, 2020.
- X. Ding and T. Trogdon, A Riemann-Hilbert approach to the perturbation theory of orthogonal polynomials: applications to random matrix theory, 2021.
- X. Ding and H.-T. Wu, Phase transition of graph Laplacian of high dimensional noisy random point cloud, arXiv:2011.10725, 2020.
- Xiucai Ding and Fan Yang, A necessary and sufficient condition for edge universality at the largest singular values of covariance matrices, Ann. Appl. Probab. 28 (2018), no. 3, 1679–1738. MR 3809475, DOI 10.1214/17-AAP1341
- Xiucai Ding and Fan Yang, Spiked separable covariance matrices and principal components, Ann. Statist. 49 (2021), no. 2, 1113–1138. MR 4255121, DOI 10.1214/20-aos1995
- Ioana Dumitriu and Alan Edelman, Matrix models for beta ensembles, J. Math. Phys. 43 (2002), no. 11, 5830–5847. MR 1936554, DOI 10.1063/1.1507823
- T. Dupic and I. Pérez Castillo, Spectral density of products of Wishart dilute random matrices. Part I: the dense case, arXiv:1401.7802, 2014.
- Alan Edelman, Eigenvalues and condition numbers of random matrices, SIAM J. Matrix Anal. Appl. 9 (1988), no. 4, 543–560. MR 964668, DOI 10.1137/0609045
- Noureddine El Karoui, Tracy-Widom limit for the largest eigenvalue of a large class of complex sample covariance matrices, Ann. Probab. 35 (2007), no. 2, 663–714. MR 2308592, DOI 10.1214/009117906000000917
- Noureddine El Karoui, The spectrum of kernel random matrices, Ann. Statist. 38 (2010), no. 1, 1–50. MR 2589315, DOI 10.1214/08-AOS648
- Miroslav Fiedler, Bounds for the determinant of the sum of hermitian matrices, Proc. Amer. Math. Soc. 30 (1971), 27–31. MR 286814, DOI 10.1090/S0002-9939-1971-0286814-1
- Jeffrey S. Geronimo, Scattering theory, orthogonal polynomials, and $q$-series, SIAM J. Math. Anal. 25 (1994), no. 2, 392–419. MR 1266566, DOI 10.1137/S0036141092238990
- Herman H. Goldstine and John von Neumann, Numerical inverting of matrices of high order. II, Proc. Amer. Math. Soc. 2 (1951), 188–202. MR 41539, DOI 10.1090/S0002-9939-1951-0041539-X
- Gene H. Golub and Charles F. Van Loan, Matrix computations, 4th ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 2013. MR 3024913
- A. Greenbaum, Behavior of slightly perturbed Lanczos and conjugate-gradient recurrences, Linear Algebra Appl. 113 (1989), 7–63. MR 978581, DOI 10.1016/0024-3795(89)90285-1
- Trevor Hastie, Robert Tibshirani, and Jerome Friedman, The elements of statistical learning, 2nd ed., Springer Series in Statistics, Springer, New York, 2009. Data mining, inference, and prediction. MR 2722294, DOI 10.1007/978-0-387-84858-7
- Magnus R. Hestenes and Eduard Stiefel, Methods of conjugate gradients for solving linear systems, J. Research Nat. Bur. Standards 49 (1952), 409–436 (1953). MR 0060307, DOI 10.6028/jres.049.044
- A. R. It⋅s, A. S. Fokas, and A. A. Kapaev, On the asymptotic analysis of the Painlevé equations via the isomonodromy method, Nonlinearity 7 (1994), no. 5, 1291–1325. MR 1294544, DOI 10.1088/0951-7715/7/5/002
- Iain M. Johnstone, On the distribution of the largest eigenvalue in principal components analysis, Ann. Statist. 29 (2001), no. 2, 295–327. MR 1863961, DOI 10.1214/aos/1009210544
- Z. T. Ke, Y. Ma, and X. Lin, Estimation of the number of spiked eigenvalues in a covariance matrix by bulk eigenvalue matching analysis, Journal of the American Statistical Association, 2021 (online), https://www.tandfonline.com/doi/full/10.1080/01621459.2021.1933497.
- Antti Knowles and Jun Yin, Anisotropic local laws for random matrices, Probab. Theory Related Fields 169 (2017), no. 1-2, 257–352. MR 3704770, DOI 10.1007/s00440-016-0730-4
- Arno B. J. Kuijlaars, Riemann-Hilbert analysis for orthogonal polynomials, Orthogonal polynomials and special functions (Leuven, 2002) Lecture Notes in Math., vol. 1817, Springer, Berlin, 2003, pp. 167–210. MR 2022855, DOI 10.1007/3-540-44945-0_{5}
- A. B. J. Kuijlaars, K. T.-R. McLaughlin, W. Van Assche, and M. Vanlessen, The Riemann-Hilbert approach to strong asymptotics for orthogonal polynomials on $[-1,1]$, Adv. Math. 188 (2004), no. 2, 337–398. MR 2087231, DOI 10.1016/j.aim.2003.08.015
- Jörg Liesen and Zdeněk Strakoš, Krylov subspace methods, Numerical Mathematics and Scientific Computation, Oxford University Press, Oxford, 2013. Principles and analysis. MR 3024841
- V. A. Marčenko and L. A. Pastur, Distribution of eigenvalues for some sets of random matrices, Mathematics of the USSR-Sbornik 1(1967), no. 4, 457–483.
- C. C. Paige, Error analysis of the Lanczos algorithm for tridiagonalizing a symmetric matrix, J. Inst. Math. Appl. 18 (1976), no. 3, 341–349. MR 501834, DOI 10.1093/imamat/18.3.341
- C. C. Paige and M. A. Saunders, Solutions of sparse indefinite systems of linear equations, SIAM J. Numer. Anal. 12 (1975), no. 4, 617–629. MR 383715, DOI 10.1137/0712047
- C. Paquette, B. van Merriënboer, and F. Pedregosa, Halting time is predictable for large models: A universality property and average-case analysis, 2020.
- E. Paquette and T. Trogdon, Universality for the conjugate gradient and MINRES algorithms on sample covariance matrices, arXiv:2007.00640, 2020.
- Debashis Paul, Asymptotics of sample eigenstructure for a large dimensional spiked covariance model, Statist. Sinica 17 (2007), no. 4, 1617–1642. MR 2399865
- Debashis Paul and Alexander Aue, Random matrix theory in statistics: a review, J. Statist. Plann. Inference 150 (2014), 1–29. MR 3206718, DOI 10.1016/j.jspi.2013.09.005
- F. Peherstorfer, Orthogonal polynomials on several intervals: accumulation points of recurrence coefficients and of zeros, J. Approx. Theory 163 (2011), no. 7, 814–837. MR 2832763, DOI 10.1016/j.jat.2011.03.002
- Christian W. Pfrang, Percy Deift, and Govind Menon, How long does it take to compute the eigenvalues of a random symmetric matrix?, Random matrix theory, interacting particle systems, and integrable systems, Math. Sci. Res. Inst. Publ., vol. 65, Cambridge Univ. Press, New York, 2014, pp. 411–442. MR 3380694
- Jack W. Silverstein and Sang-Il Choi, Analysis of the limiting spectral distribution of large-dimensional random matrices, J. Multivariate Anal. 54 (1995), no. 2, 295–309. MR 1345541, DOI 10.1006/jmva.1995.1058
- Jack W. Silverstein, The smallest eigenvalue of a large-dimensional Wishart matrix, Ann. Probab. 13 (1985), no. 4, 1364–1368. MR 806232
- Daniel A. Spielman and Shang-Hua Teng, Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time, J. ACM 51 (2004), no. 3, 385–463. MR 2145860, DOI 10.1145/990308.990310
- Gábor Szegő, Orthogonal polynomials, 4th ed., American Mathematical Society Colloquium Publications, Vol. XXIII, American Mathematical Society, Providence, R.I., 1975. MR 0372517
- Lloyd N. Trefethen and David Bau III, Numerical linear algebra, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. MR 1444820, DOI 10.1137/1.9780898719574
- Lloyd N. Trefethen and Robert S. Schreiber, Average-case stability of Gaussian elimination, SIAM J. Matrix Anal. Appl. 11 (1990), no. 3, 335–360. MR 1054179, DOI 10.1137/0611023
- Thomas Trogdon and Sheehan Olver, Riemann-Hilbert problems, their numerical solution, and the computation of nonlinear special functions, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2016. MR 3450072
- Hale F. Trotter, Eigenvalue distributions of large Hermitian matrices; Wigner’s semicircle law and a theorem of Kac, Murdock, and Szegő, Adv. in Math. 54 (1984), no. 1, 67–82. MR 761763, DOI 10.1016/0001-8708(84)90037-9
- Haokai Xi, Fan Yang, and Jun Yin, Convergence of eigenvector empirical spectral distribution of sample covariance matrices, Ann. Statist. 48 (2020), no. 2, 953–982. MR 4102683, DOI 10.1214/19-AOS1832
- Ningning Xia, Yingli Qin, and Zhidong Bai, Convergence rates of eigenvector empirical spectral distribution of large dimensional sample covariance matrix, Ann. Statist. 41 (2013), no. 5, 2572–2607. MR 3161438, DOI 10.1214/13-AOS1154
- F. Yang. Linear spectral statistics of eigenvectors of anisotropic sample covariance matrices, arXiv:2005.00999, 2020.
- Jianfeng Yao, Shurong Zheng, and Zhidong Bai, Large sample covariance matrices and high-dimensional data analysis, Cambridge Series in Statistical and Probabilistic Mathematics, vol. 39, Cambridge University Press, New York, 2015. MR 3468554, DOI 10.1017/CBO9781107588080
- Maxim L. Yattselev, Nuttall’s theorem with analytic weights on algebraic S-contours, J. Approx. Theory 190 (2015), 73–90. MR 3304590, DOI 10.1016/j.jat.2014.10.015
References
- Zhidong Bai and Jack W. Silverstein, Spectral analysis of large dimensional random matrices, 2nd ed., Springer Series in Statistics, Springer, New York, 2010. MR 2567175, DOI 10.1007/978-1-4419-0661-8
- Z. D. Bai, B. Q. Miao, and G. M. Pan, On asymptotics of eigenvectors of large sample covariance matrix, Ann. Probab. 35 (2007), no. 4, 1532–1572. MR 2330979, DOI 10.1214/009117906000001079
- Z. Bao, X. Ding, J. Wang, and K. Wang, Statistical inference for principal components of spiked covariance matrices, arXiv preprint arXiv:arXiv:2008.11903, 2020.
- Bernhard Beckermann and Arno B. J. Kuijlaars, Superlinear convergence of conjugate gradients, SIAM J. Numer. Anal. 39 (2001), no. 1, 300–329. MR 1860727, DOI 10.1137/S0036142999363188
- Serban T. Belinschi, Hari Bercovici, Mireille Capitaine, and Maxime Février, Outliers in the spectrum of large deformed unitarily invariant models, Ann. Probab. 45 (2017), no. 6A, 3571–3625. MR 3729610, DOI 10.1214/16-AOP1144
- Alex Bloemendal, Antti Knowles, Horng-Tzer Yau, and Jun Yin, On the principal components of sample covariance matrices, Probab. Theory Related Fields 164 (2016), no. 1-2, 459–552. MR 3449395, DOI 10.1007/s00440-015-0616-x
- Alex Bloemendal and Bálint Virág, Limits of spiked random matrices I, Probab. Theory Related Fields 156 (2013), no. 3-4, 795–825. MR 3078286, DOI 10.1007/s00440-012-0443-2
- P. A. Deift, Orthogonal polynomials and random matrices: a Riemann-Hilbert approach, Courant Lecture Notes in Mathematics, vol. 3, New York University, Courant Institute of Mathematical Sciences, New York; American Mathematical Society, Providence, RI, 1999. MR 1677884
- P. Deift, T. Kriecherbauer, K. T.-R. McLaughlin, S. Venakides, and X. Zhou, Uniform asymptotics for polynomials orthogonal with respect to varying exponential weights and applications to universality questions in random matrix theory, Comm. Pure Appl. Math. 52 (1999), no. 11, 1335–1425. MR 1702716, DOI 10.1002/(SICI)1097-0312(199911)52:11$\langle$1335::AID-CPA1$\rangle$3.0.CO;2-1
- P. Deift, S. D. Miller, and T. Trogdon, Stopping time signatures for some algorithms in cryptography, arXiv:1905.08408, 2019.
- Percy Deift and Thomas Trogdon, Universality for eigenvalue algorithms on sample covariance matrices, SIAM J. Numer. Anal. 55 (2017), no. 6, 2835–2862. MR 3723332, DOI 10.1137/17M1110900
- Percy Deift and Thomas Trogdon, Universality for the Toda algorithm to compute the largest eigenvalue of a random matrix, Comm. Pure Appl. Math. 71 (2018), no. 3, 505–536. MR 3762276, DOI 10.1002/cpa.21715
- Percy Deift and Thomas Trogdon, The conjugate gradient algorithm on well-conditioned Wishart matrices is almost deterministic, Quart. Appl. Math. 79 (2021), no. 1, 125–161. MR 4188626, DOI 10.1090/qam/1574
- Percy A. Deift, Alexander R. Its, and Xin Zhou, A Riemann-Hilbert approach to asymptotic problems arising in the theory of random matrix models, and also in the theory of integrable statistical mechanics, Ann. of Math. (2) 146 (1997), no. 1, 149–235. MR 1469319, DOI 10.2307/2951834
- Percy A. Deift, Govind Menon, Sheehan Olver, and Thomas Trogdon, Universality in numerical computations with random data, Proc. Natl. Acad. Sci. USA 111 (2014), no. 42, 14973–14978. MR 3276499, DOI 10.1073/pnas.1413446111
- Xiucai Ding, Spiked sample covariance matrices with possibly multiple bulk components, Random Matrices Theory Appl. 10 (2021), no. 1, Paper No. 2150014, 30. MR 4193187, DOI 10.1142/S2010326321500143
- X. Ding and H. C. Ji, Local laws for multiplication of random matrices and spiked invariant model, arXiv:2010.16083, 2020.
- X. Ding and T. Trogdon, A Riemann-Hilbert approach to the perturbation theory of orthogonal polynomials: applications to random matrix theory, 2021.
- X. Ding and H.-T. Wu, Phase transition of graph Laplacian of high dimensional noisy random point cloud, arXiv:2011.10725, 2020.
- Xiucai Ding and Fan Yang, A necessary and sufficient condition for edge universality at the largest singular values of covariance matrices, Ann. Appl. Probab. 28 (2018), no. 3, 1679–1738. MR 3809475, DOI 10.1214/17-AAP1341
- Xiucai Ding and Fan Yang, Spiked separable covariance matrices and principal components, Ann. Statist. 49 (2021), no. 2, 1113–1138. MR 4255121, DOI 10.1214/20-aos1995
- Ioana Dumitriu and Alan Edelman, Matrix models for beta ensembles, J. Math. Phys. 43 (2002), no. 11, 5830–5847. MR 1936554, DOI 10.1063/1.1507823
- T. Dupic and I. Pérez Castillo, Spectral density of products of Wishart dilute random matrices. Part I: the dense case, arXiv:1401.7802, 2014.
- Alan Edelman, Eigenvalues and condition numbers of random matrices, SIAM J. Matrix Anal. Appl. 9 (1988), no. 4, 543–560. MR 964668, DOI 10.1137/0609045
- Noureddine El Karoui, Tracy-Widom limit for the largest eigenvalue of a large class of complex sample covariance matrices, Ann. Probab. 35 (2007), no. 2, 663–714. MR 2308592, DOI 10.1214/009117906000000917
- Noureddine El Karoui, The spectrum of kernel random matrices, Ann. Statist. 38 (2010), no. 1, 1–50. MR 2589315, DOI 10.1214/08-AOS648
- Miroslav Fiedler, Bounds for the determinant of the sum of hermitian matrices, Proc. Amer. Math. Soc. 30 (1971), 27–31. MR 286814, DOI 10.2307/2038212
- Jeffrey S. Geronimo, Scattering theory, orthogonal polynomials, and $q$-series, SIAM J. Math. Anal. 25 (1994), no. 2, 392–419. MR 1266566, DOI 10.1137/S0036141092238990
- Herman H. Goldstine and John von Neumann, Numerical inverting of matrices of high order. II, Proc. Amer. Math. Soc. 2 (1951), 188–202. MR 41539, DOI 10.2307/2032484
- Gene H. Golub and Charles F. Van Loan, Matrix computations, 4th ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 2013. MR 3024913
- A. Greenbaum, Behavior of slightly perturbed Lanczos and conjugate-gradient recurrences, Linear Algebra Appl. 113 (1989), 7–63. MR 978581, DOI 10.1016/0024-3795(89)90285-1
- Trevor Hastie, Robert Tibshirani, and Jerome Friedman, The elements of statistical learning, 2nd ed., Springer Series in Statistics, Springer, New York, 2009. Data mining, inference, and prediction. MR 2722294, DOI 10.1007/978-0-387-84858-7
- Magnus R. Hestenes and Eduard Stiefel, Methods of conjugate gradients for solving linear systems, J. Research Nat. Bur. Standards 49 (1952), 409–436 (1953). MR 0060307
- A. R. Its, A. S. Fokas, and A. A. Kapaev, On the asymptotic analysis of the Painlevé equations via the isomonodromy method, Nonlinearity 7 (1994), no. 5, 1291–1325. MR 1294544
- Iain M. Johnstone, On the distribution of the largest eigenvalue in principal components analysis, Ann. Statist. 29 (2001), no. 2, 295–327. MR 1863961, DOI 10.1214/aos/1009210544
- Z. T. Ke, Y. Ma, and X. Lin, Estimation of the number of spiked eigenvalues in a covariance matrix by bulk eigenvalue matching analysis, Journal of the American Statistical Association, 2021 (online), https://www.tandfonline.com/doi/full/10.1080/01621459.2021.1933497.
- Antti Knowles and Jun Yin, Anisotropic local laws for random matrices, Probab. Theory Related Fields 169 (2017), no. 1-2, 257–352. MR 3704770, DOI 10.1007/s00440-016-0730-4
- Arno B. J. Kuijlaars, Riemann-Hilbert analysis for orthogonal polynomials, Orthogonal polynomials and special functions (Leuven, 2002) Lecture Notes in Math., vol. 1817, Springer, Berlin, 2003, pp. 167–210. MR 2022855, DOI 10.1007/3-540-44945-0_5
- A. B. J. Kuijlaars, K. T.-R. McLaughlin, W. Van Assche, and M. Vanlessen, The Riemann-Hilbert approach to strong asymptotics for orthogonal polynomials on $[-1,1]$, Adv. Math. 188 (2004), no. 2, 337–398. MR 2087231, DOI 10.1016/j.aim.2003.08.015
- Jörg Liesen and Zdeněk Strakoš, Krylov subspace methods, Numerical Mathematics and Scientific Computation, Oxford University Press, Oxford, 2013. Principles and analysis. MR 3024841
- V. A. Marčenko and L. A. Pastur, Distribution of eigenvalues for some sets of random matrices, Mathematics of the USSR-Sbornik 1(1967), no. 4, 457–483.
- C. C. Paige, Error analysis of the Lanczos algorithm for tridiagonalizing a symmetric matrix, J. Inst. Math. Appl. 18 (1976), no. 3, 341–349. MR 501834
- C. C. Paige and M. A. Saunders, Solutions of sparse indefinite systems of linear equations, SIAM J. Numer. Anal. 12 (1975), no. 4, 617–629. MR 383715, DOI 10.1137/0712047
- C. Paquette, B. van Merriënboer, and F. Pedregosa, Halting time is predictable for large models: A universality property and average-case analysis, 2020.
- E. Paquette and T. Trogdon, Universality for the conjugate gradient and MINRES algorithms on sample covariance matrices, arXiv:2007.00640, 2020.
- Debashis Paul, Asymptotics of sample eigenstructure for a large dimensional spiked covariance model, Statist. Sinica 17 (2007), no. 4, 1617–1642. MR 2399865
- Debashis Paul and Alexander Aue, Random matrix theory in statistics: a review, J. Statist. Plann. Inference 150 (2014), 1–29. MR 3206718, DOI 10.1016/j.jspi.2013.09.005
- F. Peherstorfer, Orthogonal polynomials on several intervals: accumulation points of recurrence coefficients and of zeros, J. Approx. Theory 163 (2011), no. 7, 814–837. MR 2832763, DOI 10.1016/j.jat.2011.03.002
- Christian W. Pfrang, Percy Deift, and Govind Menon, How long does it take to compute the eigenvalues of a random symmetric matrix?, Random matrix theory, interacting particle systems, and integrable systems, Math. Sci. Res. Inst. Publ., vol. 65, Cambridge Univ. Press, New York, 2014, pp. 411–442. MR 3380694
- Jack W. Silverstein and Sang-Il Choi, Analysis of the limiting spectral distribution of large-dimensional random matrices, J. Multivariate Anal. 54 (1995), no. 2, 295–309. MR 1345541, DOI 10.1006/jmva.1995.1058
- Jack W. Silverstein, The smallest eigenvalue of a large-dimensional Wishart matrix, Ann. Probab. 13 (1985), no. 4, 1364–1368. MR 806232
- Daniel A. Spielman and Shang-Hua Teng, Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time, J. ACM 51 (2004), no. 3, 385–463. MR 2145860, DOI 10.1145/990308.990310
- Gábor Szegő, Orthogonal polynomials, 4th ed., American Mathematical Society Colloquium Publications, Vol. XXIII, American Mathematical Society, Providence, R.I., 1975. MR 0372517
- Lloyd N. Trefethen and David Bau III, Numerical linear algebra, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. MR 1444820, DOI 10.1137/1.9780898719574
- Lloyd N. Trefethen and Robert S. Schreiber, Average-case stability of Gaussian elimination, SIAM J. Matrix Anal. Appl. 11 (1990), no. 3, 335–360. MR 1054179, DOI 10.1137/0611023
- Thomas Trogdon and Sheehan Olver, Riemann-Hilbert problems, their numerical solution, and the computation of nonlinear special functions, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2016. MR 3450072
- Hale F. Trotter, Eigenvalue distributions of large Hermitian matrices; Wigner’s semicircle law and a theorem of Kac, Murdock, and Szegő, Adv. in Math. 54 (1984), no. 1, 67–82. MR 761763, DOI 10.1016/0001-8708(84)90037-9
- Haokai Xi, Fan Yang, and Jun Yin, Convergence of eigenvector empirical spectral distribution of sample covariance matrices, Ann. Statist. 48 (2020), no. 2, 953–982. MR 4102683, DOI 10.1214/19-AOS1832
- Ningning Xia, Yingli Qin, and Zhidong Bai, Convergence rates of eigenvector empirical spectral distribution of large dimensional sample covariance matrix, Ann. Statist. 41 (2013), no. 5, 2572–2607. MR 3161438, DOI 10.1214/13-AOS1154
- F. Yang. Linear spectral statistics of eigenvectors of anisotropic sample covariance matrices, arXiv:2005.00999, 2020.
- Jianfeng Yao, Shurong Zheng, and Zhidong Bai, Large sample covariance matrices and high-dimensional data analysis, Cambridge Series in Statistical and Probabilistic Mathematics, vol. 39, Cambridge University Press, New York, 2015. MR 3468554, DOI 10.1017/CBO9781107588080
- Maxim L. Yattselev, Nuttall’s theorem with analytic weights on algebraic S-contours, J. Approx. Theory 190 (2015), 73–90. MR 3304590, DOI 10.1016/j.jat.2014.10.015
Similar Articles
Retrieve articles in Quarterly of Applied Mathematics
with MSC (2020):
65F10,
60B20
Retrieve articles in all journals
with MSC (2020):
65F10,
60B20
Additional Information
Xiucai Ding
Affiliation:
Department of Statistics, University of California Davis, Davis, CA 95616
MR Author ID:
1273109
Email:
xcading@ucdavis.edu
Thomas Trogdon
Affiliation:
Department of Applied Mathematics, University of Washington, Seattle, WA 98195-3925
MR Author ID:
965414
ORCID:
0000-0002-6955-4154
Email:
trogdon@uw.edu
Keywords:
Sample covariance matrices,
conjugate gradient
Received by editor(s):
October 13, 2021
Published electronically:
November 19, 2021
Additional Notes:
The authors gratefully acknowledge support from the US National Science Foundation under grant NSF-DMS-1945652 (TT). Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the funding sources.
Article copyright:
© Copyright 2021
Brown University
