The condition number of a randomly perturbed matrix

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The condition number of a randomly perturbed matrix

Full text

Pdf (245 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-ninth annual ACM symposium on Theory of computing table of contents

San Diego, California, USA

SESSION: Session 6A table of contents

Pages: 248 - 255

Year of Publication: 2007

ISBN:978-1-59593-631-8

Authors

Van H. Vu	Rutgers, Piscataway, NJ
Terence Tao	UCLA, Los Angeles, CA

Sponsors

ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 13, Downloads (12 Months): 87, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1250790.1250828 What is a DOI?

ABSTRACT

Let M be an arbitrary n by n matrix. We study the conditionnumber a random perturbation M+N_n of M, where N_n is arandom matrix. It is shown that, under very general conditions on M and M_n, the condition number of M+N_n is polynomial in nwith very high probability. The main novelty here is that we allow N_n to have discrete distribution.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	D. Bau and L. Trefethen, Numerical linear algebra. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997.
	2	B. Bollobás, Random graphs. Second edition, Cambridge Studies in Advanced Mathematics, 73. Cambridge University Press, Cambridge, 2001.
	3	Alan Edelman, Eigenvalues and condition numbers of random matrices, SIAM Journal on Matrix Analysis and Applications, v.9 n.4, p.543-560, Oct. 1988 [doi>10.1137/0609045]
	4	Alan Edelman , Brian D. Sutton, Tails of Condition Number Distributions, SIAM Journal on Matrix Analysis and Applications, v.27 n.2, p.547-560, 2005 [doi>10.1137/040614256]
	5	J. Kahn, J. Komlós, E. Szemerédi, On the probability that a random pm 1 matrix is singular, J. Amer. Math. Soc. 8 (1995), 223--240.
	6	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.
	7	M. Rudelson, Invertibility of random matrices: Norm of the inverse. submitted.
	8	A. Sankar, S. H. Teng, and D. A. Spielman, Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices, preprint.
	9	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.
	10	Daniel A. Spielman , Shang-Hua Teng, Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time, Journal of the ACM (JACM), v.51 n.3, p.385-463, May 2004 [doi>10.1145/990308.990310]
	11	Terence Tao , Van Vu, On random ±1 matrices: Singularity and determinant, Random Structures & Algorithms, v.28 n.1, p.1-23, January 2006 [doi>10.1002/rsa.v28:1]
	12	T. Tao and V. Vu, Inverse Littlewood-Offord theorems and the condition number of random discrete matrices, Annals of Mathematics, to appear.