![Algorithmic Spectral Graph Theory_hi-res logo](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-01/Algorithmic%20Spectral%20Graph%20Theory_hi-res.jpg?h=bc58dfd7&itok=8NAdfoPF)
Abstract
We study spectral algorithms for the high-dimensional Nearest Neighbor Search problem (NNS). In the practice of NNS,spectral approaches are quire popular and often outperform the random-projection methods that otherwise seem theoretically optimal (on worst case datasets). This study aims to address the above disparity in our understanding.
In particular, we consider a semi-random setting where a dataset P in R^d is chosen arbitrarily from an unknown subspace of low dimension k (much less than d), and then perturbed by fully d-dimensional Gaussian noise. We design spectral NNS algorithms whose query time depends polynomially on d and log|P| for large ranges of k and d. Our algorithms use repeated computation of the top PCA vector/subspace, and are effective even when the random-noise magnitude is much larger than the interpoint distances in P.
Joint work with Amirali Abdullah, Ravi Kannan, Robi Krauthgamer.