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]

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]

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, 2017, 22 (11) : 0-0. doi: 10.3934/dcdsb.2020132
[3]

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

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

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

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

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

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

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

Minlong Lin, Ke Tang. Selective further learning of hybrid ensemble for class imbalanced increment learning. Big Data & Information Analytics, 2017, 2 (1) : 1-21. doi: 10.3934/bdia.2017005
[15]

Junyoung Jang, Kihoon Jang, Hee-Dae Kwon, Jeehyun Lee. Feedback control of an HBV model based on ensemble kalman filter and differential evolution. Mathematical Biosciences & Engineering, 2018, 15 (3) : 667-691. doi: 10.3934/mbe.2018030
[16]

Nicolas Augier, Ugo Boscain, Mario Sigalotti. Semi-conical eigenvalue intersections and the ensemble controllability problem for quantum systems. Mathematical Control & Related Fields, 2019, 0 (0) : 0-0. doi: 10.3934/mcrf.2020023
[17]

Vladimir S. Gerdjikov, Rossen I. Ivanov, Aleksander A. Stefanov. Riemann-Hilbert problem, integrability and reductions. Journal of Geometric Mechanics, 2019, 11 (2) : 167-185. doi: 10.3934/jgm.2019009
[18]

Sie Long Kek, Mohd Ismail Abd Aziz, Kok Lay Teo. A gradient algorithm for optimal control problems with model-reality differences. Numerical Algebra, Control & Optimization, 2015, 5 (3) : 251-266. doi: 10.3934/naco.2015.5.251
[19]

Feng Bao, Thomas Maier. Stochastic gradient descent algorithm for stochastic optimization in solving analytic continuation problems. Foundations of Data Science, 2020, 2 (1) : 1-17. doi: 10.3934/fods.2020001
[20]

Gillala Rekha, V Krishna Reddy, Amit Kumar Tyagi. A novel approach for solving skewed classification problem using cluster based ensemble method. Mathematical Foundations of Computing, 2020, 3 (1) : 1-9. doi: 10.3934/mfc.2020001

2018 Impact Factor: 1.143

Tools

Metrics

  • PDF downloads (47)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences