Spectral Approaches to Nearest Neighbor Search

Spectral methods for high-dimensional nearest-neighbor search can perform well in practice even when random projections appear preferable under worst-case theory. This talk studies that difference in a semi-random model: points lie in an unknown low-dimensional subspace and are then perturbed by Gaussian noise in the full ambient space. The algorithms repeatedly compute a leading principal component or subspace and achieve query times polynomial in the ambient dimension and logarithm of the number of points over substantial parameter ranges. They can remain effective when noise is much larger than the distances among the original points. The work is joint with Amirali Abdullah, Ravi Kannan and Robi Krauthgamer.