SVD Provably Denoises Nearest Neighbor Data

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…