Entrywise eigenvector analysis of random matrices with low expected rank
From MaRDI portal
Publication:2196228
Abstract: Recovering low-rank structures via eigenvector perturbation analysis is a common problem in statistical machine learning, such as in factor analysis, community detection, ranking, matrix completion, among others. While a large variety of bounds are available for average errors between empirical and population statistics of eigenvectors, few results are tight for entrywise analyses, which are critical for a number of problems such as community detection. This paper investigates entrywise behaviors of eigenvectors for a large class of random matrices whose expectations are low-rank, which helps settle the conjecture in Abbe et al. (2014b) that the spectral algorithm achieves exact recovery in the stochastic block model without any trimming or cleaning steps. The key is a first-order approximation of eigenvectors under the norm: u_k approx frac{A u_k^*}{lambda_k^*}, where and are eigenvectors of a random matrix and its expectation , respectively. The fact that the approximation is both tight and linear in facilitates sharp comparisons between and . In particular, it allows for comparing the signs of and even if is large. The results are further extended to perturbations of eigenspaces, yielding new -type bounds for synchronization (-spiked Wigner model) and noisy matrix completion.
Recommendations
- An \(\ell_{\infty}\) eigenvector perturbation bound and its application
- Signal-plus-noise matrix models: eigenvector deviations and fluctuations
- Asymmetry helps: eigenvalue and eigenvector analyses of asymmetrically perturbed low-rank matrices
- Singular vectors under random perturbation
- Unperturbed: spectral analysis beyond Davis-Kahan
Cites work
- A Consistent Adjacency Spectral Embedding for Stochastic Blockmodel Graphs
- A proof of the block model threshold conjecture
- A Simple SVD Algorithm for Finding Hidden Partitions
- A spectral heuristic for bisecting random graphs
- Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions
- Achieving optimal misclassification proportion in stochastic block models
- An \(\ell_{\infty}\) eigenvector perturbation bound and its application
- Angular synchronization by eigenvectors and semidefinite programming
- Asymptotic mutual information for the balanced binary stochastic block model
- Asymptotics and concentration bounds for bilinear forms of spectral projectors of sample covariance
- Community detection and stochastic block models: recent developments
- Community detection in sparse networks via Grothendieck's inequality
- Community detection thresholds and the weak Ramanujan property
- Consistency of spectral clustering in stochastic block models
- Distributed 3-D Localization of Camera Sensor Networks From 2-D Image Measurements
- Exact matrix completion via convex optimization
- Exact Recovery in the Stochastic Block Model
- Fundamental limits of symmetric low-rank matrix estimation
- Guaranteed Matrix Completion via Non-Convex Factorization
- scientific article; zbMATH DE number 47363 (Why is no real title available?)
- Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution
- Low-rank matrix completion using alternating minimization
- Matrix Completion From a Few Entries
- Matrix completion from noisy entries
- Matrix estimation by universal singular value thresholding
- Minimax rates of community detection in stochastic block models
- Near-optimal bounds for phase synchronization
- Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs
- Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion
- On semidefinite relaxations for the block model
- One-Step Huber Estimates in the Linear Model
- Optimality and sub-optimality of PCA. I: Spiked random matrix models
- Perturbation bounds in connection with singular value decomposition
- Perturbation of linear forms of singular vectors under Gaussian noise
- Phase retrieval via Wirtinger flow: theory and algorithms
- Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices
- Phase transitions in semidefinite relaxations
- Proof of the achievability conjectures for the general stochastic block model
- Random Laplacian matrices and convex relaxations
- Random perturbation of low rank matrices: improving classical bounds
- Recovering Low-Rank Matrices From Few Coefficients in Any Basis
- Robust principal component analysis?
- Semidefinite programs on sparse random graphs and their application to community detection
- Spectral clustering and the high-dimensional stochastic blockmodel
- Spectral method and regularized MLE are both optimal for top-\(K\) ranking
- Spectral redemption in clustering sparse networks
- The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices
- The largest eigenvalue of rank one deformation of large Wigner matrices
- The Power of Convex Relaxation: Near-Optimal Matrix Completion
- The Rotation of Eigenvectors by a Perturbation. III
- The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics
- Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
- Unperturbed: spectral analysis beyond Davis-Kahan
- Viewing direction estimation in cryo-EM using synchronization
Cited in
(91)- Mixed Membership Estimation for Social Networks
- Using SVD for Topic Modeling
- Robust high-dimensional factor models with applications to statistical machine learning
- Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees
- Optimality of spectral clustering in the Gaussian mixture model
- Spectral clustering revisited: information hidden in the Fiedler vector
- Community detection on mixture multilayer networks via regularized tensor decomposition
- Non-convex exact community recovery in stochastic block model
- Sharp optimal recovery in the two component Gaussian mixture model
- Random graph asymptotics for treatment effect estimation under network interference
- An \({\ell_p}\) theory of PCA and spectral clustering
- Iterative algorithm for discrete structure recovery
- Asymptotically efficient estimators for stochastic blockmodels: the naive MLE, the rank-constrained MLE, and the spectral estimator
- Partial recovery for top-\(k\) ranking: optimality of MLE and suboptimality of the spectral method
- Near-optimal performance bounds for orthogonal and permutation group synchronization via spectral methods
- Eigenvector phase retrieval: recovering eigenvectors from the absolute value of their entries
- Model assisted variable clustering: minimax-optimal recovery and algorithms
- Rate optimal Chernoff bound and application to community detection in the stochastic block models
- Normal approximation and confidence region of singular subspaces
- Exact recovery in the hypergraph stochastic block model: a spectral algorithm
- 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
- Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval
- Asymmetry helps: eigenvalue and eigenvector analyses of asymmetrically perturbed low-rank matrices
- Analysis of spectral clustering algorithms for community detection: the general bipartite setting
- scientific article; zbMATH DE number 7370530 (Why is no real title available?)
- scientific article; zbMATH DE number 7370563 (Why is no real title available?)
- The interplay of demographic variables and social distancing scores in deep prediction of U.S. COVID-19 cases
- A performance guarantee for spectral clustering
- Spectral Methods for Data Science: A Statistical Perspective
- Eigenvalues of the non-backtracking operator detached from the bulk
- scientific article; zbMATH DE number 7626708 (Why is no real title available?)
- Randomized Spectral Clustering in Large-Scale Stochastic Block Models
- Iterative Collaborative Filtering for Sparse Matrix Estimation
- Spectral alignment of correlated Gaussian matrices
- Nonconvex Low-Rank Tensor Completion from Noisy Data
- Improved performance guarantees for orthogonal group synchronization via generalized power method
- Entrywise Estimation of Singular Vectors of Low-Rank Matrices With Heteroskedasticity and Dependence
- Noisy matrix completion: understanding statistical guarantees for convex relaxation via nonconvex optimization
- Uniform Bounds for Invariant Subspace Perturbations
- Nonparametric modeling of higher-order interactions via hypergraphons
- A sharp blockwise tensor perturbation bound for orthogonal iteration
- Singular vector distribution of sample covariance matrices
- Signal-plus-noise matrix models: eigenvector deviations and fluctuations
- Estimating Mixed Memberships With Sharp Eigenvector Deviations
- Hierarchical Community Detection by Recursive Partitioning
- Asymptotic Theory of Eigenvectors for Random Matrices With Diverging Spikes
- A distributed community detection algorithm for large scale networks under stochastic block models
- Eigen Selection in Spectral Clustering: A Theory-Guided Practice
- Fast Network Community Detection With Profile-Pseudo Likelihood Methods
- 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
- Near-optimal bounds for generalized orthogonal Procrustes problem via generalized power method
- On the smoothed analysis of the smallest singular value with discrete noise
- Inference for low-rank models
- Entrywise limit theorems for eigenvectors of signal-plus-noise matrix models with weak signals
- Spectral Clustering via Adaptive Layer Aggregation for Multi-Layer Networks
- Special invited paper: the SCORE normalization, especially for heterogeneous network and text data
- Inference for heteroskedastic PCA with missing data
- Statistical Significance of Clustering with Multidimensional Scaling
- Strong consistency guarantees for clustering high-dimensional bipartite graphs with the spectral method
- Rejoinder: “Co-citation and Co-authorship Networks of Statisticians”
- Clustering High-Dimensional Noisy Categorical Data
- Leave-one-out singular subspace perturbation analysis for spectral clustering
- Exact minimax optimality of spectral methods in phase synchronization and orthogonal group synchronization
- Optimal and exact recovery on the general nonuniform hypergraph stochastic block model
- Partial recovery and weak consistency in the non-uniform hypergraph stochastic block model
- High dimensional factor analysis with weak factors
- Perfect spectral clustering with discrete covariates
- Community detection in signed networks: a penalized semidefinite programming framework
- Joint Spectral Clustering in Multilayer Degree-Corrected Stochastic Blockmodels
- Higher-order entrywise eigenvectors analysis of low-rank random matrices: bias correction, Edgeworth expansion and bootstrap
- Semi-supervised clustering of sparse graphs: crossing the information-theoretic threshold
- Exact recovery discrimination in planted bisection model
- Simultaneous estimation and group identification for network vector autoregressive model with heterogeneous nodes
- Estimating Higher-Order Mixed Memberships via the l2,∞ Tensor Perturbation Bound
- Optimal Network Membership Estimation under Severe Degree Heterogeneity
- Asymptotic limits of spiked eigenvalues and eigenvectors of signal-plus-noise matrices with weak signals and heteroskedastic noise
- Uniform error bound for PCA matrix denoising
- Optimal estimation of misclassification rate for two-class clustering with sub-Gaussian noises
- Network-adjusted covariates for community detection
- Deflated HeteroPCA: overcoming the curse of ill-conditioning in heteroskedastic PCA
- 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
- Dimension Reduction for Large-Scale Federated Data: Statistical Rate and Asymptotic Inference
- Inference for Low-Rank Models Without Estimating the Rank
- Nonparametric two-sample hypothesis testing for low-rank random graphs of differing sizes
- An overview of asymptotic normality in stochastic blockmodels: cluster analysis and inference
- Consistency of Lloyd's algorithm under perturbations
This page was built for publication: Entrywise eigenvector analysis of random matrices with low expected rank
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2196228)
