Efficient Dimension Reduction with Guarantees, from Clustering to Hashing

In the first part of the talk, we discuss an semidefinite programming relaxation of the k-means clustering problem. We show that even when the SDP is not tight, its solution produces a denoised copy of the original set of points, and can be combined with a rounding scheme to produce a set of k centers with improved stability guarantees under subgaussian mixture model compared to previous algorithms.

In the second part, we discuss locality sensitive hashing (LSH) for approximate nearest neighbor search. We introduce a fast variant of the cross-polytope LSH scheme for angular distance. To our knowledge, is the first LSH scheme with provably optimal sensitivity which is also fast.