An _ eigenvector perturbation bound and its application

MaRDI QIDQ4558538zbMATH OpenFDO

Authors Yiqiao Zhong, Jianqing Fan, Weichen Wang

Publication date 22 November 2018

Full work available at URL https://arxiv.org/abs/1603.03516, http://jmlr.csail.mit.edu/papers/v18/16-140.html

zbMATH Keywords

approximate factor modelincoherencelow-rank matricesmatrix perturbation theorysparsity

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(59)

• Rate-optimal perturbation bounds for singular subspaces with applications to high-dimensional statistics
• 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
• Bridging convex and nonconvex optimization in robust PCA: noise, outliers and missing data
• Relative perturbation bounds with applications to empirical covariance operators
• Non-asymptotic properties of spectral decomposition of large Gram-type matrices and applications
• Near-optimal performance bounds for orthogonal and permutation group synchronization via spectral methods
• Entrywise eigenvector analysis of random matrices with low expected rank
• Spectral method and regularized MLE are both optimal for top-\(K\) ranking
• The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics
• Singular vector and singular subspace distribution for the matrix denoising model
• Asymmetry helps: eigenvalue and eigenvector analyses of asymmetrically perturbed low-rank matrices
• Unperturbed: spectral analysis beyond Davis-Kahan
• scientific article; zbMATH DE number 7255037 (Why is no real title available?)
• scientific article; zbMATH DE number 7370530 (Why is no real title available?)
• Strong consistency, graph Laplacians, and the stochastic block model
• A performance guarantee for spectral clustering
• Robust covariance estimation with noisy high-frequency financial data
• Improved performance guarantees for orthogonal group synchronization via generalized power method
• Optimality of singular vector perturbation under maximum norm
• Solving jigsaw puzzles by the graph connection Laplacian
• Uniform Bounds for Invariant Subspace Perturbations
• A sharp blockwise tensor perturbation bound for orthogonal iteration
• Singular vector distribution of sample covariance matrices
• A useful variant of the Davis-Kahan theorem for statisticians
• The Sup-norm Perturbation of HOSVD and Low Rank Tensor Denoising
• Signal-plus-noise matrix models: eigenvector deviations and fluctuations
• Asymptotic Theory of Eigenvectors for Random Matrices With Diverging Spikes
• Learning Gaussian graphical models with latent confounders
• Perturbation upper bounds for singular subspaces with a kind of heteroskedastic noise and its application in clustering
• Adaptive robust large volatility matrix estimation based on high-frequency financial data
• Large volatility matrix analysis using global and national factor models
• Compressed spectral screening for large-scale differential correlation analysis with application in selecting glioblastoma gene modules
• A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization
• Euclidean Representation of Low-Rank Matrices and Its Geometric Properties
• Entrywise limit theorems for eigenvectors of signal-plus-noise matrix models with weak signals
• Polynomial-Time Algorithms for Continuous Metrics on Atomic Clouds of Unordered Points
• Learning low-dimensional nonlinear structures from high-dimensional noisy data: an integral operator approach
• Inference for heteroskedastic PCA with missing data
• Testing Simultaneous Diagonalizability
• 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
• Leave-one-out singular subspace perturbation analysis for spectral clustering
• Exact minimax optimality of spectral methods in phase synchronization and orthogonal group synchronization
• Identifying the Structure of High-Dimensional Time Series via Eigen-Analysis
• Curse of dimensionality on persistence diagrams
• On model identification and out-of-sample prediction of PCR with applications to synthetic controls
• Adaptive thresholding for iterative matrix completion with heterogeneous missing probability: H-AdaptiveImpute
• Factor-guided estimation of large covariance matrix function with conditional functional sparsity
• Local MALA-within-Gibbs for Bayesian image deblurring with total variation prior
• Uniform error bound for PCA matrix denoising
• Network-adjusted covariates for community detection
• Optimal spectral recovery of a planted vector in a subspace
• On \(r\)-to-\(p\) norms of random matrices with nonnegative entries: asymptotic normality and \(\ell_{\infty}\)-bounds for the maximizer
• Analysis of singular subspaces under random perturbations
• Title not available (Why is no real title available?)
• Title not available (Why is no real title available?)
• Eigenvector decorrelation for random matrices

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)