Research ArticleNo Access

Marchenko–Pastur law with relaxed independence conditions

Jennifer Bryson

https://orcid.org/0000-0003-3120-0550

Department of Mathematics, University of California, Irvine, Irvine, CA 92697, USA

E-mail Address: jabryson@uci.edu

Corresponding author.

Search for more papers by this author

Roman Vershynin

Department of Mathematics, University of California, Irvine, Irvine, CA 92697, USA

E-mail Address: rvershyn@uci.edu

Search for more papers by this author

, and

Hongkai Zhao

Department of Mathematics, Duke University, Durham, NC 27708, USA

E-mail Address: zhao@math.duke.edu

Search for more papers by this author

https://doi.org/10.1142/S2010326321500404Cited by:12 (Source: Crossref)

Abstract

We prove the Marchenko–Pastur law for the eigenvalues of $p \times p$ sample covariance matrices in two new situations where the data does not have independent coordinates. In the first scenario — the block-independent model — the $p$ coordinates of the data are partitioned into blocks in such a way that the entries in different blocks are independent, but the entries from the same block may be dependent. In the second scenario — the random tensor model — the data is the homogeneous random tensor of order $d$ , i.e. the coordinates of the data are all $(\binom{n}{d})$ different products of $d$ variables chosen from a set of $n$ independent random variables. We show that Marchenko–Pastur law holds for the block-independent model as long as the size of the largest block is $o (p)$ , and for the random tensor model as long as $d = o (n^{1 / 3})$ . Our main technical tools are new concentration inequalities for quadratic forms in random variables with block-independent coordinates, and for random tensors.

Keywords:

AMSC: 15, 60

References

1. R. Adamczak , Logarithmic Sobolev inequalities and concentration of measure for convex functions and polynomial chaoses, Bull. Pol. Acad. Sci. Math. 53 (2005) 221–238. Crossref, Google Scholar
2. R. Adamczak , On the Marchenko–Pastur and circular law for some classes of random matrices with dependent entries, Electron. J. Prob. 16(37) (2011) 1068–1095. Google Scholar
3. R. Adamczak and R. Latala , Tail and moment estimates for chaoses generated by symmetric random variables with logarithmically concave tails, Ann. Inst. Henri Poincaré Probab. Stat. 48 (2012) 1103–1136. Google Scholar
4. R. Adamczak and P. Wolff , Concentration inequalities for non-Lipschitz functions with bounded derivatives of higher order, Probab. Theory Relat. Fields 162 (2015) 531–586. Crossref, Google Scholar
5. A. Ambainis, A. W. Harrow and M. B. Hastings , Random tensor theory: extending random matrix to mixtures of random product states, Commun. Math. Phys. 310 (2012) 25–74. Crossref, Google Scholar
6. A. Anandkumar, R. Ge, D. Hsu, S. Kakade and M. Telgarsky , Tensor decompositions for learning latent variable models, J. Mach. Learn. Res. 15 (2014) 2773–2832. Google Scholar
7. G. Aubrun , Random points in the unit ball of $l_{p}^{n}$ , Positivity 10(4) (2006) 755–759. Crossref, Google Scholar
8. A. Auffinger, G. Ben Arous and J. Cerny , Random matrices and complexity of spin glasses, Commun. Pure Appl. Math. 66 (2013) 165–201. Crossref, Google Scholar
9. Z. D. Bai , Methodologies in spectral analysis of large-dimensional random matrices, a review, Stat. Sin. 9 (1999) 611–677. Google Scholar
10. Z. D. Bai and J. W. Silverstein , Spectral Analysis of Large Dimensional Random Matrices, 2nd edn. (Springer, 2010). Crossref, Google Scholar
11. Z. Bai and W. Zhou , Large sample covariance matrices without independence structures in columns, Stat. Sin. 18 (2008) 425–442. Google Scholar
12. P. Baldi and R. Vershynin , Polynomial threshold functions, hyperplane arrangements, and random tensors, SIAM Journal on Mathematics of Data Science 1 (2019) 699–729. Crossref, Google Scholar
13. D. Banerjee and A. Bose , Bulk behavior of some patterned block matrices, Indian J. Pure Appl. Math. 47(2) (2016) 273–289. Crossref, Google Scholar
14. G. Ben Arous, S. Mei, A. Montanari and M. Nica , The landscape of the spiked tensor model, Commun. Pure Appl. Math. 72 (2019) 2282–2330. Crossref, Google Scholar
15. W. Bryc, A. Dembo and T. Jiang , Spectral measure of large random Hankel, Markov and Toeplitz matrices, Ann. Prob. 34(1) (2006) 1–38. Crossref, Google Scholar
16. W.-K. Chen , Phase transition in the spiked random tensor with Rademacher prior, Ann. Stat. 47 (2019) 2734–2756. Crossref, Google Scholar
17. R. Couillet and M. Debbah , Random Matrix Methods for Wireless Communications (Cambridge University Press, 2011). Crossref, Google Scholar
18. O. Friesen, M. Lowe and M. Stolz , Gaussian fluctuations for sample covariance matrices with dependent data, J. Multivar. Anal. 114 (2013) 270–287. Crossref, Google Scholar
19. R. Ge, F. Huang, C. Jin and Y. Yuan , Escaping from saddle points — online stochastic gradient for tensor decomposition, COLT 2015 (Conf. Learning Theory), Paris, France, pp. 797–842. Google Scholar
20. D. Ghoshdastidar and A. Dukkipati , Consistency of spectral hypergraph partitioning under planted partition model, Ann. Stat. 45 (2017) 289–315. Crossref, Google Scholar
21. F. Götze, H. Sambale and A. Sinulis, Concentration inequalities for polynomials in $α$ -sub-exponential random variables, preprint (2019), arXiv:1903.05964. Google Scholar
22. F. Götze and A. Tikhomirov, Limit theorems for spectra of positive random matrices under dependence, Zap. Nauchn. Sem. S.-Petersburg. Otdel. Mat. Inst. Steklov. (POMI) 311 (2004), Veroyatn. i Stat. 7, 92–123, 299. Google Scholar
23. F. Götze and A. Tikhomirov . Limit theorems for spectra of random matrices with martingale structure, in Stein’s Method and Applications (Singapore University Press, 2005), pp. 181–195. Link, Google Scholar
24. W. Hoeffding , A class of statistics with asymptotically normal distribution, Ann. Math. Stat. 19 (1948) 293–325. Crossref, Google Scholar
25. K. Hofmann-Credner and M. Stolz , Wigner theorems for random matrices with dependent entries: ensembles associated to symmetric spaces and sample covariance matrices, Electron. Commun. Probab. 13 (2008) 401–414. Crossref, Google Scholar
26. J. Hui and G. M. Pan , Limiting spectral distribution for large sample covariance matrices with m-dependent elements, Commun. Stat. Theory Methods 39 (2010) 935–941. Crossref, Google Scholar
27. P. Jain and S. Oh , Provable tensor factorization with missing data, NIPS 2014 (Advances in Neural Information Processing Systems), Montreal, Quebec, Canada, pp. 1431–1439. Google Scholar
28. N. El Karoui , Concentration of measure and spectra of random matrices: Applications to correlation matrices, elliptical distributions and beyond, Ann. Appl. Probab. 19(6) (2009) 2362–2405. Crossref, Google Scholar
29. C. Kim, A. S. Bandeira and M. X. Goemans , Community detection in hypergraphs, spiked tensor models, and sum-of-squares, SampTA 2017 (Int. Conf. Sampling Theory and Applications), Tallinn, Estonia, pp. 124–128. Google Scholar
30. L. Laloux, P. Cizeau, M. Potters and J.-P. Bouchaud , Random matrix theory and financial correlations, Int. J. Theor. Appl. Finance 1(3) (2000) 391–397. Link, Google Scholar
31. R. Latala , Estimates of moments and tails of Gaussian chaoses, Ann. Probab. 34 (2006) 2315–2331. Crossref, Google Scholar
32. R. Latala and R. Lochowski , Moment and tail estimates for multidimensional chaos generated by positive random variables with logarithmically concave tails, Progress in Probability 56 (2003) 77–92. Google Scholar
33. J. Lehec , Moments of the Gaussian chaos, in Seminaire de Probabilites XLIII, Lecture Notes in Mathematics (2006) (Springer, Berlin, 2011), pp. 327–340. Crossref, Google Scholar
34. P. Loubaton , On the almost sure location of the singular values of certain Gaussian block-Hankel large random matrices, J. Theoretical Probab. 29(4) (2016) 1339–1443. Crossref, Google Scholar
35. A. Lytova , Central limit theorem for linear eigenvalue statistics for a tensor product version of sample covariance matrices, J. Theor. Prob. 31 (2018) 1024–1057. Crossref, Google Scholar
36. V. A. Marchenko and L. A. Pastur , Distribution of eigenvalues for some sets of random matrices, Math. USSR Sbornik 1 (1967) 457–483. Crossref, Google Scholar
37. A. Montanari and N. Sun , Spectral algorithms for tensor completion, Commun. Pure Appl. Math. 71 (2018) 2381–2425. Crossref, Google Scholar
38. N. H. Nguyen, P. Drineas and T. D. Tran , Tensor sparsification via a bound on the spectral norm of random tensors, Inf. Inference J. IMA 4 (2015) 195–229. Crossref, Google Scholar
39. S. O’Rourke , A note on the Marchenko–Pastur law for a class of random matrices with dependent entries, Electron. Commun. Probab. 17(28) (2012) 1–13. Google Scholar
40. A. Pajor and L. Pastur , On the limiting empirical measure of eigenvalues of the sum of rank one matrices with log-concave distribution, Stud. Math. 195(1) (2009) 11–29. Crossref, Google Scholar
41. L. Pastur and M. Shcherbina , Eigenvalue distribution of large random matrices, Mathematical Surveys and Monographs, Vol. 171 (American Mathematical Society, Providence, RI, 2011). Google Scholar
42. V. Plerou, P. Gopikrishnan, B. Rosenow, L. Amaral, T. Guhr and H. Stanley , Random matrix approach to cross correlations in financial data, Phys. Rev. E 64 (2002) 66126-66144. Google Scholar
43. E. Richard and A. Montanari , A statistical model for tensor PCA, NIPS 2014 (Advances in Neural Information Processing Systems), Montreal, Quebec, Canada, pp. 2897–2905. Google Scholar
44. M. Rudelson and R. Vershynin , Hanson-Wright inequality and sub-gaussian concentration, Electron. Commun. Probab. 18 (2013) 1–9. Crossref, Google Scholar
45. R. Vershynin , High-Dimensional Probability: An Introduction with Applications in Data Science (Cambridge University Press, 2018). Crossref, Google Scholar
46. R. Vershynin , Concentration inequalities for random tensors, Bernoulli 26 (2020) 3139–3162. Crossref, Google Scholar
47. Y. Wang, H.-Y. Tung, A. J. Smola and A. Anandkumar , Fast and guaranteed tensor decomposition via sketching, NIPS 2015 (Advances in Neural Information Processing Systems), Montreal, Quebec, Canada, pp. 991–999. Google Scholar
48. M. Wei, G. Yang and L. Ying , The limiting spectral distribution for large sample covariance matrices with unbounded m-dependent entries, Commun. Stat. Theory Methods 45 (2016) 6651–6662. Crossref, Google Scholar
49. J. Yao , A note on a Marchenko–Pastur type theorem for time series, Statist. Probab. Lett. 82 (2012) 20–28. Crossref, Google Scholar
50. P. Yaskov , LLN for quadratic forms of long memory time series and its applications in random matrix theory, J. Theor. Probability 31(4) (2018) 2032–2055. Crossref, Google Scholar
51. P. Yaskov , Necessary and sufficient conditions for the Marchenko–Pastur theorem, Electron. Commun. Probab. 21(73) (2016) 1–8. Google Scholar
52. P. Yaskov , A short proof of the Marchenko–Pastur theorem, C. R. Math. Acad. Sci. Paris Ser. I, 354 (2016) 319–322. Crossref, Google Scholar
53. Y. Q. Yin and P. R. Krishnaiah , Limit theorems for the eigenvalues of product of large-dimensional random matrices when the underlying distribution is isotropic, Teor. Veroyatnost. i Primenen. 31 (1986) 394–398. Google Scholar
54. Z. Zhou and Y. Zhu, Sparse random tensors: concentration, regularization and applications, submitted (2019), arXiv:1911.09063. Google Scholar