Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

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


Authors: Ming-Jun Lai and Yang Liu
Journal: Math. Comp. 84 (2015), 1775-1794
MSC (2010): Primary 60B20; Secondary 60F10, 60G50, 60G42
DOI: https://doi.org/10.1090/S0025-5718-2014-02895-0
Published electronically: October 30, 2014
MathSciNet review: 3335891
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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 (89i:62083), https://doi.org/10.1016/0047-259X(88)90078-4
  • [2] G. Bennett, V. Goodman, and C. M. Newman, Norms of random matrices, Pacific J. Math. 59 (1975), no. 2, 359-365. MR 0393085 (52 #13896)
  • [3] 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 (2001g:60089)
  • [4] Rick Chartrand and Valentina Staneva, Restricted isometry properties and nonconvex compressive sensing, Inverse Problems 24 (2008), no. 3, 035020, 14. MR 2421974 (2009d:94027), https://doi.org/10.1088/0266-5611/24/3/035020
  • [5] Alan Edelman, Eigenvalues and condition numbers of random matrices, SIAM J. Matrix Anal. Appl. 9 (1988), no. 4, 543-560. MR 964668 (89j:15039), https://doi.org/10.1137/0609045
  • [6] Alan Edelman, Eigenvalues and condition numbers of random matrices, Ph.D. thesis, Massachusetts Institute of Technology, 1989. PRoQuest LLC.MR 2941174
  • [7] A. Fisher, The Mathematical Theory of Probabilities and its Application to Frequency Curves and Statistical Methods, vol. 1, The Macmillan Company, 1922.
  • [8] 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 (2011b:65045), https://doi.org/10.1016/j.acha.2008.09.001
  • [9] Simon Foucart and Ming-Jun Lai, Sparse recovery with pre-Gaussian random matrices, Studia Math. 200 (2010), no. 1, 91-102. MR 2720209 (2011g:15061), https://doi.org/10.4064/sm200-1-6
  • [10] Stuart Geman, A limit theorem for the norm of random matrices, Ann. Probab. 8 (1980), no. 2, 252-261. MR 566592 (81m:60046)
  • [11] 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 (97g:65006)
  • [12] Gilles Pisier, The Volume of Convex Bodies and Banach Space Geometry, Cambridge Tracts in Mathematics, vol. 94, Cambridge University Press, Cambridge, 1989. MR 1036275 (91d:52005)
  • [13] Herbert Robbins, A remark on Stirling's formula, Amer. Math. Monthly 62 (1955), 26-29. MR 0069328 (16,1020e)
  • [14] 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 (2009i:60104), https://doi.org/10.1016/j.crma.2008.07.009
  • [15] Mark Rudelson and Roman Vershynin, The Littlewood-Offord problem and invertibility of random matrices, Adv. Math. 218 (2008), no. 2, 600-633. MR 2407948 (2010g:60048), https://doi.org/10.1016/j.aim.2008.01.010
  • [16] Mark Rudelson, Invertibility of random matrices: norm of the inverse, Ann. of Math. (2) 168 (2008), no. 2, 575-600. MR 2434885 (2010f:46021), https://doi.org/10.4007/annals.2008.168.575
  • [17] 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 (2012g:60016)
  • [18] Jack W. Silverstein, The smallest eigenvalue of a large-dimensional Wishart matrix, Ann. Probab. 13 (1985), no. 4, 1364-1368. MR 806232 (87b:60050)
  • [19] Steve Smale, On the efficiency of algorithms of analysis, Bull. Amer. Math. Soc. (N.S.) 13 (1985), no. 2, 87-121. MR 799791 (86m:65061), https://doi.org/10.1090/S0273-0979-1985-15391-1
  • [20] 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 (2003h:62108), https://doi.org/10.1023/A:1019739414239
  • [21] Daniel W. Stroock, Probability Theory, 2nd ed., Cambridge University Press, Cambridge, 2011. An analytic view. MR 2760872 (2012a:60003)
  • [22] Stanisław J. Szarek, Condition numbers of random matrices, J. Complexity 7 (1991), no. 2, 131-149. MR 1108773 (92i:65086), https://doi.org/10.1016/0885-064X(91)90002-F
  • [23] 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 (2008h:60027), https://doi.org/10.1090/S0894-0347-07-00555-3
  • [24] Terence Tao and Van Vu, Random matrices: the circular law, Commun. Contemp. Math. 10 (2008), no. 2, 261-307. MR 2409368 (2009d:60091), https://doi.org/10.1142/S0219199708002788
  • [25] Terence Tao and Van Vu, On the permanent of random Bernoulli matrices, Adv. Math. 220 (2009), no. 3, 657-669. MR 2483225 (2010b:15014), https://doi.org/10.1016/j.aim.2008.09.006
  • [26] 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 (2011m:60020), https://doi.org/10.1007/s00039-010-0057-8
  • [27] 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 (2011k:65065), https://doi.org/10.1090/S0025-5718-2010-02396-8
  • [28] John von Neumann and H. H. Goldstine, Numerical inverting of matrices of high order, Bull. Amer. Math. Soc. 53 (1947), 1021-1099. MR 0024235 (9,471b)
  • [29] Eugene P. Wigner, On the distribution of the roots of certain symmetric matrices, Ann. of Math. (2) 67 (1958), 325-327. MR 0095527 (20 #2029)
  • [30] J. Wishart, The generalised product moment distribution in samples from a normal multivariate population, Biometrika 20 (1928), no. 1/2, 32-52.
  • [31] 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 (89g:60117), https://doi.org/10.1007/BF00353874

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 60B20, 60F10, 60G50, 60G42

Retrieve articles in all journals with MSC (2010): 60B20, 60F10, 60G50, 60G42


Additional Information

Ming-Jun Lai
Affiliation: Department of Mathematics, The University of Georgia, Athens, Georgia 30602
Email: mjlai@math.uga.edu

Yang Liu
Affiliation: Department of Mathematics, Michigan State University, East Lansing, Michigan 488244-1027
Email: yliu@math.msu.edu

DOI: https://doi.org/10.1090/S0025-5718-2014-02895-0
Keywords: Random matrices, probability, pre-Gaussian random variable, generalized singular values
Received by editor(s): November 26, 2012
Received by editor(s) in revised form: September 23, 2013
Published electronically: October 30, 2014
Additional Notes: The first author was partly supported by the National Science Foundation under grant DMS-0713807
The second author was partially supported by the Air Force Office of Scientific Research under grant AFOSR 9550-12-1-0455
Article copyright: © Copyright 2014 American Mathematical Society

American Mathematical Society