SVD Provably Denoises Nearest Neighbor Data
Ravindran Kannan, Kijun Shin, David Woodruff · 2026
Read SVD Provably Denoises Nearest Neighbor Data by Ravindran Kannan, Kijun Shin, David Woodruff (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-03831.txt.
Introduction
Ravindran Kannan and colleagues proved that singular value decomposition can denoise nearest-neighbor search when data sit in a low-dimensional subspace plus Gaussian noise. When noise stays below a threshold tied to subspace dimension, SVD recovers the true nearest neighbor. Above that threshold, the true neighbor may not even be identifiable from noisy data, a matching lower bound. A third result shows naive search on noisy data fails in regimes where SVD still succeeds.
Catalog record
| CREATOR | Ravindran Kannan, Kijun Shin, David Woodruff |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 51833 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.03831
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
SVD Provably Denoises Nearest Neighbor Data Ravindran Kannan, Kijun Shin, David Woodruff Abstract We study the Nearest Neighbor Search (NNS) problem in a high-dimensional setting where data originates from a low-dimensional subspace and is corrupted by Gaussian noise. Specifically, we consider a semi-random model where n n points from an unknown k k -dimensional subspace of ℝ d \mathbb{R}^{d} ( k ≪ d k\ll d ) are perturbed by zero-mean d d -dimensional Gaussian noise with variance σ 2 \sigma^{2} on each coordinate. We assume that the second-nearest neighbor is at least a factor ( 1 + ε ) (1+\varepsilon) farther from the query than the nearest neighbor. We assume we are given only the noisy data and are required to find NN of the uncorrupted data. We prove the following results: 1. For σ ∈ O ( 1 / k 1 / 4 ) \sigma\in O(1/k^{1/4}) , we show that simply performing SVD denoises the data; namely, we provably recover accurate NN of uncorrupted data (Theorem 1.1 ). 2. For σ ≫ 1 / k 1 / 4 \sigma\gg 1/k^{1/4} , NN in uncorrupted data is not even identifiable from the noisy data in general. This is a matching lower bound on σ \sigma with the above result, demonstrating the necessity of this threshold for NNS (Lemma 3.1 ). 3. For σ ≫ 1 / k \sigma\gg 1/\sqrt{k} , the noise magnitude ( σ d \sigma\sqrt{d} ) significantly exceeds the inter-point distances in the unperturbed data. Moreover, NN in noisy data is different from NN in the uncorrupted data in general. Note that (1) and (3) together imply SVD identifies correct NN in uncorrupted data even in a regime where it is different from NN in noisy data. This was not the case in existing literature (see e.g. [ 1 ] ). Another comparison with [ 1 ] is that it requires σ \sigma to be at least an inverse polynomial in the ambient dimension d d . The proof of (1) above uses upper bounds on perturbations of singular spaces of matrices as well as concentration and spherical symmetry of Gaussians. We thus give theoretical justification for the performance of spectral methods in practice. We also provide empirical results on real datasets to corroborate our findings. 1 Introduction The nearest neighbor problem is a fundamental task in various fields, including machine learning, data mining, and computer vision. It involves identifying the data point closest to a given query point within a dataset. While conceptually straightforward, the performance and reliability of nearest neighbor search (NNS) can suffer in the presence of noise, particularly in high-dimensional spaces. Real-world data is susceptible to noise, which can ruin the true underlying structure and lead to erroneous nearest neighbor identifications. This necessitates robust techniques that can reduce the impact of noise to ensure accurate and reliable NNS. In this paper, we analyze the NNS problem in a noisy high-dimensional setting. Specifically, we consider a semi-random model where data points from an unknown k -dimensional subspace of \mathbb{R}^{d} ( k\ll d ) are perturbed by adding d -dimensional Gaussian noise N_{d}(0,\sigma^{2}I_{d}) to it. A fundamental tool in high-dimensional computational geometry, often applied to the NNS problem, is the random projection method. The Johnson-Lindenstrauss Lemma [ 13 ] demonstrates that projecting data onto a uniformly random k -dimensional subspace of \mathbb{R}^{d} approximately preserves distances between points, offering a computationally efficient way to reduce dimensionality. This approach has had a tremendous impact on algorithmic questions in high-dimensional geometry, leading to the development of algorithms for approximate NNS, such as Locality-Sensitive Hashing (LSH) [ 11 ] , which are widely used both theoretically and practically. All known variants of LSH for Euclidean space, including [ 8 , 4 , 3 ] , involve random projections. However, it is natural to question whether performance can be improved by replacing "random" projections with "best" or data-aware projections. Practitioners often rely on techniques like Principal Component Analysis (PCA) and its variants for dimension reduction, leading to successful heuristics such as PCA trees [ 15 , 21 , 22 ] , spectral hashing [ 24 ] , and semantic hashing [ 20 ] . These data-adaptive methods frequently outperform algorithms based on oblivious random projections in practice. Yet, unlike random projection methods, these adaptive approaches often lack rigorous correctness or performance guarantees. Bridging this gap between theoretical guarantees and empirical successes for data-aware projections is a significant open question in Massive Data Analysis, see, e.g., [ 7 ] . For worst-case inputs, random projections are known to be theoretically optimal [ 2 , 12 ] , making it challenging to theoretically justify data-aware improvements. This paper aims to provide a theoretical justification for this disparity by studying data-aware projections for the NNS problem. To address this challenge, we study the semi-random setting proposed in [ 1 ] . In this setting, a dataset P of n points in \mathbb{R}^{d} , and a query point q are arbitrarily drawn from an unknown k -dimensional subspace (where k\ll d ) and then perturbed by adding d -dimensional Gaussian noise N_{d}(0,\sigma^{2}I_{d}) . The goal is to find the point p\in P that is closest to q in Euclidean distance (considering their unperturbed versions), based on noisy versions. Our main contribution is a new Singular Value Decomposition (SVD) algorithm for solving the NNS recovery problem. This algorithm can tolerate substantially larger noise levels compared to previous approaches, such as those in [ 1 ] . Specifically, we characterize the robustness of NNS under various noise levels. We identify several critical noise level thresholds below in the increasing order of noise level: • For \sigma\gg 1/\sqrt{d} , the noise magnitude (with an expected magnitude of \sigma\sqrt{d} ) can be substantially larger than the inter-point distances in the original data. Specifically, random Johnson-Lindenstrauss projections will preserve these noisy distances, effectively losing the underlying nearest neighbor structure of the uncorrupted data. Therefore, SVD would be preferred to random projection when \sigma\gg 1/\sqrt{d} . • For \sigma\in O(1/d^{1/4}) , [ 1 ] proved that the nearest neighbor in the perturbed data remains the same. Their algorithm tolerates a noise level of at most \sigma=O(1/\sqrt{k}d^{1/4}) , which implies \sigma must be at least an inverse polynomial in the ambient dimension d . • For \sigma\gg 1/\sqrt{k} , the nearest neighbor in the perturbed data can, with large probability, differ from the true nearest neighbor. • For \sigma\in O(1/k^{1/4}) , our algorithmic results (Theorem 1.1 ) demonstrate that applying SVD to the perturbed data can effectively identify the true nearest neighbor in this regime. This represents a critical improvement over the previous work of [ 1 ] , as our algorithm is effective for \sigma\gg 1/\sqrt{k} where the NN in noisy data is different from the NN in uncorrupted data. • For \sigma\gg 1/k^{1/4} , we show that it is information-theoretically impossible to identify the nearest neighbors from the noisy data. This result complements our algorithmic findings by providing matching lower bounds on the noise level \sigma , thereby demonstrating the necessity of the threshold \sigma=O(1/k^{1/4}) for NNS. 1.1 High-level Overview In addition to improved noise tolerance, our algorithm offers simplicity, requiring only two SVD calls, unlike the iterated