Asymmetry Helps: Eigenvalue and Eigenvector Analyses of Asymmetrically Perturbed Low-Rank Matrices

Abstract

This paper is concerned with the interplay between statistical asymmetry and spectral methods. Suppose we are interested in estimating a rank-1 and symmetric matrix ${\mathbf{M}}^{\star }\in {\mathbb{R}}^{n\times n}$, yet only a randomly perturbed version $\mathbf{M}$ is observed. The noise matrix $\mathbf{M}-{\mathbf{M}}^{\star }$ is composed of zero-mean independent (but not necessarily homoscedastic) entries and is, therefore, not symmetric in general. This might arise, for example, when we have two independent samples for each entry of ${\mathbf{M}}^{\star }$ and arrange them into an {\em asymmetric} data matrix $\mathbf{M}$. The aim is to estimate the leading eigenvalue and eigenvector of ${\mathbf{M}}^{\star }$. We demonstrate that the leading eigenvalue of the data matrix $\mathbf{M}$ can be $O(\sqrt{n})$ times more accurate --- up to some log factor --- than its (unadjusted) leading singular value in eigenvalue estimation. Further, the perturbation of any linear form of the leading eigenvector of $\mathbf{M}$ --- say, entrywise eigenvector perturbation --- is provably well-controlled. This eigen-decomposition approach is fully adaptive to heteroscedasticity of noise without the need of careful bias correction or any prior knowledge about the noise variance. We also provide partial theory for the more general rank-$r$ case. The takeaway message is this: arranging the data samples in an asymmetric manner and performing eigen-decomposition could sometimes be beneficial.

accepted to Annals of Statistics, 2020. 37 pages

References in corpus (6)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization
• Limiting Laws for Divergent Spiked Eigenvalues and Largest Non-spiked Eigenvalue of Sample Covariance Matrices
• Singular vector and singular subspace distribution for the matrix denoising model
• Outlier eigenvalue fluctuations of perturbed iid matrices

Cited by in corpus (8)

• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• Inference and Uncertainty Quantification for Noisy Matrix Completion
• A Sharp Blockwise Tensor Perturbation Bound for Orthogonal Iteration
• Power Iteration for Tensor PCA
• Subspace Estimation from Unbalanced and Incomplete Data Matrices: ${\ell }_{2,\infty }$ Statistical Guarantees
• A Schatten-$q$ Low-rank Matrix Perturbation Analysis via Perturbation Projection Error Bound
• A simpler spectral approach for clustering in directed networks
• An exact $\sin \Theta$ formula for matrix perturbation analysis and its applications