The probabilistic estimates on the largest and smallest 𝑞-singular values of random matrices

Lai, Ming-Jun; Liu, Yang

doi:10.1090/S0025-5718-2014-02895-0

The probabilistic estimates on the largest and smallest $q$-singular values of random matrices
HTML articles powered by AMS MathViewer

by Ming-Jun Lai and Yang Liu PDF

Math. Comp. 84 (2015), 1775-1794 Request permission

Abstract:

We study the $q$-singular values of random matrices with pre-Gaussian entries defined in terms of the $\ell _{q}$-quasinorm with $0<q\le 1$. In this paper, we mainly consider the decay of the lower and upper tail probabilities of the largest $q$-singular value $s_{1}^{(q)}$, when the number of rows of the matrices becomes very large. Based on the results in probabilistic estimates on the largest $q$-singular value, we also give probabilistic estimates on the smallest $q$-singular value for pre-Gaussian random matrices.

References

Z. D. Bai, Jack W. Silverstein, and Y. Q. Yin, A note on the largest eigenvalue of a large-dimensional sample covariance matrix, J. Multivariate Anal. 26 (1988), no. 2, 166–168. MR 963829, DOI 10.1016/0047-259X(88)90078-4
G. Bennett, V. Goodman, and C. M. Newman, Norms of random matrices, Pacific J. Math. 59 (1975), no. 2, 359–365. MR 393085
V. V. Buldygin and Yu. V. Kozachenko, Metric characterization of random variables and random processes, Translations of Mathematical Monographs, vol. 188, American Mathematical Society, Providence, RI, 2000. Translated from the 1998 Russian original by V. Zaiats. MR 1743716, DOI 10.1090/mmono/188
Rick Chartrand and Valentina Staneva, Restricted isometry properties and nonconvex compressive sensing, Inverse Problems 24 (2008), no. 3, 035020, 14. MR 2421974, DOI 10.1088/0266-5611/24/3/035020
Alan Edelman, Eigenvalues and condition numbers of random matrices, SIAM J. Matrix Anal. Appl. 9 (1988), no. 4, 543–560. MR 964668, DOI 10.1137/0609045
Alan Stuart Edelman, Eigenvalues and condition numbers of random matrices, ProQuest LLC, Ann Arbor, MI, 1989. Thesis (Ph.D.)–Massachusetts Institute of Technology. MR 2941174
A. Fisher, The Mathematical Theory of Probabilities and its Application to Frequency Curves and Statistical Methods, vol. 1, The Macmillan Company, 1922.
Simon Foucart and Ming-Jun Lai, Sparsest solutions of underdetermined linear systems via $l_q$-minimization for $0<q\leq 1$, Appl. Comput. Harmon. Anal. 26 (2009), no. 3, 395–407. MR 2503311, DOI 10.1016/j.acha.2008.09.001
Simon Foucart and Ming-Jun Lai, Sparse recovery with pre-Gaussian random matrices, Studia Math. 200 (2010), no. 1, 91–102. MR 2720209, DOI 10.4064/sm200-1-6
Stuart Geman, A limit theorem for the norm of random matrices, Ann. Probab. 8 (1980), no. 2, 252–261. MR 566592
Gene H. Golub and Charles F. Van Loan, Matrix computations, 3rd ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1996. MR 1417720
Gilles Pisier, The volume of convex bodies and Banach space geometry, Cambridge Tracts in Mathematics, vol. 94, Cambridge University Press, Cambridge, 1989. MR 1036275, DOI 10.1017/CBO9780511662454
Herbert Robbins, A remark on Stirling’s formula, Amer. Math. Monthly 62 (1955), 26–29. MR 69328, DOI 10.2307/2308012
Mark Rudelson and Roman Vershynin, The least singular value of a random square matrix is $O(n^{-1/2})$, C. R. Math. Acad. Sci. Paris 346 (2008), no. 15-16, 893–896 (English, with English and French summaries). MR 2441928, DOI 10.1016/j.crma.2008.07.009
Mark Rudelson and Roman Vershynin, The Littlewood-Offord problem and invertibility of random matrices, Adv. Math. 218 (2008), no. 2, 600–633. MR 2407948, DOI 10.1016/j.aim.2008.01.010
Mark Rudelson, Invertibility of random matrices: norm of the inverse, Ann. of Math. (2) 168 (2008), no. 2, 575–600. MR 2434885, DOI 10.4007/annals.2008.168.575
Mark Rudelson and Roman Vershynin, Non-asymptotic theory of random matrices: extreme singular values, Proceedings of the International Congress of Mathematicians. Volume III, Hindustan Book Agency, New Delhi, 2010, pp. 1576–1602. MR 2827856
Jack W. Silverstein, The smallest eigenvalue of a large-dimensional Wishart matrix, Ann. Probab. 13 (1985), no. 4, 1364–1368. MR 806232
Steve Smale, On the efficiency of algorithms of analysis, Bull. Amer. Math. Soc. (N.S.) 13 (1985), no. 2, 87–121. MR 799791, DOI 10.1090/S0273-0979-1985-15391-1
Alexander Soshnikov, A note on universality of the distribution of the largest eigenvalues in certain sample covariance matrices, J. Statist. Phys. 108 (2002), no. 5-6, 1033–1056. Dedicated to David Ruelle and Yasha Sinai on the occasion of their 65th birthdays. MR 1933444, DOI 10.1023/A:1019739414239
Daniel W. Stroock, Probability theory, 2nd ed., Cambridge University Press, Cambridge, 2011. An analytic view. MR 2760872
Stanisław J. Szarek, Condition numbers of random matrices, J. Complexity 7 (1991), no. 2, 131–149. MR 1108773, DOI 10.1016/0885-064X(91)90002-F
Terence Tao and Van Vu, On the singularity probability of random Bernoulli matrices, J. Amer. Math. Soc. 20 (2007), no. 3, 603–628. MR 2291914, DOI 10.1090/S0894-0347-07-00555-3
Terence Tao and Van Vu, Random matrices: the circular law, Commun. Contemp. Math. 10 (2008), no. 2, 261–307. MR 2409368, DOI 10.1142/S0219199708002788
Terence Tao and Van Vu, On the permanent of random Bernoulli matrices, Adv. Math. 220 (2009), no. 3, 657–669. MR 2483225, DOI 10.1016/j.aim.2008.09.006
Terence Tao and Van Vu, Random matrices: the distribution of the smallest singular values, Geom. Funct. Anal. 20 (2010), no. 1, 260–297. MR 2647142, DOI 10.1007/s00039-010-0057-8
Terence Tao and Van Vu, Smooth analysis of the condition number and the least singular value, Math. Comp. 79 (2010), no. 272, 2333–2352. MR 2684367, DOI 10.1090/S0025-5718-2010-02396-8
John von Neumann and H. H. Goldstine, Numerical inverting of matrices of high order, Bull. Amer. Math. Soc. 53 (1947), 1021–1099. MR 24235, DOI 10.1090/S0002-9904-1947-08909-6
Eugene P. Wigner, On the distribution of the roots of certain symmetric matrices, Ann. of Math. (2) 67 (1958), 325–327. MR 95527, DOI 10.2307/1970008
J. Wishart, The generalised product moment distribution in samples from a normal multivariate population, Biometrika 20 (1928), no. 1/2, 32–52.
Y. Q. Yin, Z. D. Bai, and P. R. Krishnaiah, On the limit of the largest eigenvalue of the large-dimensional sample covariance matrix, Probab. Theory Related Fields 78 (1988), no. 4, 509–521. MR 950344, DOI 10.1007/BF00353874