Isotropic PCA and Affine-Invariant Clustering
| dc.creator | Brubaker, S. Charles | |
| dc.creator | Vempala, Santosh S. | |
| dc.date | 2008-04-22 | |
| dc.date | 2008-08-04 | |
| dc.date.accessioned | 2026-07-07T09:54:10Z | |
| dc.date.available | 2026-07-07T09:54:10Z | |
| dc.description | We present a new algorithm for clustering points in R^n. The key property of the algorithm is that it is affine-invariant, i.e., it produces the same partition for any affine transformation of the input. It has strong guarantees when the input is drawn from a mixture model. For 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 emoverlap in every direction is small. Here we define overlap to be the ratio of the following two quantities: 1) the average squared distance between a point and the mean of its component, and 2) the average squared distance between a point and the mean of the mixture. The main result may also be stated in the language of linear discriminant analysis: if the standard Fisher discriminant is small enough, labels are not needed to estimate the optimal subspace for projection. Our main tools are isotropic transformation, spectral projection and a simple reweighting technique. We call this combination isotropic PCA. | |
| dc.identifier | https://arxiv.org/abs/0804.3575 | |
| dc.identifier | http://arxiv.org/abs/0804.3575 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/166215 | |
| dc.subject | Machine Learning | |
| dc.subject | Computational Geometry | |
| dc.title | Isotropic PCA and Affine-Invariant Clustering | |
| dc.type | text |