Random perturbation of low rank matrices: Improving classical bounds

2013/11/12 by Sean M. O’Rourke, Van Vu, O'Rourke, Sean +3 · 6 citations
Engineering · Mathematics · #Sparse and Compressive Sensing Techniques #Random Matrices and Applications #Tensor decomposition and applications

paper · pdf · doi:10.48550/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.

Citations

• The Rotation of Eigenvectors by a Perturbation. III
• Optimal Estimation and Rank Detection for Sparse Spiked Covariance Matrices
• Nuclear norm penalization and optimal rates for noisy low rank matrix\n completion

Cited by

• Estimating eigenvectors and eigenspaces of covariance matrices: Optimal Bounds and Conditions for Consistency
• New perturbation bounds for low rank approximation of matrices: Beyond Eckart-Young-Mirsky
• Spectral Perturbation Bounds for Low-Rank Approximation with Applications to Privacy
• Davis-Kahan Theorem under a moderate gap condition
• Perturbation of linear forms of singular vectors under Gaussian noise
• Controllability of random systems: Universality and minimal controllability

Related

• New matrix perturbation bounds via combinatorial expansion I: Perturbation of eigenspaces
• Singular vectors under random perturbation
• Rank 1 perturbations in random matrix theory -- a review of exact results
• Matrix Perturbation: Davis-Kahan in the Infinity Norm
• Rank of Near Uniform Matrices