Event Date:
Event Location:
- Zoom Webinar
Title: An ℓp theory of PCA and spectral clustering theory of PCA and spectral clustering
Abstract:
We 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. For sub-Gaussian mixture models, the choice of p in the theoretical analysis depends on the signal-to-noise ratio, which further yields optimality guarantees for spectral clustering. For contextual community detection, the ℓp theory leads to a simple spectral algorithm that achieves the information threshold for exact recovery. This provides optimal recovery results for the stochastic block model and Gaussian mixture model as special cases.
(Joint work with Emmanual Abbe and Kaizheng Wang)