Random perturbation of low rank matrices: Improving classical bounds
arXiv:1311.2657
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.
arXiv comment28 pages, 1 figure. Updated introduction and references. Final version. Wrong replacement in [v6]
References in corpus (7)
- Matrix estimation by Universal Singular Value Thresholding
- Sparse Principal Components Analysis
- The outliers of a deformed Wigner matrix
- Finding Hidden Cliques of Size \sqrt{N/e} in Nearly Linear Time
- Eigenvector dynamics under free addition
- Random weighted projections, random quadratic forms and random eigenvectors
- Optimal Estimation and Rank Detection for Sparse Spiked Covariance Matrices
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