An ℓp theory of PCA and spectral clustering

2022/08/01 by Emmanuel Abbe, Emmanuel Abbé, Jianqing Fan +1 · 32 citations
Computer Science · Engineering · Mathematics · #Algorithm #Applied mathematics #Artificial intelligence #Blind Source Separation Techniques #Cluster analysis #Computer science #Eigenvalues and eigenvectors #Gaussian #Heteroscedasticity #Mathematics #Matrix norm #Pattern recognition (psychology) #Principal component analysis #Random Matrices and Applications #Sparse PCA #Sparse and Compressive Sensing Techniques #Spectral clustering #Statistics

paper · open access · doi:10.1214/22-aos2196

published in The Annals of Statistics 50(4) (Institute of Mathematical Statistics)

openalex publication_date 2022/08/01 · openalex created_date 2022/08/29 · openalex updated_date 2026/07/22

Abstract

Principal Component Analysis (PCA) is a powerful tool in statistics and machine learning. While existing study of PCA focuses on the recovery of principal components and their associated eigenvalues, there are few precise characterizations of individual principal component scores that yield low-dimensional embedding of samples. That hinders the analysis of various spectral methods. In this paper, we first develop an ℓp perturbation theory for a hollowed version of PCA in Hilbert spaces which provably improves upon the vanilla PCA in the presence of heteroscedastic noises. Through a novel ℓp analysis of eigenvectors, we investigate entrywise behaviors of principal component score vectors and show that they can be approximated by linear functionals of the Gram matrix in ℓp norm, which includes ℓ2 and ℓ∞ as special cases. For sub-Gaussian mixture models, the choice of p giving optimal bounds depends on the signal-to-noise ratio, which further yields optimality guarantees for spectral clustering. For contextual community detection, the ℓp theory leads to simple spectral algorithms that achieve the information threshold for exact recovery and the optimal misclassification rate.

Citations

• On the distribution of the largest eigenvalue in principal components analysis
• The Rotation of Eigenvectors by a Perturbation. III
• A Least Squares Estimate of Satellite Attitude
• Least squares quantization in PCM

Cited by

• On spectral clustering under non-isotropic Gaussian mixture models
• New perturbation bounds for low rank approximation of matrices: Beyond Eckart-Young-Mirsky
• Finite-sample certification and operating envelopes for spectral clustering and graph centrality
• Multiply Robust Inference of Average Treatment Effects by High-dimensional Empirical Likelihood
• Beyond Sin-Squared Error: Linear-Time Entrywise Uncertainty Quantification for Streaming PCA
• High-dimensional Clustering and Signal Recovery under Block Signals
• Optimal Network-Guided Covariate Selection for High-Dimensional Data Integration

Related

• An ℓ_p theory of PCA and spectral clustering
• Two-way kernel matrix puncturing: towards resource-efficient PCA and spectral clustering
• Bayes-optimal limits in structured PCA, and how to reach them
• Correlated-PCA: Principal Components' Analysis when Data and Noise are Correlated
• The ϕ-PCA Framework: A Unified and Efficiency-Preserving Approach with Robust Variants