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.
تحميل البحث