Random perturbation of low rank matrices: improving classical bounds

DOI10.1016/j.laa.2017.11.014zbMath1380.65076arXiv1311.2657OpenAlexW2962740067MaRDI QIDQ1688904

Sean O'Rourke, Ke Wang, Van H. Vu

Publication date: 12 January 2018

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1311.2657

zbMATH Keywords

singular value decompositionrandom perturbationWeyl's theoremrandom matrixsingular valuessingular vectorsDavis-Kahan theorem

Mathematics Subject Classification ID

Numerical solutions to overdetermined systems, pseudoinverses (65F20) Random matrices (algebraic aspects) (15B52)

Related Items

Eigenvalues of stochastic blockmodel graphs and random graphs with low-rank edge probability matrices, Near-optimal performance bounds for orthogonal and permutation group synchronization via spectral methods, Lower bounds for invariant statistical models with applications to principal component analysis, Singular vector and singular subspace distribution for the matrix denoising model, Asymmetry helps: eigenvalue and eigenvector analyses of asymmetrically perturbed low-rank matrices, Robust Recovery of Low-Rank Matrices and Low-Tubal-Rank Tensors from Noisy Sketches, Perturbation upper bounds for singular subspaces with a kind of heteroskedastic noise and its application in clustering, Newton-MR: inexact Newton method with minimum residual sub-problem solver, Bias-Adjusted Spectral Clustering in Multi-Layer Stochastic Block Models, Entrywise eigenvector analysis of random matrices with low expected rank, Euclidean Representation of Low-Rank Matrices and Its Geometric Properties, Near-optimal bounds for generalized orthogonal Procrustes problem via generalized power method, On the smoothed analysis of the smallest singular value with discrete noise, Time Series Source Separation Using Dynamic Mode Decomposition, A note on exploratory item factor analysis by singular value decomposition, Convergence of Newton-MR under Inexact Hessian Information, Rate-optimal perturbation bounds for singular subspaces with applications to high-dimensional statistics, An $\ell_{\infty}$ Eigenvector Perturbation Bound and Its Application to Robust Covariance Estimation, Robust high-dimensional factor models with applications to statistical machine learning, Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees, On the \(\ell^\infty\)-norms of the singular vectors of arbitrary powers of a difference matrix with applications to sigma-delta quantization, Perturbation bounds for eigenspaces under a relative gap condition, Eigenvectors of a matrix under random perturbation, Spectral Methods for Passive Imaging: Nonasymptotic Performance and Robustness, The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics, An \({\ell_p}\) theory of PCA and spectral clustering, Unnamed Item, Relative perturbation bounds with applications to empirical covariance operators

Uses Software

• mctoolbox
• softImpute

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Von Neumann entropy penalization and low-rank matrix estimation
• The outliers of a deformed Wigner matrix
• The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices
• Probability in Banach spaces. Isoperimetry and processes
• Estimation of (near) low-rank matrices with noise and high-dimensional scaling
• Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion
• Finite sample approximation results for principal component analysis: A matrix perturbation approach
• Rate-optimal perturbation bounds for singular subspaces with applications to high-dimensional statistics
• A new look at independence
• Matrix estimation by universal singular value thresholding
• Optimal estimation and rank detection for sparse spiked covariance matrices
• Spectra of nearly Hermitian random matrices
• Weighted sums of certain dependent random variables
• Exact matrix completion via convex optimization
• A Singular Value Thresholding Algorithm for Matrix Completion
• SYMMETRIC GAUGE FUNCTIONS AND UNITARILY INVARIANT NORMS
• On random ±1 matrices: Singularity and determinant
• Random weighted projections, random quadratic forms and random eigenvectors
• Sampling from large matrices
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• A Spectral Technique for Coloring Random 3-Colorable Graphs
• ON FINITE RANK DEFORMATIONS OF WIGNER MATRICES II: DELOCALIZED PERTURBATIONS
• Fast computation of low rank matrix approximations
• Spectral analysis of data
• Finding Hidden Cliques in Linear Time with High Probability
• Singular Vector Perturbation Under Gaussian Noise
• Matrix Completion From a Few Entries
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• Probability Inequalities for Sums of Bounded Random Variables
• Singular vectors under random perturbation
• Some Kolmogoroff-type inequalities for bounded random variables
• The Rotation of Eigenvectors by a Perturbation. III
• Perturbation bounds in connection with singular value decomposition
• Spectral norm of random matrices