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

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

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.
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.

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

[3]

P. Deift, Orthogonal Polynomials and Random Matrices: A Riemann-Hilbert Approach,, Amer. Math. Soc., (1999).

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

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

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

[7]

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

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

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

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

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

[12]

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

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

[14]

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

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

[16]

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

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

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

[19]

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

[20]

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

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

[22]

B Simon, Trace Ideals and Their Applications, volume 120 of Mathematical Surveys and Monographs,, American Mathematical Society, (2010).

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

[24]

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

[25]

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

[26]

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

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

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

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.

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

[3]

P. Deift, Orthogonal Polynomials and Random Matrices: A Riemann-Hilbert Approach,, Amer. Math. Soc., (1999).

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

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

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

[7]

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

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

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

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

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

[12]

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

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

[14]

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

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

[16]

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

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

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

[19]

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

[20]

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

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

[22]

B Simon, Trace Ideals and Their Applications, volume 120 of Mathematical Surveys and Monographs,, American Mathematical Society, (2010).

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

[24]

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

[25]

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

[26]

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

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

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

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

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

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

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

[15]

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

[16]

Aviv Gibali, Dang Thi Mai, Nguyen The Vinh. A new relaxed CQ algorithm for solving split feasibility problems in Hilbert spaces and its applications. Journal of Industrial & Management Optimization, 2019, 15 (2) : 963-984. doi: 10.3934/jimo.2018080

[17]

Nur Fadhilah Ibrahim. An algorithm for the largest eigenvalue of nonhomogeneous nonnegative polynomials. Numerical Algebra, Control & Optimization, 2014, 4 (1) : 75-91. doi: 10.3934/naco.2014.4.75

[18]

Irene Benedetti, Luisa Malaguti, Valentina Taddei. Nonlocal problems in Hilbert spaces. Conference Publications, 2015, 2015 (special) : 103-111. doi: 10.3934/proc.2015.0103

[19]

C.Y. Wang, M.X. Li. Convergence property of the Fletcher-Reeves conjugate gradient method with errors. Journal of Industrial & Management Optimization, 2005, 1 (2) : 193-200. doi: 10.3934/jimo.2005.1.193

[20]

Shishun Li, Zhengda Huang. Guaranteed descent conjugate gradient methods with modified secant condition. Journal of Industrial & Management Optimization, 2008, 4 (4) : 739-755. doi: 10.3934/jimo.2008.4.739

2017 Impact Factor: 1.179

Metrics

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

Other articles
by authors

[Back to Top]