Advertisement
Published in:
2009 | OriginalPaper | Chapter
Smooth Analysis of the Condition Number and the Least Singular Value
Authors : Terence Tao, Van Vu
Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
A few years ago, Spielman and Teng initiated the study of Smooth analysis of the condition number and the least singular value of a matrix. Let
x
be a complex variable with mean zero and bounded variance. Let
N
n
be the random matrix of sie
n
whose entries are iid copies of
x
and
M
a deterministic matrix of the same size. The goal of smooth analysis is to estimate the condition number and the least singular value of
M
+
N
n
.
Spielman and Teng considered the case when
x
is gaussian. We are going to study the general case when
x
is arbitrary. Our investigation reveals a new and interesting fact that, unlike the gaussian case, in the general case the “core“ matrix
M
does play a role in the tail bounds for the least singular value of
M
+
N
n
. Consequently, our estimate involves the norm ∥
M
∥ and it is a challenging question to determine the right magnitude of this involvement. When ∥
M
∥ is relatively small, our estimate is nearly optimal and extends or refines several existing result.