Smooth analysis of the condition number and the least singular value

Abstract

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 $\Vert M\Vert$. In the special case when $\Vert M\Vert$ is relatively small, this estimate is nearly optimal and extends or refines existing results.

20 pages. An erratum to the published version has been added

References in corpus (1)

• The probability that a small perturbation of a numerical analysis problem is difficult