The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices ☆
- Florent Benaych-Georgesa, b,
, , - Raj Rao Nadakuditic,
, ,
- a LPMA, UPMC Univ Paris 6, Case courier 188, 4, Place Jussieu, 75252 Paris Cedex 05, France
- b CMAP, École Polytechnique, route de Saclay, 91128 Palaiseau Cedex, France
- c Department of Electrical Engineering and Computer Science, University of Michigan, 1301 Beal Avenue, Ann Arbor, MI 48109, USA
- Received 12 October 2009
- Accepted 9 February 2011
- Available online 23 February 2011
- Communicated by Dan Voiculescu
Abstract
We consider the eigenvalues and eigenvectors of finite, low rank perturbations of random matrices. Specifically, we prove almost sure convergence of the extreme eigenvalues and appropriate projections of the corresponding eigenvectors of the perturbed matrix for additive and multiplicative perturbation models.
The limiting non-random value is shown to depend explicitly on the limiting eigenvalue distribution of the unperturbed random matrix and the assumed perturbation model via integral transforms that correspond to very well-known objects in free probability theory that linearize non-commutative free additive and multiplicative convolution. Furthermore, we uncover a phase transition phenomenon whereby the large matrix limit of the extreme eigenvalues of the perturbed matrix differs from that of the original matrix if and only if the eigenvalues of the perturbing matrix are above a certain critical threshold. Square root decay of the eigenvalue density at the edge is sufficient to ensure that this threshold is finite. This critical threshold is intimately related to the same aforementioned integral transforms and our proof techniques bring this connection and the origin of the phase transition into focus. Consequently, our results extend the class of ‘spiked’ random matrix models about which such predictions (called the BBP phase transition) can be made well beyond the Wigner, Wishart and Jacobi random ensembles found in the literature. We examine the impact of this eigenvalue phase transition on the associated eigenvectors and observe an analogous phase transition in the eigenvectors. Various extensions of our results to the problem of non-extreme eigenvalues are discussed.
MSC
- 15A52;
- 46L54;
- 60F99
Keywords
- Random matrices;
- Haar measure;
- Principal components analysis;
- Informational limit;
- Free probability;
- Phase transition;
- Random eigenvalues;
- Random eigenvectors;
- Random perturbation;
- Sample covariance matrices
References
- [1]
An Introduction to Random Matrices
Cambridge Stud. Adv. Math., vol. 118Cambridge University Press (2010)
- [2]
Restricted rank modification of the symmetric eigenvalue problem: theoretical considerations
Linear Algebra Appl., 104 (1988), pp. 75–95
- [3]
Spectral Analysis of Large Dimensional Random Matrices
(second ed.)Springer, New York (2009)
- [4]
Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices
Ann. Probab., 33 (5) (2005), pp. 1643–1697
- [5]
Eigenvalues of large sample covariance matrices of spiked population models
J. Multivariate Anal., 97 (6) (2006), pp. 1382–1408
- [6]
Eigenvalue separation in some random matrix models
J. Math. Phys., 50 (3) (2009), p. 033302 24 pp
- [7]
Infinitely divisible distributions for rectangular free convolution: classification and matricial interpretation
Probab. Theory Related Fields, 139 (1–2) (2007), pp. 143–189
- [8]
Rectangular random matrices, related convolution
Probab. Theory Related Fields, 144 (3) (2009), pp. 471–515
- [9]
Rectangular R-transform at the limit of rectangular spherical integrals
available online at http://arxiv.org/abs/0909.0178 (2009)
- [10]
On a surprising relation between the Marchenko–Pastur law, rectangular and square free convolutions
Ann. Inst. H. Poincaré Probab. Statist., 46 (3) (2010), pp. 644–652
- [11]
Fluctuations of the extreme eigenvalues of finite rank deformations of random matrices
available online at http://arxiv.org/abs/1009.0145 (2010)
- [12]
Large deviations of the extreme eigenvalues of finite rank deformations of random matrices
available online at http://arxiv.org/abs/1009.0135 (2010)
- [13]
- F. Benaych-Georges, R.R. Nadakuditi, The extreme singular values and singular vectors of finite, low rank perturbations of large random rectangular matrices, in preparation.
- [14]
Rank-one modification of the symmetric eigenproblem
Numer. Math., 31 (1) (1978/1979), pp. 31–48
- [15]
The largest eigenvalues of finite rank deformation of large Wigner matrices: convergence and nonuniversality of the fluctuations
Ann. Probab., 37 (1) (2009), pp. 1–47
- [16]
Product of random projections, Jacobi ensembles and universality problems arising from free probability
Probab. Theory Related Fields, 133 (3) (2005), pp. 315–344
- [17]
Integration with respect to the Haar measure on unitary, orthogonal and symplectic group
Comm. Math. Phys., 264 (3) (2006), pp. 773–795
- [18]
Uniform asymptotics for polynomials orthogonal with respect to varying exponential weights and applications to universality questions in random matrix theory
Comm. Pure Appl. Math., 52 (1999), pp. 1335–1425
- [19]
Tracy–Widom limit for the largest eigenvalue of a large class of complex sample covariance matrices
Ann. Probab., 35 (2) (2007), pp. 663–714
- [20]
The largest eigenvalue of rank one deformation of large Wigner matrices
Comm. Math. Phys., 272 (1) (2007), pp. 185–228
- [21]
Character expansion method for the first order asymptotics of a matrix integral
Probab. Theory Related Fields, 132 (4) (2005), pp. 539–578
- [22]
A Fourier view on the R-transform and related asymptotics of spherical integrals
J. Funct. Anal., 222 (2) (2005), pp. 435–490
- [23]
The Semicircle Law, Free Random Variables and Entropy
Math. Surveys Monogr., vol. 77Amer. Math. Soc., Providence, RI (2000)
- [24]
Matrix Analysis
Cambridge University Press, Cambridge (1985)
- [25]
Statistical mechanics of learning multiple orthogonal signals: asymptotic theory and fluctuation effects
Phys. Rev. E (3), 75 (1) (2007), p. 016101 13 pp
- [26]
Refined perturbation bounds for eigenvalues of Hermitian and non-Hermitian matrices
SIAM J. Matrix Anal. Appl., 31 (1) (2009), pp. 40–53
- [27]
Generic behavior of the density of states in random matrix theory and equilibrium problems in the presence of real analytic external fields
Comm. Pure Appl. Math., 53 (2000), pp. 736–785
- [28]
The Concentration of Measure Phenomenon
Amer. Math. Soc., Providence, RI (2001)
- [29]
Distribution of eigenvalues in certain sets of random matrices
Mat. Sb. (N.S.), 72 (114) (1967), pp. 507–536
- [30]
Fundamental limit of sample generalized eigenvalue based detection of signals in noise using relatively few signal-bearing and noise-only samples
J. Selected Top. Sig. Processing, 4 (3) (2010), pp. 468–480
- [31]
Finite sample approximation results for principal component analysis: a matrix perturbation approach
Ann. Statist., 36 (6) (2008), pp. 2791–2817
- [32]
Asymptotics of sample eigenstructure for a large dimensional spiked covariance model
Statist. Sinica, 17 (4) (2007), pp. 1617–1642
- [33]
The largest eigenvalue of small rank perturbations of Hermitian random matrices
Probab. Theory Related Fields, 134 (1) (2006), pp. 127–173
- [34]
The polynomial method for random matrices
Found. Comput. Math., 8 (6) (2008), pp. 649–702
- [35]
Some limit theorems on the eigenvectors of large-dimensional sample covariance matrices
J. Multivariate Anal., 15 (3) (1984), pp. 295–324
- [36]
On the eigenvectors of large-dimensional sample covariance matrices
J. Multivariate Anal., 30 (1) (1989), pp. 1–16
- [37]
Weak convergence of random functions defined by the eigenvectors of sample covariance matrices
J. Multivariate Anal., 18 (3) (1990), pp. 1–16
- [38]
Analysis of the limiting spectral distribution of large-dimensional random matrices
J. Multivariate Anal., 54 (2) (1995), pp. 295–309
- [39]
Matrix Perturbation Theory
Comput. Sci. Sci. Comput.Academic Press Inc., Boston, MA (1990)
- [40]
Free Random Variables
CRM Monogr. Ser., vol. 1Amer. Math. Soc., Providence, RI (1992)
- [41]
On the distribution of the roots of certain symmetric matrices
Ann. of Math. (2), 67 (1958), pp. 325–327
- ☆
F.B.G.ʼs work was partially supported by the Agence Nationale de la Recherche grant ANR-08-BLAN-0311-03. R.R.N.ʼs research was partially supported by an Office of Naval Research postdoctoral fellowship award and grant N00014-07-1-0269. R.R.N. thanks Arthur Baggeroer for his feedback, support and encouragement. We thank Alan Edelman for feedback and encouragement and for facilitating this collaboration by hosting F.B.G.ʼs stay at M.I.T. We gratefully acknowledge the Singapore-MIT alliance for funding F.B.G.ʼs stay.
- Corresponding author.
Copyright © 2011 Elsevier Inc. All rights reserved.
