An _ eigenvector perturbation bound and its application

zbMATH Open1473.15015arXiv1603.03516MaRDI QIDQ4558538FDOQ4558538

Authors: Yiqiao Zhong, Jianqing Fan, Weichen Wang 

Publication date: 22 November 2018

Abstract: In statistics and machine learning, people are often interested in the eigenvectors (or singular vectors) of certain matrices (e.g. covariance matrices, data matrices, etc). However, those matrices are usually perturbed by noises or statistical errors, either from random sampling or structural patterns. One usually employs Davis-Kahan $sinheta$ theorem to bound the difference between the eigenvectors of a matrix $A$ and those of a perturbed matrix $widetildeA=A+E$, in terms of $el{l}_2$ norm. In this paper, we prove that when $A$ is a low-rank and incoherent matrix, the $el{l}_{infty}$ norm perturbation bound of singular vectors (or eigenvectors in the symmetric case) is smaller by a factor of $sqrt{d}_1$ or $sqrt{d}_2$ for left and right vectors, where $d_1$ and $d_2$ are the matrix dimensions. The power of this new perturbation result is shown in robust covariance estimation, particularly when random variables have heavy tails. There, we propose new robust covariance estimators and establish their asymptotic properties using the newly developed perturbation bound. Our theoretical results are verified through extensive numerical experiments.

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

Recommendations

• Optimality of singular vector perturbation under maximum norm
• Singular vectors under random perturbation
• Unperturbed: spectral analysis beyond Davis-Kahan
• Rate-optimal perturbation bounds for singular subspaces with applications to high-dimensional statistics
• Random perturbation of low rank matrices: improving classical bounds

zbMATH Keywords

matrix perturbation theorysparsityincoherencelow-rank matricesapproximate factor model

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Computational methods for sparse matrices (65F50) Eigenvalues, singular values, and eigenvectors (15A18) Perturbation theory of linear operators (47A55) Numerical methods for low-rank matrix approximation; matrix compression (65F55)

Cites Work

• Principal component analysis.
• Forecasting Using Principal Components From a Large Number of Predictors
• Inferential Theory for Factor Models of Large Dimensions
• Spectral clustering and the high-dimensional stochastic blockmodel
• Modern multidimensional scaling. Theory and applications.
• High dimensional covariance matrix estimation using a factor model
• Latent variable models and factor analysis. A unified approach
• Robust Estimation of a Location Parameter
• The Rotation of Eigenvectors by a Perturbation. III
• Covariance regularization by thresholding
• Robust principal component analysis?
• Arbitrage, Factor Structure, and Mean-Variance Analysis on Large Asset Markets
• Title not available (Why is that?)
• On consistency and sparsity for principal components analysis in high dimensions
• A useful variant of the Davis-Kahan theorem for statisticians
• Dimension Reduction and Coefficient Estimation in Multivariate Linear Regression
• Challenging the empirical mean and empirical variance: a deviation study
• Sparse principal component analysis and iterative thresholding
• Title not available (Why is that?)
• Regularization of Wavelet Approximations
• Common risk factors in the returns on stocks and bonds
• Rate-optimal perturbation bounds for singular subspaces with applications to high-dimensional statistics
• Rank-Sparsity Incoherence for Matrix Decomposition
• Optimal detection of sparse principal components in high dimension
• Generalized thresholding of large covariance matrices
• Estimation of High Dimensional Mean Regression in the Absence of Symmetry and Light Tail Assumptions
• Perturbation bounds in connection with singular value decomposition
• User-friendly tail bounds for sums of random matrices
• Asymptotics of empirical eigenstructure for high dimensional spiked covariance
• Title not available (Why is that?)
• A framework for robust subspace learning
• Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices
• Elliptically contoured models in statistics and portfolio theory
• A multivariate version of kendall's τ
• Scale-invariant sparse PCA on high-dimensional meta-elliptical data
• Minimax sparse principal subspace estimation in high dimensions
• Incoherence-Optimal Matrix Completion
• SYMMETRIC GAUGE FUNCTIONS AND UNITARILY INVARIANT NORMS
• A distributed method for solving semidefinite programs arising from ad hoc wireless sensor network localization
• Singular vectors under random perturbation
• Random perturbation of low rank matrices: improving classical bounds

Cited In (45)

• Compressed spectral screening for large-scale differential correlation analysis with application in selecting glioblastoma gene modules
• A useful variant of the Davis-Kahan theorem for statisticians
• Testing Simultaneous Diagonalizability
• Adaptive robust large volatility matrix estimation based on high-frequency financial data
• Relative perturbation bounds with applications to empirical covariance operators
• The Sup-norm Perturbation of HOSVD and Low Rank Tensor Denoising
• Rate-optimal perturbation bounds for singular subspaces with applications to high-dimensional statistics
• Optimality of singular vector perturbation under maximum norm
• Title not available (Why is that?)
• Entrywise eigenvector analysis of random matrices with low expected rank
• A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization
• High-dimensional volatility matrix estimation with cross-sectional dependent and heavy-tailed microstructural noise
• Strong consistency guarantees for clustering high-dimensional bipartite graphs with the spectral method
• Non-asymptotic properties of spectral decomposition of large Gram-type matrices and applications
• The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics
• Title not available (Why is that?)
• Uniform Bounds for Invariant Subspace Perturbations
• Entrywise limit theorems for eigenvectors of signal-plus-noise matrix models with weak signals
• Robust covariance estimation with noisy high-frequency financial data
• Unperturbed: spectral analysis beyond Davis-Kahan
• A performance guarantee for spectral clustering
• Improved performance guarantees for orthogonal group synchronization via generalized power method
• Strong consistency, graph Laplacians, and the stochastic block model
• Polynomial-Time Algorithms for Continuous Metrics on Atomic Clouds of Unordered Points
• Robust high-dimensional factor models with applications to statistical machine learning
• Learning low-dimensional nonlinear structures from high-dimensional noisy data: an integral operator approach
• Near-optimal performance bounds for orthogonal and permutation group synchronization via spectral methods
• 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
• Title not available (Why is that?)
• Spectral method and regularized MLE are both optimal for top-\(K\) ranking
• Perturbation upper bounds for singular subspaces with a kind of heteroskedastic noise and its application in clustering
• Bridging convex and nonconvex optimization in robust PCA: noise, outliers and missing data
• Asymmetry helps: eigenvalue and eigenvector analyses of asymmetrically perturbed low-rank matrices
• Signal-plus-noise matrix models: eigenvector deviations and fluctuations
• Singular vector distribution of sample covariance matrices
• Euclidean Representation of Low-Rank Matrices and Its Geometric Properties
• Exact minimax optimality of spectral methods in phase synchronization and orthogonal group synchronization
• Leave-one-out singular subspace perturbation analysis for spectral clustering
• Large volatility matrix analysis using global and national factor models
• Learning Gaussian graphical models with latent confounders
• Singular vector and singular subspace distribution for the matrix denoising model
• Inference for heteroskedastic PCA with missing data
• Asymptotic Theory of Eigenvectors for Random Matrices With Diverging Spikes
• Solving jigsaw puzzles by the graph connection Laplacian

This page was built for publication: An \(\ell_{\infty}\) eigenvector perturbation bound and its application

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4558538)