Asymptotic analysis for extreme eigenvalues of principal minors of random matrices. (English) Zbl 1486.60010
The current paper focuses on random matrices. More precisely, the authors consider white Wishart matrices \(W=(w_{ij})_{1\leq i,j\leq p}=X^TX\), where \(X=(x_{ij})_{1\leq \leq n, 1\leq j\leq p}\) and \(x_{ij}\) are independent standard normally distributed random variables. For a subset \(S\) of the index set \(\{1,\ldots, p\}\) with \(|S|=k\), the \(S\)-principal minor of \(W\) is denoted by \(W_S=(w_{ij})_{i,j\in S}\). If one denotes by \(\lambda_1(W_S)\geq \ldots \geq \lambda_k(W_s)\) the eigenvalues of \(W_S\) in descending order, the quantities of interest during the current work are the largest and the smallest eigenvalues of all the \(k \times k\) principal minors of \(W\) in the setting that \(n, p,\) and \(k\) are large but \(k\) relatively smaller than \(\min \{n,p\}\). For the extreme eigenvalues
\[
\lambda_{\max}(k)=\max_{1\leq i\leq k,S\subset \{1,\dots, p\}, |S|=k }\lambda_i(W_S)
\]
and
\[
\lambda_{\min}(k)=\min_{1\leq i\leq k,S\subset \{1,\dots, p\}, |S|=k }\lambda_i(W_S)
\]
the asymptotic behaviour is investigated. The results are then applied in the construction of compressed sensing matrices.
Reviewer: Ecaterina Sava-Huss (Innsbruck)
MSC:
| 60B20 | Random matrices (probabilistic aspects) |
| 60F99 | Limit theorems in probability theory |
| 60K35 | Interacting random processes; statistical mechanics type models; percolation theory |
| 15B52 | Random matrices (algebraic aspects) |
| 15A18 | Eigenvalues, singular values, and eigenvectors |
Keywords:
extremal eigenvalues; maximum of random variables; minimum of random variables; random matrixReferences:
| [1] | Anderson, T. W. (1962). An Introduction to Multivariate Statistical Analysis. Wiley, New York. |
| [2] | Arratia, R., Goldstein, L. and Gordon, L. (1990). Poisson approximation and the Chen-Stein method. Statist. Sci. 5 403-434. · Zbl 0955.62542 |
| [3] | Bai, Z. D. (1999). Methodologies in spectral analysis of large-dimensional random matrices, a review. Statist. Sinica 9 611-677. · Zbl 0949.60077 |
| [4] | Bai, Z. and Silverstein, J. W. (2010). Spectral Analysis of Large Dimensional Random Matrices, 2nd ed. Springer Series in Statistics. Springer, New York. · Zbl 1301.60002 · doi:10.1007/978-1-4419-0661-8 |
| [5] | Bai, Z. D. and Yin, Y. Q. (1993). Limit of the smallest eigenvalue of a large-dimensional sample covariance matrix. Ann. Probab. 21 1275-1294. · Zbl 0779.60026 |
| [6] | Baraniuk, R., Davenport, M., DeVore, R. and Wakin, M. (2008). A simple proof of the restricted isometry property for random matrices. Constr. Approx. 28 253-263. · Zbl 1177.15015 · doi:10.1007/s00365-007-9003-x |
| [7] | Bryc, W., Dembo, A. and Jiang, T. (2006). Spectral measure of large random Hankel, Markov and Toeplitz matrices. Ann. Probab. 34 1-38. · Zbl 1094.15009 · doi:10.1214/009117905000000495 |
| [8] | Bump, D. and Diaconis, P. (2002). Toeplitz minors. J. Combin. Theory Ser. A 97 252-271. · Zbl 1005.47030 · doi:10.1006/jcta.2001.3214 |
| [9] | Cai, T., Fan, J. and Jiang, T. (2013). Distributions of angles in random packing on spheres. J. Mach. Learn. Res. 14 1837-1864. · Zbl 1318.60017 |
| [10] | Cai, T. T. and Jiang, T. (2012). Phase transition in limiting distributions of coherence of high-dimensional random matrices. J. Multivariate Anal. 107 24-39. · Zbl 1352.60006 · doi:10.1016/j.jmva.2011.11.008 |
| [11] | Cai, T. T., Wang, L. and Xu, G. (2009). Shifting inequality and recovery of sparse signals. IEEE Trans. Signal Process. 58 1300-1308. · Zbl 1392.94117 |
| [12] | Cai, T. T., Wang, L. and Xu, G. (2010). New bounds for restricted isometry constants. IEEE Trans. Inf. Theory 56 4388-4394. · Zbl 1366.94181 · doi:10.1109/TIT.2010.2054730 |
| [13] | Cai, T. T. and Zhang, A. (2013). Sharp RIP bound for sparse signal and low-rank matrix recovery. Appl. Comput. Harmon. Anal. 35 74-93. · Zbl 1310.94021 · doi:10.1016/j.acha.2012.07.010 |
| [14] | Cai, T. T. and Zhang, A. (2014). Sparse representation of a polytope and recovery in sparse signals and low-rank matrices. IEEE Trans. Inf. Theory 60 122-132. · Zbl 1364.94114 · doi:10.1109/TIT.2013.2288639 |
| [15] | Candès, E. J. (2008). The restricted isometry property and its implications for compressed sensing. C. R. Math. Acad. Sci. Paris 346 589-592. · Zbl 1153.94002 · doi:10.1016/j.crma.2008.03.014 |
| [16] | Candes, E. J. and Tao, T. (2005). Decoding by linear programming. IEEE Trans. Inf. Theory 51 4203-4215. · Zbl 1264.94121 · doi:10.1109/TIT.2005.858979 |
| [17] | Candes, E. and Tao, T. (2007). The Dantzig selector: Statistical estimation when \(p\) is much larger than \(n\). Ann. Statist. 35 2313-2351. · Zbl 1139.62019 · doi:10.1214/009053606000001523 |
| [18] | Dallaporta, S. and De Castro, Y. (2019). Sparse recovery from extreme eigenvalues deviation inequalities. ESAIM Probab. Stat. 23 430-463. · Zbl 1447.60055 · doi:10.1051/ps/2018024 |
| [19] | Diaconis, P. and Evans, S. N. (2001). Linear functionals of eigenvalues of random matrices. Trans. Amer. Math. Soc. 353 2615-2633. · Zbl 1008.15013 · doi:10.1090/S0002-9947-01-02800-8 |
| [20] | Donoho, D. L. (2006). Compressed sensing. IEEE Trans. Inf. Theory 52 1289-1306. · Zbl 1288.94016 · doi:10.1109/TIT.2006.871582 |
| [21] | Donoho, D. L., Elad, M. and Temlyakov, V. N. (2006). Stable recovery of sparse overcomplete representations in the presence of noise. IEEE Trans. Inf. Theory 52 6-18. · Zbl 1288.94017 · doi:10.1109/TIT.2005.860430 |
| [22] | Doumerc, Y. (2002). An asymptotic link between LUE and GUE and its spectral interpretation. arXiv preprint math/0204175. |
| [23] | Dyson, F. J. (1962a). Statistical theory of the energy levels of complex systems. I. J. Math. Phys. 3 140-156. · Zbl 0105.41604 · doi:10.1063/1.1703773 |
| [24] | Dyson, F. J. (1962b). Statistical theory of the energy levels of complex systems. II. J. Math. Phys. 3 157-165. · Zbl 0105.41604 · doi:10.1063/1.1703774 |
| [25] | Dyson, F. J. (1962c). Statistical theory of the energy levels of complex systems. III. J. Math. Phys. 3 166-175. · Zbl 0105.41604 · doi:10.1063/1.1703775 |
| [26] | Edelman, A. (1988). Eigenvalues and condition numbers of random matrices. SIAM J. Matrix Anal. Appl. 9 543-560. · Zbl 0678.15019 · doi:10.1137/0609045 |
| [27] | Fan, J., Shao, Q.-M. and Zhou, W.-X. (2018). Are discoveries spurious? Distributions of maximum spurious correlations and their applications. Ann. Statist. 46 989-1017. · Zbl 1402.62097 · doi:10.1214/17-AOS1575 |
| [28] | Fey, A., van der Hofstad, R. and Klok, M. J. (2008). Large deviations for eigenvalues of sample covariance matrices, with applications to mobile communication systems. Adv. in Appl. Probab. 40 1048-1071. · Zbl 1255.60039 |
| [29] | Horn, R. A. and Johnson, C. R. (2012). Matrix Analysis. Cambridge Univ. Press, Cambridge. |
| [30] | James, A. T. (1964). Distributions of matrix variates and latent roots derived from normal samples. Ann. Math. Stat. 35 475-501. · Zbl 0121.36605 · doi:10.1214/aoms/1177703550 |
| [31] | Jiang, T. (2004a). The asymptotic distributions of the largest entries of sample correlation matrices. Ann. Appl. Probab. 14 865-880. · Zbl 1047.60014 · doi:10.1214/105051604000000143 |
| [32] | Jiang, T. (2004b). The limiting distributions of eigenvalues of sample correlation matrices. Sankhyā 66 35-48. · Zbl 1193.62018 |
| [33] | Jiang, T. and Li, D. (2015). Approximation of rectangular beta-Laguerre ensembles and large deviations. J. Theoret. Probab. 28 804-847. · Zbl 1333.15032 · doi:10.1007/s10959-013-0519-7 |
| [34] | Johansson, K. (1990). On Szego’s asymptotic formula for Toeplitz determinants and generalizations. · Zbl 0661.30001 |
| [35] | Johnstone, I. M. (2001). On the distribution of the largest eigenvalue in principal components analysis. Ann. Statist. 29 295-327. · Zbl 1016.62078 · doi:10.1214/aos/1009210544 |
| [36] | Johnstone, I. M. (2008). Multivariate analysis and Jacobi ensembles: Largest eigenvalue, Tracy-Widom limits and rates of convergence. Ann. Statist. 36 2638-2716. · Zbl 1284.62320 · doi:10.1214/08-AOS605 |
| [37] | Laurent, B. and Massart, P. (2000). Adaptive estimation of a quadratic functional by model selection. Ann. Statist. 28 1302-1338. · Zbl 1105.62328 |
| [38] | Li, D., Liu, W.-D. and Rosalsky, A. (2010). Necessary and sufficient conditions for the asymptotic distribution of the largest entry of a sample correlation matrix. Probab. Theory Related Fields 148 5-35. · Zbl 1210.62010 · doi:10.1007/s00440-009-0220-z |
| [39] | Li, D., Qi, Y. and Rosalsky, A. (2012). On Jiang’s asymptotic distribution of the largest entry of a sample correlation matrix. J. Multivariate Anal. 111 256-270. · Zbl 1275.62037 · doi:10.1016/j.jmva.2012.04.002 |
| [40] | Li, D. and Rosalsky, A. (2006). Some strong limit theorems for the largest entries of sample correlation matrices. Ann. Appl. Probab. 16 423-447. · Zbl 1098.60034 · doi:10.1214/105051605000000773 |
| [41] | Mehta, M. L. (2004). Random Matrices, 3rd ed. Pure and Applied Mathematics (Amsterdam) 142. Elsevier/Academic Press, Amsterdam. |
| [42] | Mo, Q. and Li, S. (2011). New bounds on the restricted isometry constant \[{\delta_{2k}}\]. Appl. Comput. Harmon. Anal. 31 460-468. · Zbl 1231.94027 · doi:10.1016/j.acha.2011.04.005 |
| [43] | Muirhead, R. J. (2009). Aspects of Multivariate Statistical Theory 197. Wiley, New York. |
| [44] | Péché, S. (2009). Universality results for the largest eigenvalues of some sample covariance matrix ensembles. Probab. Theory Related Fields 143 481-516. · Zbl 1167.62019 · doi:10.1007/s00440-007-0133-7 |
| [45] | Rogers, C. A. (1963). Covering a sphere with spheres. Mathematika 10 157-164. · Zbl 0158.19603 · doi:10.1112/S0025579300004083 |
| [46] | Shao, Q.-M. and Zhou, W.-X. (2014). Necessary and sufficient conditions for the asymptotic distributions of coherence of ultra-high dimensional random matrices. Ann. Probab. 42 623-648. · Zbl 1354.60020 · doi:10.1214/13-AOP837 |
| [47] | Szeg, G. (1939). Orthogonal Polynomials 23. Amer. Math. Soc., Providence. |
| [48] | Tao, T. and Vu, V. (2010). Random matrices: Universality of ESDs and the circular law. Ann. Probab. 38 2023-2065. · Zbl 1203.15025 · doi:10.1214/10-AOP534 |
| [49] | Tracy, C. A. and Widom, H. (1994). Level spacing distributions and the Bessel kernel. Comm. Math. Phys. 161 289-309. · Zbl 0808.35145 |
| [50] | Tracy, C. A. and Widom, H. (1996). On orthogonal and symplectic matrix ensembles. Comm. Math. Phys. 177 727-754. · Zbl 0851.60101 |
| [51] | Tracy, C. A. and Widom, H. (2000). The distribution of the largest eigenvalue in the Gaussian ensembles: \[ \beta =1,2,4\]. In Calogero-Moser-Sutherland Models (Montréal, QC, 1997). CRM Ser. Math. Phys. 461-472. Springer, New York. |
| [52] | Tracy, C. A. and Widom, H. (2002). On the limit of some Toeplitz-like determinants. SIAM J. Matrix Anal. Appl. 23 1194-1196. · Zbl 1010.47019 · doi:10.1137/S0895479801395367 |
| [53] | Wigner, E. P. (1955). Characteristic vectors of bordered matrices with infinite dimensions. Ann. of Math. (2) 62 548-564. · Zbl 0067.08403 · doi:10.2307/1970079 |
| [54] | Wigner, E. P. (1958). On the distribution of the roots of certain symmetric matrices. Ann. of Math. (2) 67 325-327. · Zbl 0085.13203 · doi:10.2307/1970008 |
| [55] | Zhang, R. and Li, S. (2018). A proof of conjecture on restricted isometry property constants \[{\delta_{tk}} (0\textless t\textless 4/3)\]. IEEE Trans. Inf. Theory 64 1699-1705. · Zbl 1390.94508 · doi:10.1109/TIT.2017.2705741 |
| [56] | Zhou, W. (2007). Asymptotic distribution of the largest off-diagonal entry of correlation matrices. Trans. Amer. Math. Soc. 359 5345-5363 · Zbl 1130.60032 · doi:10.1090/S0002-9947-07-04192-X |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
