  Let $M$ be an arbitrary $n$ by $n$ matrix of rank $n-k$. We study the
condition number of $M$ plus a \emph{low-rank} perturbation $UV^T$ where $U, V$
are $n$ by $k$ random Gaussian matrices. Under some necessary assumptions, it
is shown that $M+UV^T$ is unlikely to have a large condition number. The main
advantages of this kind of perturbation over the well-studied dense Gaussian
perturbation, where every entry is independently perturbed, is the $O(nk)$ cost
to store $U,V$ and the $O(nk)$ increase in time complexity for performing the
matrix-vector multiplication $(M+UV^T)x$. This improves the $\Omega(n^2)$ space
and time complexity increase required by a dense perturbation, which is
especially burdensome if $M$ is originally sparse. Our results also extend to
the case where $U$ and $V$ have rank larger than $k$ and to symmetric and
complex settings. We also give an application to linear systems solving and
perform some numerical experiments. Lastly, barriers in applying low-rank noise
to other problems studied in the smoothed analysis framework are discussed.
