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

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

[3]

P. Deift, Orthogonal Polynomials and Random Matrices: A Riemann-Hilbert Approach, Amer. Math. Soc., Providence, RI, 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-782. 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-1552.

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

[7]

A. Edelman, Eigenvalues and condition numbers of random matrices, SIAM J. Matrix Anal. Appl., 9 (1988), 543-560. 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-430. doi: 10.1007/BF02096594.

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

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

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

[12]

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

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

[14]

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

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

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

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

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

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

[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-372. 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, Providence, Rhode Island, mar 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-1001. doi: 10.1214/aoms/1177699378.

[24]

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

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

[26]

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

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

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

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.

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

[3]

P. Deift, Orthogonal Polynomials and Random Matrices: A Riemann-Hilbert Approach, Amer. Math. Soc., Providence, RI, 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-782. 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-1552.

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

[7]

A. Edelman, Eigenvalues and condition numbers of random matrices, SIAM J. Matrix Anal. Appl., 9 (1988), 543-560. 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-430. doi: 10.1007/BF02096594.

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

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

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

[12]

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

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

[14]

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

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

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

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

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

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

[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-372. 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, Providence, Rhode Island, mar 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-1001. doi: 10.1214/aoms/1177699378.

[24]

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

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

[26]

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

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

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

[1]

Zhong-Qing Wang, Ben-Yu Guo, Yan-Na Wu. Pseudospectral method using generalized Laguerre functions for singular problems on unbounded domains. Discrete and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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]

Zhiyan Ding, Qin Li. Constrained Ensemble Langevin Monte Carlo. Foundations of Data Science, 2022, 4 (1) : 37-70. doi: 10.3934/fods.2021034
[13]

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

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

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

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

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

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

Andreas Bock, Colin J. Cotter. Learning landmark geodesics using the ensemble Kalman filter. Foundations of Data Science, 2021, 3 (4) : 701-727. doi: 10.3934/fods.2021020
[20]

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

2021 Impact Factor: 1.588

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy