  Matrix perturbation inequalities, such as Weyl's theorem (concerning the
singular values) and the Davis-Kahan theorem (concerning the singular vectors),
play essential roles in quantitative science; in particular, these bounds have
found application in data analysis as well as related areas of engineering and
computer science. In many situations, the perturbation is assumed to be random,
and the original matrix has certain structural properties (such as having low
rank). We show that, in this scenario, classical perturbation results, such as
Weyl and Davis-Kahan, can be improved significantly. We believe many of our new
bounds are close to optimal and also discuss some applications.
