Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

Smooth analysis of the condition number and the least singular value


Authors: Terence Tao and Van Vu
Journal: Math. Comp. 79 (2010), 2333-2352
MSC (2010): Primary 11B25
DOI: https://doi.org/10.1090/S0025-5718-2010-02396-8
Published electronically: June 4, 2010
MathSciNet review: 2684367
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ x$ be a complex random variable with mean zero and bounded variance. Let $ N_{n}$ be the random matrix of size $ n$ whose entries are iid copies of $ x$ and let $ M$ be a fixed matrix of the same size. The goal of this paper is to give a general estimate for the condition number and least singular value of the matrix $ M + N_{n}$, generalizing an earlier result of Spielman and Teng for the case when $ x$ is gaussian.

Our investigation reveals an interesting fact that the ``core'' matrix $ M$ does play a role on tail bounds for the least singular value of $ M+N_{n} $. This does not occur in Spielman-Teng studies when $ \a$ is gaussian. Consequently, our general estimate involves the norm $ \Vert M\Vert$. In the special case when is relatively small, this estimate is nearly optimal and extends or refines existing results.


References [Enhancements On Off] (What's this?)

  • 1. Z. Bai and J. Silverstein, Spectral analysis of large dimensional random matrices, Second Edition, Springer, New York, 2010. MR 2567175
  • 2. D. Bau and L. N. Trefethen, Numerical linear algebra, SIAM (1997). MR 1444820 (98k:65002)
  • 3. P. Burgisser, F. Cucker, M. Lotz, The probability that a slightly perturbed numerical analysis problem is difficult, Math. Comp. 77 (2008), 1559-1583. MR 2398780 (2009a:65132)
  • 4. P. Bürgisser, F. Cucker, M. Lotz, General formulas for the smooth analysis of condition numbers, C. R. Acad. Sci. Paris, 343 (2006), 145-150. MR 2243310 (2007b:65147)
  • 5. P. Bürgisser, F. Cucker, M. Lotz, Smooth analysis of conic condition numbers, J. Math. Pure Appl. 86 (2006), 293-309. MR 2257845 (2007h:65040)
  • 6. A. Edelman, Eigenvalues and condition numbers of random matrices. SIAM J. Matrix Anal. Appl. 9 (1988), no. 4, 543-560. MR 964668 (89j:15039)
  • 7. P. Erdös, On a lemma of Littlewood and Offord, Bull. Amer. Math. Soc. 51 (1945), 898-902. MR 0014608 (7:309j)
  • 8. J. Demmel, The probability that a numerical analysis problem is difficult, Math. Comp. 50 (1988), 449-480. MR 929546 (89g:65062)
  • 9. J. Dunagan, D. A. Spielman and S. H. Teng, Smoothed Analysis of the Renegar's Condition Number for Linear Programming, preprint.
  • 10. G. Golub and C. Van Loan, Matrix computations, Third edition, Johns Hopkins Press, 1996. MR 1417720 (97g:65006)
  • 11. Z. Füredi and J. Komlós, The eigenvalues of random symmetric matrices, Combinatorica 1 (1981), no. 3, 233-241. MR 637828 (83e:15010)
  • 12. E. Kostlan, Complexity theory of numerical linear algebra, J. Comp. Appl. Math. 22 (1988), no. 2-3, 219-230. MR 0956504 (89i:65048)
  • 13. J. Komlós, On the determinant of $ (0,1)$ matrices, Studia Sci. Math. Hungar. 2 (1967), 7-22. MR 0221962 (36:5014)
  • 14. R. Latala, Some estimates of norms of random matrices, Proc. Amer. Math. Soc. 133 (2005), 1273-1282. MR 2111932 (2005i:15041)
  • 15. A. Litvak, A. Pajor, M. Rudelson and N. Tomczak-Jaegermann, Smallest singular value of random matrices and geometry of random polytopes, Adv. Math. 195 (2005), no. 2, 491-523. MR 2146352 (2006g:52009)
  • 16. M.L. Mehta, Random Matrices and the Statistical Theory of Energy Levels, Academic Press, New York, NY, 1967. MR 0220494 (36:3554)
  • 17. L.A. Pastur, The spectrum of random matrices, Teoret. Mat. Fiz. 10 (1973), 102-112. MR 0475502 (57:15106)
  • 18. J. Renegar, On the efficiency of Newton's method in approximating all zeros of a system of complex polynomials, Math. Oper. Res. 12 (1987), no. 1, 121-148. MR 882846 (88j:65112)
  • 19. M. Rudelson, Invertibility of random matrices: Norm of the inverse. Annals of Mathematics 168 (2008), no. 2, 575-600. MR 2434885
  • 20. M. Rudelson and R. Vershynin, The Littlewood-Offord problem and the condition number of random matrices, Advances in Mathematics 218 (2008), no. 2, 600-633. MR 2407948
  • 21. S. Smale, On the efficiency of algorithms of analysis, Bull. Amer. Math. Soc. 13 (1985), 87-121. MR 799791 (86m:65061)
  • 22. Y. Seginer, The expected norm of random matrices, Combin. Probab. Comput. 9 (2000), no. 2, 149-166. MR 1762786 (2001a:62070)
  • 23. D. A. Spielman and S. H. Teng, Smoothed analysis of algorithms, Proceedings of the International Congress of Mathematicians, Vol. I (Beijing, 2002), 597-606, Higher Ed. Press, Beijing, 2002. MR 1989210 (2004d:90138)
  • 24. D. A. Spielman and S. H. Teng, Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time, J. ACM 51 (2004), no. 3, 385-463. MR 2145860 (2006f:90029)
  • 25. A. Sankar, S. H. Teng, and D. A. Spielman, Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices, SIAM J. Matrix Anal. Appl. 28 (2006), no. 2, 446-476. MR 2255338 (2008b:65060)
  • 26. T. Tao and V. Vu, Inverse Littlewood-Offord theorems and the condition number of random discrete matrices, Annals of Mathematics, 169 (2009), no. 2, 595-632. MR 2480613
  • 27. T. Tao and V. Vu, The condition number of a randomly perturbed matrix, STOC'07, ACM, 248-255, 2007. MR 2402448 (2010a:65069)
  • 28. T. Tao and V. Vu, Random matrices: The circular law, Communications in Contemporary Mathematics, 10 (2008), 261-307. MR 2409368 (2009d:60091)
  • 29. T. Tao and V. Vu, Additive Combinatorics, Cambridge Univ. Press, 2006. MR 2289012 (2008a:11002)
  • 30. J. von Neumann and H. Goldstein, Numerical inverting matrices of high order, Bull. Amer. Math. Soc. 53 (1947) 1021-1099. MR 0024235 (9:471b)
  • 31. V. Vu, Spectral norm of random matrices, Combinatorica 27 (2007), no. 6, 721-736. MR 2384414 (2009d:15060)
  • 32. P. Wigner, On the distribution of the roots of certain symmetric matrices, Annals of Math. 67 (1958), 325-327. MR 0095527 (20:2029)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11B25

Retrieve articles in all journals with MSC (2010): 11B25


Additional Information

Terence Tao
Affiliation: Department of Mathematics, UCLA, Los Angeles, California 90095-1555
Email: tao@math.ucla.edu

Van Vu
Affiliation: Department of Mathematics, Rutgers University, Piscataway, New Jersey 08854
Email: vanvu@math.rutgers.edu

DOI: https://doi.org/10.1090/S0025-5718-2010-02396-8
Received by editor(s): March 10, 2009
Published electronically: June 4, 2010
Additional Notes: The first author was supported by a grant from the MacArthur Foundation.
The second author was supported by research grants DMS-0901216 and AFOSAR-FA-9550-09-1-0167.
Article copyright: © Copyright 2010 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society