Randomized Non-Linear Projections Uncover High-Dimensional Structure.

. We consider the problem of investigating the "structure" of a set of points in highdimensional space (n points in d dimensional Euclidean space) when n !! d. The analysis of such data sets is a notoriously difficult problem in both combinatorial optimization and statistics due to an exponential explosion in d. A randomized non-linear projection method is presented that maps these observations to a low-dimensional space, while approximately preserving salient features of the original data. Classical statistical analyses can then be applied, and results from the multiple lower-dimensional projected spaces are combined to yield information about the high-dimensional structure. We apply our dimension reduction techniques to a pattern recognition problem involving PET scan brain volumes. The problem. Let x 1 ; : : : ; x n be a collection of n observations in ! d . The goal is to cluster the observations into g groups. We are concerned with this problem in the unsupervised case, where ..