Mathematics – Probability
Scientific paper
2008-05-20
Mathematics
Probability
20 pages, no figures, to appear, Mathematics of Computation
Scientific paper
Let $\a$ 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 $\a$ and $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 $\a$ 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 $\|M\|$. In the special case when $\|M\|$ is relatively small, this estimate is nearly optimal and extends or refines existing results.
Tao Terence
Vu Van
No associations
LandOfFree
Smooth analysis of the condition number and the least singular value does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Smooth analysis of the condition number and the least singular value, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Smooth analysis of the condition number and the least singular value will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-289619