Isotropic PCA and Affine-Invariant Clustering
- 1 October 2008
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE) in 2008 49th Annual IEEE Symposium on Foundations of Computer Science
- p. 551-560
- https://doi.org/10.1109/focs.2008.48
Abstract
We present an extension of principal component analysis (PCA) and a new algorithm for clustering points in \Rn based on it. The key property of the algorithm is that it is affine-invariant. When the input is a sample from a mixture of two arbitrary Gaussians, the algorithm correctly classifies the sample assuming only that the two components are separable by a hyperplane, i.e., there exists a halfspace that contains most of one Gaussian and almost none of the other in probability mass. This is nearly the best possible, improving known results substantially. For k>2 components, the algorithm requires only that there be some (k-1)-dimensional subspace in which the ``overlap'' in every direction is small. Our main tools are isotropic transformation, spectral projection and a simple reweighting technique. We call this combination isotropic PCA.Keywords
This publication has 4 references indexed in Scilit:
- On Learning Mixtures of Heavy-Tailed DistributionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Learning mixtures of separated nonspherical GaussiansThe Annals of Applied Probability, 2005
- The Spectral Method for General Mixture ModelsLecture Notes in Computer Science, 2005
- Learning mixtures of GaussiansPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003