# Spectral Approaches to Nearest Neighbor Search

arXiv: https://arxiv.org/abs/1408.0751 · HTML: https://mlsanity.com/paper/1408.0751/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Aug 2014.

## Built on by (most cited first, 5 of 5)

- [Learning to Hash Robustly, Guaranteed](https://mlsanity.com/paper/2108.05433/) (2021)
- [Unsupervised Space Partitioning for Nearest Neighbor Search](https://mlsanity.com/paper/2206.08091/) (2022)
- [Improved analysis of randomized SVD for top-eigenvector approximation](https://mlsanity.com/paper/2202.07992/) (2022)
- [GARLIC: GAussian Representation LearnIng for spaCe partitioning](https://mlsanity.com/paper/2505.24608/) (2025)
- [Learning Partition Trees for Nearest Neighbor Search](https://mlsanity.com/paper/2607.09909/) (2026)

## Abstract (arXiv)

We study spectral algorithms for the high-dimensional Nearest Neighbor Search problem (NNS). In particular, we consider a semi-random setting where a dataset P in ℝd is chosen arbitrarily from an unknown subspace of low dimension kll d, and then perturbed by fully d-dimensional Gaussian noise. We design spectral NNS algorithms whose query time depends polynomially on d and log n (where n=|P|) for large ranges of k, d and n. Our algorithms use a repeated computation of the top PCA vector/subspace, and are effective even when the random-noise magnitude is em much larger than the interpoint distances in P. Our motivation is that in practice, a number of spectral NNS algorithms outperform the random-projection methods that seem otherwise theoretically optimal on worst case datasets. In this paper we aim to provide theoretical justification for this disparity.