Random perturbation of low rank matrices: Improving classical bounds

Abstract

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.

28 pages, 1 figure. Updated introduction and references. Final version. Wrong replacement in [v6]

References in corpus (2)

• Sparse Principal Components Analysis
• Finding Hidden Cliques of Size \sqrt{N/e} in Nearly Linear Time

Cited by in corpus (7)

• Unperturbed: spectral analysis beyond Davis-Kahan
• Laplacian Eigenmaps from Sparse, Noisy Similarity Measurements
• Controllability of random systems: Universality and minimal controllability
• Asymmetry Helps: Eigenvalue and Eigenvector Analyses of Asymmetrically Perturbed Low-Rank Matrices
• Eigenvectors of random matrices: A survey
• The eigenvalues of stochastic blockmodel graphs
• Perturbation of linear forms of singular vectors under Gaussian noise