Random perturbation and matrix sparsification and completion

We discuss general perturbation inequalities when the perturbation is random. As applications, we obtain several new results concerning two important problems: matrix sparsification and matrix completion.