Ravindran Kannan, Kijun Shin, David Woodruff
We study the Nearest Neighbor Search (NNS) problem in a high-dimensional setting where data lies in a low-dimensional subspace and is corrupted by Gaussian noise. Specifically, we consider a semi-random model in which $n$ points from an unknown $k$-dimensional subspace of $\mathbb{R}^d$ ($k \ll d$) are perturbed by zero-mean $d$-dimensional Gaussian noise with variance $Ï^2$ per coordinate. Assuming the second-nearest neighbor is at least a factor $(1+\varepsilon)$ farther from the query than the nearest neighbor, and given only the noisy data, our goal is to recover the nearest neighbor in the uncorrupted data. We prove three results. First, for $Ï\in O(1/k^{1/4})$, simply performing SVD denoises the data and provably recovers the correct nearest neighbor of the uncorrupted data. Second, for $Ï\gg 1/k^{1/4}$, the nearest neighbor in the uncorrupted data is not even identifiable from the noisy data in general, giving a matching lower bound and showing the necessity of this threshold for NNS. Third, for $Ï\gg 1/\sqrt{k}$, the noise magnitude $Ï\sqrt d$ significantly exceeds inter-point distances in the unperturbed data, and the nearest neighbor in the noisy data generally differs from that in the uncorrupted data. Thus, the first and third results together imply that SVD can identify the correct nearest neighbor even in regimes where naive nearest neighbor search on the noisy data fails. Compared to \citep{abdullah2014spectral}, our result does not require $Ï$ to be at least an inverse polynomial in the ambient dimension $d$. Our analysis uses perturbation bounds for singular spaces together with Gaussian concentration and spherical symmetry. We also provide empirical results on real datasets supporting our theory.