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
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?)

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

Van Vu
Affiliation: Department of Mathematics, Rutgers University, Piscataway, New Jersey 08854

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.