American Institute of Mathematical Sciences

Advanced
August  2016, 36(8): 4287-4347. doi: 10.3934/dcds.2016.36.4287

On the condition number of the critically-scaled Laguerre Unitary Ensemble

Percy A. Deift 1, , Thomas Trogdon 1, and  Govind Menon 2,

1. 

Courant Institute of Mathematical Sciences, New York University, 251 Mercer St, New York, NY 10012, United States, United States
2. 

Division of Applied Mathematics, Brown University, 182 George St, Providence, RI 02912, United States

Received  July 2015 Revised  November 2015 Published  March 2016

We consider the Laguerre Unitary Ensemble (aka, Wishart Ensemble) of sample covariance matrices $A = XX^*$, where $X$ is an $N \times n$ matrix with iid standard complex normal entries. Under the scaling $n = N + \lfloor \sqrt{ 4 c N} \rfloor$, $c > 0$ and $N \rightarrow \infty$, we show that the rescaled fluctuations of the smallest eigenvalue, largest eigenvalue and condition number of the matrices $A$ are all given by the Tracy--Widom distribution ($\beta = 2$). This scaling is motivated by the study of the solution of the equation $Ax=b$ using the conjugate gradient algorithm, in the case that $A$ and $b$ are random: For such a scaling the fluctuations of the halting time for the algorithm are empirically seen to be universal.
Keywords: Laguerre polynomials, Wishart ensemble, conjugate gradient algorithm., Laguerre Unitary Ensemble, Riemann--Hilbert problems.
Mathematics Subject Classification: Primary: 60B20, 65C50; Secondary: 35Q1.
Citation: Percy A. Deift, Thomas Trogdon, Govind Menon. On the condition number of the critically-scaled Laguerre Unitary Ensemble. Discrete & Continuous Dynamical Systems, 2016, 36 (8) : 4287-4347. doi: 10.3934/dcds.2016.36.4287
References:
[1]

T. H. Baker, P. J. Forrester and P. A. Pearce, Random matrix ensembles with an effective extensive external charge, J. Phys. A. Math. Gen., 31 (1998), 6087-6101. doi: 10.1088/0305-4470/31/29/002.  Google Scholar

[2]

E. Basor, Y. Chen and L. Zhang, PDEs satisfied by extreme eigenvalues distributions of GUE and LUE, Random Matrices Theory Appl., 1 (2012), 1150003, 21pp. doi: 10.1142/S2010326311500031.  Google Scholar

[3]

P. Deift, Orthogonal Polynomials and Random Matrices: A Riemann-Hilbert Approach, Amer. Math. Soc., Providence, RI, 1999.  Google Scholar

[4]

P. Deift, T. Kriecherbauer, K. T.-R. McLaughlin, S. Venakides and X. Zhou, Asymptotics for polynomials orthogonal with respect to varying exponential weights, Internat. Math. Res. Not., 16 (1997), 759-782. doi: 10.1155/S1073792897000500.  Google Scholar

[5]

P. Deift, T. Kriecherbauer, K. T.-R. McLaughlin, S. Venakides and X. Zhou, Strong asymptotics of orthogonal polynomials with respect to exponential weights, Comm. Pure Appl. Math., 52 (1999), 1491-1552.  Google Scholar

[6]

P. A. Deift, G. Menon, S. Olver and T. Trogdon, Universality in numerical computations with random data, Proc. Natl. Acad. Sci. U. S. A., 111 (2014), 14973-14978. doi: 10.1073/pnas.1413446111.  Google Scholar

[7]

A. Edelman, Eigenvalues and condition numbers of random matrices, SIAM J. Matrix Anal. Appl., 9 (1988), 543-560. doi: 10.1137/0609045.  Google Scholar

[8]

A. S. Fokas, A. R. Its and A. V. Kitaev, The isomonodromy approach to matrix models in 2D quantum gravity, Comm. Math. Phys., 147 (1992), 395-430. doi: 10.1007/BF02096594.  Google Scholar

[9]

P. J. Forrester, The spectrum edge of random matrix ensembles, Nucl. Phys. B, 402 (1993), 709-728. doi: 10.1016/0550-3213(93)90126-A.  Google Scholar

[10]

H. H. Goldstine and J. von Neumann, Numerical inverting of matrices of high order. II, Proc. AMS, 2 (1951), 188-202. doi: 10.1090/S0002-9939-1951-0041539-X.  Google Scholar

[11]

A. Greenbaum, Behavior of slightly perturbed Lanczos and conjugate-gradient recurrences, Linear Algebra Appl., 113 (1989), 7-63. doi: 10.1016/0024-3795(89)90285-1.  Google Scholar

[12]

M. Hestenes and E. Steifel, Method of conjugate gradients for solving linear systems, J. Res., 20 (1952), 409-436. Google Scholar

[13]

T. Jiang and D. Li, Approximation of rectangular beta-laguerre ensembles and large deviations, J. Theor. Probab., 28 (2015), 804-847. doi: 10.1007/s10959-013-0519-7.  Google Scholar

[14]

K. Johansson, Shape fluctuations and random matrices, Commun. Math. Phys., 209 (2000), 437-476. doi: 10.1007/s002200050027.  Google Scholar

[15]

I. M. Johnstone, On the distribution of the largest eigenvalue in principal components analysis, Ann. Stat., 29 (2001), 295-327. doi: 10.1214/aos/1009210543.  Google Scholar

[16]

S. Kaniel, Estimates for some computational techniques in linear algebra, Math. Comput., 20 (1966), 369-378. doi: 10.1090/S0025-5718-1966-0234618-4.  Google Scholar

[17]

P. R. Krishnaiah and T. C. Chang, On the exact distribution of the smallest root of the wishart matrix using zonal polynomials, Ann. Inst. Stat. Math., 23 (1971), 293-295. doi: 10.1007/BF02479230.  Google Scholar

[18]

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. (N. Y)., 188 (2004), 337-398. doi: 10.1016/j.aim.2003.08.015.  Google Scholar

[19]

V. A. Marčenko and L. A. Pastur, Distribution of eigenvalues for some sets of random matrices, Math. USSR-Sbornik, 1 (1967), 457-483. Google Scholar

[20]

F. W. J. Olver, D. W. Lozier, R. F. Boisvert and C. W. Clark, NIST Handbook of Mathematical Functions, Cambridge University Press, 2010.  Google Scholar

[21]

W.-Y. Qiu and R. Wong, Global asymptotic expansions of the Laguerre polynomials Riemann-Hilbert approach, Numer. Algorithms, 49 (2008), 331-372. doi: 10.1007/s11075-008-9159-x.  Google Scholar

[22]

B Simon, Trace Ideals and Their Applications, volume 120 of Mathematical Surveys and Monographs, American Mathematical Society, Providence, Rhode Island, mar 2010.  Google Scholar

[23]

T. Sugiyama, On the distribution of the largest latent root and the corresponding latent vector for principal component analysis, Ann. Math. Stat., 37 (1966), 995-1001. doi: 10.1214/aoms/1177699378.  Google Scholar

[24]

G. Szegö, Orthogonal Polynomials, Amer. Math. Soc., Providence, RI, 1959. Google Scholar

[25]

C. A. Tracy and H. Widom, Level-spacing distributions and the Airy kernel, Comm. Math. Phys., 159 (1994), 151-174. doi: 10.1007/BF02100489.  Google Scholar

[26]

T. Trogdon, Riemann-Hilbert Problems, Their Numerical Solution and the Computation of Nonlinear Special Functions, PhD thesis, University of Washington, nov 2013.  Google Scholar

[27]

M. Vanlessen, Strong asymptotics of laguerre-type orthogonal polynomials and applications in random matrix theory, Constr. Approx., 25 (2007), 125-175. doi: 10.1007/s00365-005-0611-z.  Google Scholar

[28]

S.-X. Xu, D. Dai and Y.-Q. Zhao, Critical edge behavior and the bessel to airy transition in the singularly perturbed laguerre unitary ensemble, Commun. Math. Phys., 332 (2014), 1257-1296. doi: 10.1007/s00220-014-2131-9.  Google Scholar

show all references

References:
[1]

T. H. Baker, P. J. Forrester and P. A. Pearce, Random matrix ensembles with an effective extensive external charge, J. Phys. A. Math. Gen., 31 (1998), 6087-6101. doi: 10.1088/0305-4470/31/29/002.  Google Scholar

[2]

E. Basor, Y. Chen and L. Zhang, PDEs satisfied by extreme eigenvalues distributions of GUE and LUE, Random Matrices Theory Appl., 1 (2012), 1150003, 21pp. doi: 10.1142/S2010326311500031.  Google Scholar

[3]

P. Deift, Orthogonal Polynomials and Random Matrices: A Riemann-Hilbert Approach, Amer. Math. Soc., Providence, RI, 1999.  Google Scholar

[4]

P. Deift, T. Kriecherbauer, K. T.-R. McLaughlin, S. Venakides and X. Zhou, Asymptotics for polynomials orthogonal with respect to varying exponential weights, Internat. Math. Res. Not., 16 (1997), 759-782. doi: 10.1155/S1073792897000500.  Google Scholar

[5]

P. Deift, T. Kriecherbauer, K. T.-R. McLaughlin, S. Venakides and X. Zhou, Strong asymptotics of orthogonal polynomials with respect to exponential weights, Comm. Pure Appl. Math., 52 (1999), 1491-1552.  Google Scholar

[6]

P. A. Deift, G. Menon, S. Olver and T. Trogdon, Universality in numerical computations with random data, Proc. Natl. Acad. Sci. U. S. A., 111 (2014), 14973-14978. doi: 10.1073/pnas.1413446111.  Google Scholar

[7]

A. Edelman, Eigenvalues and condition numbers of random matrices, SIAM J. Matrix Anal. Appl., 9 (1988), 543-560. doi: 10.1137/0609045.  Google Scholar

[8]

A. S. Fokas, A. R. Its and A. V. Kitaev, The isomonodromy approach to matrix models in 2D quantum gravity, Comm. Math. Phys., 147 (1992), 395-430. doi: 10.1007/BF02096594.  Google Scholar

[9]

P. J. Forrester, The spectrum edge of random matrix ensembles, Nucl. Phys. B, 402 (1993), 709-728. doi: 10.1016/0550-3213(93)90126-A.  Google Scholar

[10]

H. H. Goldstine and J. von Neumann, Numerical inverting of matrices of high order. II, Proc. AMS, 2 (1951), 188-202. doi: 10.1090/S0002-9939-1951-0041539-X.  Google Scholar

[11]

A. Greenbaum, Behavior of slightly perturbed Lanczos and conjugate-gradient recurrences, Linear Algebra Appl., 113 (1989), 7-63. doi: 10.1016/0024-3795(89)90285-1.  Google Scholar

[12]

M. Hestenes and E. Steifel, Method of conjugate gradients for solving linear systems, J. Res., 20 (1952), 409-436. Google Scholar

[13]

T. Jiang and D. Li, Approximation of rectangular beta-laguerre ensembles and large deviations, J. Theor. Probab., 28 (2015), 804-847. doi: 10.1007/s10959-013-0519-7.  Google Scholar

[14]

K. Johansson, Shape fluctuations and random matrices, Commun. Math. Phys., 209 (2000), 437-476. doi: 10.1007/s002200050027.  Google Scholar

[15]

I. M. Johnstone, On the distribution of the largest eigenvalue in principal components analysis, Ann. Stat., 29 (2001), 295-327. doi: 10.1214/aos/1009210543.  Google Scholar

[16]

S. Kaniel, Estimates for some computational techniques in linear algebra, Math. Comput., 20 (1966), 369-378. doi: 10.1090/S0025-5718-1966-0234618-4.  Google Scholar

[17]

P. R. Krishnaiah and T. C. Chang, On the exact distribution of the smallest root of the wishart matrix using zonal polynomials, Ann. Inst. Stat. Math., 23 (1971), 293-295. doi: 10.1007/BF02479230.  Google Scholar

[18]

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. (N. Y)., 188 (2004), 337-398. doi: 10.1016/j.aim.2003.08.015.  Google Scholar

[19]

V. A. Marčenko and L. A. Pastur, Distribution of eigenvalues for some sets of random matrices, Math. USSR-Sbornik, 1 (1967), 457-483. Google Scholar

[20]

F. W. J. Olver, D. W. Lozier, R. F. Boisvert and C. W. Clark, NIST Handbook of Mathematical Functions, Cambridge University Press, 2010.  Google Scholar

[21]

W.-Y. Qiu and R. Wong, Global asymptotic expansions of the Laguerre polynomials Riemann-Hilbert approach, Numer. Algorithms, 49 (2008), 331-372. doi: 10.1007/s11075-008-9159-x.  Google Scholar

[22]

B Simon, Trace Ideals and Their Applications, volume 120 of Mathematical Surveys and Monographs, American Mathematical Society, Providence, Rhode Island, mar 2010.  Google Scholar

[23]

T. Sugiyama, On the distribution of the largest latent root and the corresponding latent vector for principal component analysis, Ann. Math. Stat., 37 (1966), 995-1001. doi: 10.1214/aoms/1177699378.  Google Scholar

[24]

G. Szegö, Orthogonal Polynomials, Amer. Math. Soc., Providence, RI, 1959. Google Scholar

[25]

C. A. Tracy and H. Widom, Level-spacing distributions and the Airy kernel, Comm. Math. Phys., 159 (1994), 151-174. doi: 10.1007/BF02100489.  Google Scholar

[26]

T. Trogdon, Riemann-Hilbert Problems, Their Numerical Solution and the Computation of Nonlinear Special Functions, PhD thesis, University of Washington, nov 2013.  Google Scholar

[27]

M. Vanlessen, Strong asymptotics of laguerre-type orthogonal polynomials and applications in random matrix theory, Constr. Approx., 25 (2007), 125-175. doi: 10.1007/s00365-005-0611-z.  Google Scholar

[28]

S.-X. Xu, D. Dai and Y.-Q. Zhao, Critical edge behavior and the bessel to airy transition in the singularly perturbed laguerre unitary ensemble, Commun. Math. Phys., 332 (2014), 1257-1296. doi: 10.1007/s00220-014-2131-9.  Google Scholar

[1]

Zhong-Qing Wang, Ben-Yu Guo, Yan-Na Wu. Pseudospectral method using generalized Laguerre functions for singular problems on unbounded domains. Discrete & Continuous Dynamical Systems - B, 2009, 11 (4) : 1019-1038. doi: 10.3934/dcdsb.2009.11.1019
[2]

R. Wong, L. Zhang. Global asymptotics of Hermite polynomials via Riemann-Hilbert approach. Discrete & Continuous Dynamical Systems - B, 2007, 7 (3) : 661-682. doi: 10.3934/dcdsb.2007.7.661
[3]

Jie Shen, Li-Lian Wang. Laguerre and composite Legendre-Laguerre Dual-Petrov-Galerkin methods for third-order equations. Discrete & Continuous Dynamical Systems - B, 2006, 6 (6) : 1381-1402. doi: 10.3934/dcdsb.2006.6.1381
[4]

Lili Ju, Wei Leng, Zhu Wang, Shuai Yuan. Numerical investigation of ensemble methods with block iterative solvers for evolution problems. Discrete & Continuous Dynamical Systems - B, 2020, 25 (12) : 4905-4923. doi: 10.3934/dcdsb.2020132
[5]

Zhiyan Ding, Qin Li, Jianfeng Lu. Ensemble Kalman Inversion for nonlinear problems: Weights, consistency, and variance bounds. Foundations of Data Science, 2021, 3 (3) : 371-411. doi: 10.3934/fods.2020018
[6]

Huiying Fan, Tao Ma. Parabolic equations involving Laguerre operators and weighted mixed-norm estimates. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5487-5508. doi: 10.3934/cpaa.2020249
[7]

Guanghui Zhou, Qin Ni, Meilan Zeng. A scaled conjugate gradient method with moving asymptotes for unconstrained optimization problems. Journal of Industrial & Management Optimization, 2017, 13 (2) : 595-608. doi: 10.3934/jimo.2016034
[8]

El-Sayed M.E. Mostafa. A nonlinear conjugate gradient method for a special class of matrix optimization problems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 883-903. doi: 10.3934/jimo.2014.10.883
[9]

ShiChun Lv, Shou-Qiang Du. A new smoothing spectral conjugate gradient method for solving tensor complementarity problems. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021150
[10]

Sebastian Reich, Seoleun Shin. On the consistency of ensemble transform filter formulations. Journal of Computational Dynamics, 2014, 1 (1) : 177-189. doi: 10.3934/jcd.2014.1.177
[11]

Ronan Costaouec, Haoyun Feng, Jesús Izaguirre, Eric Darve. Analysis of the accelerated weighted ensemble methodology. Conference Publications, 2013, 2013 (special) : 171-181. doi: 10.3934/proc.2013.2013.171
[12]

Yigui Ou, Xin Zhou. A modified scaled memoryless BFGS preconditioned conjugate gradient algorithm for nonsmooth convex optimization. Journal of Industrial & Management Optimization, 2018, 14 (2) : 785-801. doi: 10.3934/jimo.2017075
[13]

Ben-Yu Guo, Yu-Jian Jiao. Mixed generalized Laguerre-Fourier spectral method for exterior problem of Navier-Stokes equations. Discrete & Continuous Dynamical Systems - B, 2009, 11 (2) : 315-345. doi: 10.3934/dcdsb.2009.11.315
[14]

Young-Pil Choi, Seung-Yeal Ha, Javier Morales. Emergent dynamics of the Kuramoto ensemble under the effect of inertia. Discrete & Continuous Dynamical Systems, 2018, 38 (10) : 4875-4913. doi: 10.3934/dcds.2018213
[15]

Neil K. Chada, Claudia Schillings, Simon Weissmann. On the incorporation of box-constraints for ensemble Kalman inversion. Foundations of Data Science, 2019, 1 (4) : 433-456. doi: 10.3934/fods.2019018
[16]

Seung-Yeal Ha, Jaeseung Lee, Zhuchun Li. Emergence of local synchronization in an ensemble of heterogeneous Kuramoto oscillators. Networks & Heterogeneous Media, 2017, 12 (1) : 1-24. doi: 10.3934/nhm.2017001
[17]

Seung-Yeal Ha, Myeongju Kang, Bora Moon. Collective behaviors of a Winfree ensemble on an infinite cylinder. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2749-2779. doi: 10.3934/dcdsb.2020204
[18]

Andreas Bock, Colin J. Cotter. Learning landmark geodesics using the ensemble Kalman filter. Foundations of Data Science, 2021  doi: 10.3934/fods.2021020
[19]

Alexey Penenko. Convergence analysis of the adjoint ensemble method in inverse source problems for advection-diffusion-reaction models with image-type measurements. Inverse Problems & Imaging, 2020, 14 (5) : 757-782. doi: 10.3934/ipi.2020035
[20]

Ya Li, ShouQiang Du, YuanYuan Chen. Modified spectral PRP conjugate gradient method for solving tensor eigenvalue complementarity problems. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020147

2020 Impact Factor: 1.392

Tools

Metrics

  • PDF downloads (128)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences