This is the authors' abstract. We don't add key points for this paper.
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 Rᵈ is chosen arbitrarily from an unknown subspace of low dimension k 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 { 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.
Answers are grounded in this paper and cite their sources.
No takes yet. Share an insight, caveat, or question.
Abdullah et al. (2014) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: