Smooth analysis of the condition number and the least singular value

Tao, Terence; Vu, Van

doi:10.1090/S0025-5718-2010-02396-8

Smooth analysis of the condition number and the least singular value
HTML articles powered by AMS MathViewer

by Terence Tao and Van Vu PDF

Math. Comp. 79 (2010), 2333-2352 Request permission

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 ${x}$ is gaussian. Consequently, our general estimate involves the norm $\|M\|$. In the special case when $\|M\|$ is relatively small, this estimate is nearly optimal and extends or refines existing results.

References

Zhidong Bai and Jack W. Silverstein, Spectral analysis of large dimensional random matrices, 2nd ed., Springer Series in Statistics, Springer, New York, 2010. MR 2567175, DOI 10.1007/978-1-4419-0661-8
Lloyd N. Trefethen and David Bau III, Numerical linear algebra, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. MR 1444820, DOI 10.1137/1.9780898719574
Peter Bürgisser, Felipe Cucker, and Martin Lotz, The probability that a slightly perturbed numerical analysis problem is difficult, Math. Comp. 77 (2008), no. 263, 1559–1583. MR 2398780, DOI 10.1090/S0025-5718-08-02060-7
Peter Bürgisser, Felipe Cucker, and Martin Lotz, General formulas for the smoothed analysis of condition numbers, C. R. Math. Acad. Sci. Paris 343 (2006), no. 2, 145–150 (English, with English and French summaries). MR 2243310, DOI 10.1016/j.crma.2006.05.014
Peter Bürgisser, Felipe Cucker, and Martin Lotz, Smoothed analysis of complex conic condition numbers, J. Math. Pures Appl. (9) 86 (2006), no. 4, 293–309 (English, with English and French summaries). MR 2257845, DOI 10.1016/j.matpur.2006.06.001
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
P. Erdös, On a lemma of Littlewood and Offord, Bull. Amer. Math. Soc. 51 (1945), 898–902. MR 14608, DOI 10.1090/S0002-9904-1945-08454-7
James W. Demmel, The probability that a numerical analysis problem is difficult, Math. Comp. 50 (1988), no. 182, 449–480. MR 929546, DOI 10.1090/S0025-5718-1988-0929546-7
J. Dunagan, D. A. Spielman and S. H. Teng, Smoothed Analysis of the Renegar’s Condition Number for Linear Programming, preprint.
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
Z. Füredi and J. Komlós, The eigenvalues of random symmetric matrices, Combinatorica 1 (1981), no. 3, 233–241. MR 637828, DOI 10.1007/BF02579329
Eric Kostlan, Complexity theory of numerical linear algebra, J. Comput. Appl. Math. 22 (1988), no. 2-3, 219–230. Special issue on emerging paradigms in applied mathematical modelling. MR 956504, DOI 10.1016/0377-0427(88)90402-5
J. Komlós, On the determinant of $(0,\,1)$ matrices, Studia Sci. Math. Hungar. 2 (1967), 7–21. MR 221962
RafałLatała, Some estimates of norms of random matrices, Proc. Amer. Math. Soc. 133 (2005), no. 5, 1273–1282. MR 2111932, DOI 10.1090/S0002-9939-04-07800-1
A. E. 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, DOI 10.1016/j.aim.2004.08.004
M. L. Mehta, Random matrices and the statistical theory of energy levels, Academic Press, New York-London, 1967. MR 0220494
L. A. Pastur, The spectrum of random matrices, Teoret. Mat. Fiz. 10 (1972), no. 1, 102–112 (Russian, with English summary). MR 475502
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, DOI 10.1287/moor.12.1.121
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, 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
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
Yoav Seginer, The expected norm of random matrices, Combin. Probab. Comput. 9 (2000), no. 2, 149–166. MR 1762786, DOI 10.1017/S096354830000420X
Daniel A. Spielman and Shang-Hua Teng, Smoothed analysis of algorithms, Proceedings of the International Congress of Mathematicians, Vol. I (Beijing, 2002) Higher Ed. Press, Beijing, 2002, pp. 597–606. MR 1989210
Daniel A. Spielman and Shang-Hua Teng, Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time, J. ACM 51 (2004), no. 3, 385–463. MR 2145860, DOI 10.1145/990308.990310
Arvind Sankar, Daniel A. Spielman, and Shang-Hua Teng, Smoothed analysis of the condition numbers and growth factors of matrices, SIAM J. Matrix Anal. Appl. 28 (2006), no. 2, 446–476. MR 2255338, DOI 10.1137/S0895479803436202
Terence Tao and Van H. Vu, Inverse Littlewood-Offord theorems and the condition number of random discrete matrices, Ann. of Math. (2) 169 (2009), no. 2, 595–632. MR 2480613, DOI 10.4007/annals.2009.169.595
Terence Tao and Van Vu, The condition number of a randomly perturbed matrix, STOC’07—Proceedings of the 39th Annual ACM Symposium on Theory of Computing, ACM, New York, 2007, pp. 248–255. MR 2402448, DOI 10.1145/1250790.1250828
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, Additive combinatorics, Cambridge Studies in Advanced Mathematics, vol. 105, Cambridge University Press, Cambridge, 2006. MR 2289012, DOI 10.1017/CBO9780511755149
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
Van H. Vu, Spectral norm of random matrices, Combinatorica 27 (2007), no. 6, 721–736. MR 2384414, DOI 10.1007/s00493-007-2190-z
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