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 - A, 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.  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).  doi: 10.1142/S2010326311500031.  Google Scholar

[3]

P. Deift, Orthogonal Polynomials and Random Matrices: A Riemann-Hilbert Approach,, Amer. Math. Soc., (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.  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.   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.  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.  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.  doi: 10.1007/BF02096594.  Google Scholar

[9]

P. J. Forrester, The spectrum edge of random matrix ensembles,, Nucl. Phys. B, 402 (1993), 709.  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.  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.  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.   Google Scholar

[13]

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

[14]

K. Johansson, Shape fluctuations and random matrices,, Commun. Math. Phys., 209 (2000), 437.  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.  doi: 10.1214/aos/1009210543.  Google Scholar

[16]

S. Kaniel, Estimates for some computational techniques in linear algebra,, Math. Comput., 20 (1966), 369.  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.  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.  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.   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.  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, (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.  doi: 10.1214/aoms/1177699378.  Google Scholar

[24]

G. Szegö, Orthogonal Polynomials,, Amer. Math. Soc., (1959).   Google Scholar

[25]

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

[26]

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

[27]

M. Vanlessen, Strong asymptotics of laguerre-type orthogonal polynomials and applications in random matrix theory,, Constr. Approx., 25 (2007), 125.  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.  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.  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).  doi: 10.1142/S2010326311500031.  Google Scholar

[3]

P. Deift, Orthogonal Polynomials and Random Matrices: A Riemann-Hilbert Approach,, Amer. Math. Soc., (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.  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.   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.  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.  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.  doi: 10.1007/BF02096594.  Google Scholar

[9]

P. J. Forrester, The spectrum edge of random matrix ensembles,, Nucl. Phys. B, 402 (1993), 709.  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.  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.  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.   Google Scholar

[13]

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

[14]

K. Johansson, Shape fluctuations and random matrices,, Commun. Math. Phys., 209 (2000), 437.  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.  doi: 10.1214/aos/1009210543.  Google Scholar

[16]

S. Kaniel, Estimates for some computational techniques in linear algebra,, Math. Comput., 20 (1966), 369.  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.  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.  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.   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.  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, (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.  doi: 10.1214/aoms/1177699378.  Google Scholar

[24]

G. Szegö, Orthogonal Polynomials,, Amer. Math. Soc., (1959).   Google Scholar

[25]

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

[26]

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

[27]

M. Vanlessen, Strong asymptotics of laguerre-type orthogonal polynomials and applications in random matrix theory,, Constr. Approx., 25 (2007), 125.  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.  doi: 10.1007/s00220-014-2131-9.  Google Scholar

[1]

Zhiyan Ding, Qin Li, Jianfeng Lu. Ensemble Kalman Inversion for nonlinear problems: Weights, consistency, and variance bounds. Foundations of Data Science, 2020  doi: 10.3934/fods.2020018
[2]

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
[3]

Håkon Hoel, Gaukhar Shaimerdenova, Raúl Tempone. Multilevel Ensemble Kalman Filtering based on a sample average of independent EnKF estimators. Foundations of Data Science, 2020, 2 (4) : 351-390. doi: 10.3934/fods.2020017
[4]

Geir Evensen, Javier Amezcua, Marc Bocquet, Alberto Carrassi, Alban Farchi, Alison Fowler, Pieter L. Houtekamer, Christopher K. Jones, Rafael J. de Moraes, Manuel Pulido, Christian Sampson, Femke C. Vossepoel. An international initiative of predicting the SARS-CoV-2 pandemic using ensemble data assimilation. Foundations of Data Science, 2020  doi: 10.3934/fods.2021001
[5]

Manxue You, Shengjie Li. Perturbation of Image and conjugate duality for vector optimization. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020176
[6]

Alessandro Carbotti, Giovanni E. Comi. A note on Riemann-Liouville fractional Sobolev spaces. Communications on Pure & Applied Analysis, 2021, 20 (1) : 17-54. doi: 10.3934/cpaa.2020255
[7]

Constantine M. Dafermos. A variational approach to the Riemann problem for hyperbolic conservation laws. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 185-195. doi: 10.3934/dcds.2009.23.185
[8]

Mostafa Mbekhta. Representation and approximation of the polar factor of an operator on a Hilbert space. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020463
[9]

Peter H. van der Kamp, D. I. McLaren, G. R. W. Quispel. Homogeneous darboux polynomials and generalising integrable ODE systems. Journal of Computational Dynamics, 2021, 8 (1) : 1-8. doi: 10.3934/jcd.2021001
[10]

Petr Čoupek, María J. Garrido-Atienza. Bilinear equations in Hilbert space driven by paths of low regularity. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 121-154. doi: 10.3934/dcdsb.2020230
[11]

Liam Burrows, Weihong Guo, Ke Chen, Francesco Torella. Reproducible kernel Hilbert space based global and local image segmentation. Inverse Problems & Imaging, 2021, 15 (1) : 1-25. doi: 10.3934/ipi.2020048
[12]

Predrag S. Stanimirović, Branislav Ivanov, Haifeng Ma, Dijana Mosić. A survey of gradient methods for solving nonlinear optimization. Electronic Research Archive, 2020, 28 (4) : 1573-1624. doi: 10.3934/era.2020115
[13]

Wolfgang Riedl, Robert Baier, Matthias Gerdts. Optimization-based subdivision algorithm for reachable sets. Journal of Computational Dynamics, 2021, 8 (1) : 99-130. doi: 10.3934/jcd.2021005
[14]

Djamel Aaid, Amel Noui, Özen Özer. Piecewise quadratic bounding functions for finding real roots of polynomials. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 63-73. doi: 10.3934/naco.2020015
[15]

He Zhang, John Harlim, Xiantao Li. Estimating linear response statistics using orthogonal polynomials: An RKHS formulation. Foundations of Data Science, 2020, 2 (4) : 443-485. doi: 10.3934/fods.2020021
[16]

Ágota P. Horváth. Discrete diffusion semigroups associated with Jacobi-Dunkl and exceptional Jacobi polynomials. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021002
[17]

Martin Heida, Stefan Neukamm, Mario Varga. Stochastic homogenization of $ \Lambda $-convex gradient flows. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 427-453. doi: 10.3934/dcdss.2020328
[18]

Gabrielle Nornberg, Delia Schiera, Boyan Sirakov. A priori estimates and multiplicity for systems of elliptic PDE with natural gradient growth. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3857-3881. doi: 10.3934/dcds.2020128
[19]

Aihua Fan, Jörg Schmeling, Weixiao Shen. $ L^\infty $-estimation of generalized Thue-Morse trigonometric polynomials and ergodic maximization. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 297-327. doi: 10.3934/dcds.2020363
[20]

Thomas Frenzel, Matthias Liero. Effective diffusion in thin structures via generalized gradient systems and EDP-convergence. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 395-425. doi: 10.3934/dcdss.2020345

2019 Impact Factor: 1.338

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences