IDEAL Workshop: Erik Waingarten, Johnson-Lindenstrauss for Clustering and Subspace Approximation

The Johnson-Lindenstrauss lemma says that for any set of vectors in a high-dimensional space, there exists an embedding into a much lower dimensional space which approximately preserves all pairwise distances. Here, we explore dimensionality reduction for other geometric optimization problems: given a geometric optimization problem (for example, k-means clustering or principal components analysis) is there always an embedding to a lower dimensional space which approximately preserves the cost of the optimization? In this talk, I will overview a few results in this space, and present a new technique for using coreset constructions in order to get improved dimensionality reduction.

Based on joint work with Moses Charikar.