SVD Provably Denoises Nearest Neighbor Data
Authors: Ravindran Kannan
Kijun Shin
David Woodruff
Venue: ICLR 2026 Poster (2026)
Keywords: nearest neighbor
planted models
Primary area: optimization

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$ 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 $\sigma^2$ on each coordinate. Without loss of generality, we may assume the nearest neighbor is at distance $1$ from the query, and that all other points are at distance at least $1+\varepsilon$. 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 $\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 $\sigma \gg 1/k^{1/4}$, NN in uncorrupted data is not even {\bf 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 $\sigma \gg 1/\sqrt k$, the noise magnitude ($\sigma \sqrt{d}$) is 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.
\end{enumerate}

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. (Abdullah et al., 2014)). Another comparison with (Abdullah et al., 2014) is that it requires $\sigma$ to be at least an inverse polynomial in the ambient dimension $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.

SVD PROVABLY DENOISES DATA
NEAREST
NEIGHBOR
Ravindran Kannan', Kijun Shin?, David 2
1 Simons Institute, UC Berkeley, kannan1 000 11. com
CCarnegie Mellon University, (k1 junshi,
cmu edu
ABSTRACT
We study the Nearest Neighbor Search (NNS) problem a high-dimensional set- ting where data originates from low-dimensional subspace and is corrupted by Gaussian noise. Specifically, we consider a semi-random model where n points from an unknown k-dimensional subspace of ı2 (k < d) are perturbed by zero- mean d-dimensional Gaussian noise with variance o² on each coordinate. We assume that the second-nearest neighbor is at least a factor (1 + E) 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 E O(1/kA/4), we show that simply performing SVD denoises the data; namely, we provably recover accurate NN of uncorrupted data (Theo- rem L.Ip
For >> 1/k'/4, NN in uncorrupted data is even identifiable from the noisy data in general. This is matching lower bound on with the above result, demonstrating the necessity of this threshold for NNS (Lemma 3.T).
3. For 1/VÆ, the noise magnitude (a significantly exceeds the inter- point distances in the unperturbed data. Moreover, NN noisy data is dif- ferent from NN the uncorrupted data in general.
Note that (1) and (3) together imply SVD identifies correct NN in uncorrupted data even in regime where it is different from NN in noisy data. This was not the case in existing literature (see e.g. (Abdullah et al.] 2014)). Another comparison with (Abdullah et al.) 2014)) is that it requires a to be at least an inverse polyno- mial in the ambient dimension d. The proof of (1) above uses upper bounds on perturbations of singular spaces of matrices as well concentration and spherical symmetry of Gaussians. We thus give theoretical justification for the performance of spectral methods in practice. We also provide empirical results real datasets to corroborate our findings.
INTRODUCTION
The nearest neighbor problem is fundamental task in various fields, including machine learning, data mining, and computer vision. It involves identifying the data point closest to given query point within 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 unknown k-dimensional subspace of IRd (k < d) are perturbed by adding d-dimensional Gaussian noise N2 d²Ia) to it.
A fundamental tool in high- dimensioonn computational geometry, often applied to the NNS prob- lem, is the random projection method. The Lindeenn-nndssstruuss Lemma (Johnson and Linden- strauss 1984) demonstrates that projecting data onto a uniformly random k-dimensional subspace

---

of Rd approximately preserves distances between points, offering a computationally efficient way to reduce dimensionality. This approach has had tremendous impact on algorithmic questions in high-dimennsonal geometry, leading to the development of algorithms for approximate NNS, such as Locality-Sensite Hashing (L.HH) (Indyk and Motwani] 1998), which are widely used both the- oretically and practically. All known variants of LSH for Euclidean space, including (Datar al.)
2004 Andoni and Indyk] 2006; Andonii et al. 2014), involve random projections.
However, it is natural question whether performance can be improved by replacing "random" pro- jections 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 heuris- tics such as PCA trees (McNames 2001 [Sproull] [99I] Verma et al. 2009). spectral hashing (Weiss) al. 2008), and semantic hashing (Salakhutdinov and Hinton| 2009) These data-adaptive methods frequently outperform algorithms based on oblivious random projections in practice. Yet, unlike ran- dom 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 Massive Data Analysis, see, e.g., (Council 2013). For worst-case inputs, random projections are known to be theoretically optimal (Alon 2003 Jayram and Woodruff 2013), making challenging to theoretically justify data- awtre improvements. This paper aims provide theoretical justification for this disparity by studying data-aware projections for the NNS problem.
To address this challenge, study the semi-random setting proposed in (Abdullah et al. [014). In this setting, dataset P of n points in Rd, and a query point q are arbitrarily drawn from an unknown k-dimensional subspace (where Gaussian noise Na(0, a² [a). The goal is to find the point p E P that is closest to in Euclidean distance (considering their unperturbed versions). based on noisy versions.
< d) and then perturbed by adding d-dimensional
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 previous approaches, such as those in (Abdullah et al.] 2014). 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 o >> 1/Vd, the noise magnitude (with an expected magnitude of ov can be sub- stantially larger than the inter-point distances in the original data. Specifically, random Lohnsonn-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 a >> 1/vd.
For a E O(1/dt/1), (Abdullah et al. 2014) proved that the nearest neighbor in the perturbed data remains the same. Their algorithm tolerates a noise level of most O(1/v (il//kdd//)) which implies must be at least an inverse polynomial in the am- bient dimension d.
For a > 1/Vk, the nearest neighbor in the perturbed data can, with large probability, differ from the true nearest neighbor.
For E ( 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 critical improvement over the previous work of (Abdullah al., [014), as our algorithm effective for a 1/VT where the NN in noisy data is different from the NN in uncorrupted data.
For > 1/K2/4, we show that it is information-theorriiies nearest neighbors from the noisy data. This result complements our algorithmic findings by providing matching lower bounds the noise level a,, thereby demonstrating the necessity of the threshold a = (11/k1/4) for NNS.
impossible to identify the
1.1 HIGH-LEVEL OVERVIEW
In addition to improved noise tolerance, our algorithm offers simplicity, requiring only two SVD calls, unlike the iterated PCA approach in (Abdullah al. 2014). We now discuss the high-level
2

---

idea of our algorithm. We represent the input points as the first columns of d x (n + 1) matrix B, with the last column being the query point q. Similarly, we represent the Gaussian noise as a d x (n+11 1) matrix C with i..d. entries drawn from (0, o²). Let A B + C' denote the perturbed data set, which serves as the input to our algorithm. Our approach involves computing the SVD of A and projecting A onto its top k-dimensional subspace. A direct application of the SVD) was not explored in earlier works to handle such high noise levels. The only earlier work we are aware of with related provable guarantees in a noisy model via the SVD is that on latent semantic indexing (Papadimitriou et al. 2000), though (Papadimitriou et al. 2000) makes strong assumptions.
More specifically, we process the j indices in two parts: first for 1 S S 3. then for 2 ++1sj S n. Let A be a d x (2 + 1) matrix consisting of the first n/2 columns of A and the query point (as column n/2 + 1). Similarly, let A be d x (# + 1) matrix formed by the last n/2 columns of A and the query point. The query point in both parts. This superseript notation, (1) and (2), is also extended B and C. Let U(I) be the subspace spanned by the l top singular vectors of the first n/2 columns of A (i.e., (1, DD. Similarly, (122 is the subspace spanned by the k top singular vectors of the first n1/ columns of A (i.e., [( SD. Since A and A are given, (1)) and (2) can be computed. The point of splitting the data into 2 parts is that Puca and A0) are stochastically independent and this makes our probabilistic arguments simpler. It is not clear that this is necassary and we leave it as an open question as to whether the simpler algorithm without splitting provably works.
We denote the projection matrix onto subspace U C R as Pv. The underlying idea is that pro- jecting points (both data and query) onto the SVD subspace effectively extracts the latent subspace structure, which is sufficient to estimate distances, |/p; gll- Thus, the main algorithm proceeds as follows: to estimate all distances for the first n1/ points, we compute the minimum value of:
(A A /
min
Puce
where 4 denotes the j-th column of A With Iy = = - 0n/2+1, this expression simplifies to ||Pore A0xz]] Our claim is that, under specific noise regime, ||Prre A()rr provides Ip: - all for any > O. Subsequently, similar steps are performed for the second part of the data. The complete algorithm is then as follows:
(1 + appppooxiiatoo of | ||
Algorithm (1 + appprxxiie NNS for the
Model
Require: An ambient space Rdd and a matrix A E Rdx(x+1) representing the perturbed point set. Ensure: Returns the index of (1 + apaapoooiee nearest neighbor for the unperturbed data. 1: (1) + matrix formed by columns to n// of A and column n + 1 of A.
2: A(2) + matrix formed by columns n1/2 + to of A and column n + 1 of A.
3: U(1) + the subspace spanned by the & top singular vectors of (1))
4: (T(2) + the subspace spanned by the k top singular vectors of (2)
5: ji + arg minl |Pree (1) xx,
6: j2 + arg argmingssist
Pras xx))
7: if Perc A x || <
|| Peycs (2) x%al then
8: Return ji.
9: else
10: Return j2 + n/2.
11: end if
Below, we formalize the theoretical guarantee of Algorithm 1 Let 8 (x) denote the k-th singular value of matrix X. If rank(X) < k. then 8 X)=x is defined as O.
(X)
Theorem 1.1. For the semi-random model described above, if the noise level a satisfies:
min (V E min () (1( 21 |B(] x11l) E. (inn(s(B(()) sn (B())) E min (()B()) x B(2)
240
(k In14
75
36vInn
Algorithm returns (1 + e)aaprooximate nearest point for with probability at least
3

---

Remark 1.2 (Interpretation of Bounds). Theorem 1.1 highlights two distinct scaling requirements for recovery:
1. Intrinsic Dimension (k): The term 041/K4/4 reflects the geometric complexity of the subspace. This threshold aligns with the information-theene theoretic limits of preserving nearest neighbor structures (see Lemma 3.7)
Signal Strength (sa(B)); The term proportional to sx(B)/Vī bounds the spectral gap. By Wedin's 's Theorem, this ratio ensures that the principal angles between the true subspace V and the empirical subspace U remain small. If sx(B) were too small, the signal directions would be indistinguishable from noise directions, making subspace recovery impossible regardless of the algorithm used. We discuss this factor in Section 2.3
This highlights the power of SVD in extracting low-dimensional structure from noisy high- dimensional observations. We also explored impact through our empirical results. Our empirical results further validate our theoretical findings, demonstrating the practical benefits of our SVD- based approach and its superior performance compared to naïve algorithms,, particularly in terms of noise dependence the intrinsic subspace dimension ic and sensitivity to the k-th minimum singular value of the data sx(
Organization: Section 2 details our algorithmic approach, including the problem setup and the SVD-based algorithm, along with its analysis and discussion. Section providees theoretical lower bounds, demonstrating the optimality of our proposed noise thresholds. Section presents empirical results that validate our theoretical findings and illustrate the practical benefits of our approach.
ALGORITHMIC RESULTS
2.1 THE MODEL AND PROBLEM
We employ a semi-random data model that assumes the original data consists of n arbitrary (not random) points from k-dimensional subspace V of Rd We also assume the query point lie in V. The original data is latent (hidden), and so is V. The input is noisy data, obtained by adding Gaussian noise the original data. Such a semi-random model has been widely used (Abdullah)
et al. 2014 Azar et al. 200T).
B is a (n + 1) matrix where the first n columns represent the latent data points, and the last column represents the latent query. C is a d (n 1) matrix representing the perturbations to the n latent data points and the query. We assume the entries C are i.i.d. random variables, each drawn from NN, o?). The observed data A B + C constitutes the input the problem. For notational convenience, let z'2 = ej Gn+1 such that B.j - B, = Bay. The objective is to output a (1 + apapprooiee nearest neighbor for > 0. Specifically, the goal is to find an index j E (1,2..... .., n) satisfying Bar (1 +)) minigisn |Bx|ll-
2.2 ANALYSIS
We are now ready to start the proof of Theorem 1.1 We said that P/ [|PorrsA)))) A0)zy is a good ap- proximation 2z) Below, Lemma 2.1 quantifies how well the projected noisy distances approximate the true latent distances, plus an expected noise term (2ka²). Hence, we can infer that if satisfies: || 21,1l minigisu/2 PP (1)) || then, j approximately minimizes ||B0x,]l over [|B()x for sis n/2 within error at most the right hand side of 11.
Lemma 2.1. Assume B(1) has rank k, 2 d, and k In Then, for each S s n/2, the following holds with at least 1 - + probability:
Puce A0)z)) 2 2ko² -||B(U0 x
<
1 (B((1T
40
20 1B)x
Vin 2002 (1)
(B(22)
4

---

Similarly, assuming 2 has rank k, n 2 and ls 2 In then each 1 S $ n/2, the following holds with at least n probability:
||| Purss A
12
A
2ko² -
10003n [B))
|2
400v
1| 20 [()) Vln + 40o² V Inn.
$
+
(B(1())
Proof. Without loss of generality, we prove only the first part. Since all data points and the query point q lie in V. projecting B()) onto V does not change it. Thus, Pv. Pv = B(), Therefore, the following holds:
A Pirca (BO) + +(()) = B(V) + (Pur Pv) + Prac C())
We aim to bound each term in this expression. First, || - Pvll can be bounded in terms of the k-th singular value s (). Second, Perca C is random Gaussian vector, as per the definition of the noise matrix C. Thus, in the lemma statement, terms containing S%. (B()) relate to the effect of the (Pure) - Pv)B(Z x term, while the remaining terms are associated with the inner product of random Gaussian noise or the norm of the noise vector itself.
Since Pow is symmetric, we get:
2 = | + (Pre)- -PV) Puc x01
Pue A
= ||BWWZg
+ + Pr)B(12) 1|² |Poeres c azll
2x B(U)
(Pow Bv) + 2n² B(a)² Pow c0 + 2x Cayy Puce (Poi2) Pv) mz-
Now, Pv12) is idempotent: Pro Pyca = Pyon Also since the columns of B(1) lie in V, we have B() ((), Plugging these into the last term the right hand side of ( is zero (Prres (Pre Pv) 0). It turns out that each of the other terms can be bounded. By Lemma [2.4 Lemma 2.5 Lemma 2.6 and Lemma 2.7 below, together with the union bound, the thcorem is proved.
that term
Before proving the lemmas directly, we first show a bound on the spectral norm of the matrix Perce Pv. Recall that V the true underlying subspace containing the points and the query, while (2) the subspace spanned by the columns of the perturbed matrix A. Thus, bounds on the spectral norm of the difference between these two projection matrices can be expressed in terms of the noise follows. For this, we use well-established results from Numerical Analysis, namely, the sin O theorem by (Davis and Kahan 1970) and the corresponding theorem for singular subspaces due to (Wedin) 1972). which is stated as Lemma 2.2 below:
2018 Theorem 19)). Let B be real d x matrix with singular values $1 2 ... sm)n(d,n) 2 O and corresponding singular vectors U1,..., Umin(d.my Also, let E be an d x n perturbation matrix. Let s 2 ... ...2. 2 ('min(a,n) 2 O denote the singular values of B + E with corresponding singular vectors vi,,.., ".....,,mma "'iindd,n Suppose the rank of B is r. For 1 S S r, Then, V, and Vi both j dimensional spaces, the following holds for the (principal) angle between two subspaces:
Lemma 2.2 (O Rourke al.
let Vj and V be the subspaces spanned by (ui,..., 2/} and (u',,..,,'') v.)..
2 2
sin VVV,,V)) max min sin <(v,0))) Pv, Pvy DE NEV V'EY x'$00
s
33 - 5,+1
where 8r41
The bound in Lemma 2.2 in terms of the |E term, which is the spectral norm of the perturbation matrix. To use this, we need an upper bound on ||E|]. For this, we use a well-known result from Random Matrix Theory:
5

---

Lemma 2.3 (Rudelson and Vershynin 2010
Equation 2.3)). Suppose all entries of d x matrix
E are sampled (00, o²) i.i.d. Then the following holds for any t 2 0:
t2
Pr |E > o(vn+ va) + S 2xxp
2
Lemma 2.4. Assume that n 2 d, and B has rank k. Then for all holds with at least 4n2 probability:
j S n/2, the following
(P Pv) ||
10000n 5K (B12)
|BW22)
Lemma 2.5. Assume k 2 In and n 2 d. Then P| C(1) xyl1
-2k0 I 10 ko² holds
for all 1 Sj S n/2,, with at least 1 - 2n probability.
Lemma 2.6. Assume 2 d. and ((2) has rank k. Then, for all 1 S n/2, the following holds with at least
1 2n probability.:
4ovi (B(B(2)
1 BT (Poes PV)BW))
[
Lemma 2.7. For all Ssj S n/2, the following holds:
B Pereo Cray 3o 30
Vin
with at least 1 Inz probability.
We now use Lemma 2.1 to prove the following corollary, which quantifies the noise level tolerance needed for (1 + (E)) approxxitaii of the distance:
Corollary 2.8. Suppose the noise satisfies:
S min (V
| (B(( e [|B("xz))
240 1//
75
16vinn
Then, we have
|| Pure A (1)
1| 2ko² E
(1-3) B || (1
5)
3 [(() x3 =1/
3
for all 1 Sj S y with least
žn probubility. Similarly, the above holds for A and B(2)
We now provide the proof of Theorem I.I which offers the theoretical guarantee for our main algorithm:
Proof. Our algorithm returns the index j corresponding to the minimum value found across two parts of the minimization: minigjes/22 Prre A and min,//2-sj$sn |P A(2) (//2|l- Without loss of generality, assume that the first column of B (corresponding P1) is the nearest neighbor to the query point then we need to show that the algorithm selects an index j such that |B (1 + e) 11
Suppose our algorithm returns an index jr from the first part of the minimization, where S $ S n/2. By the algorithm's logic, this implies:
P 1|2 2kk² Poce A ()
2ko
Since the noise level a satisfies the conditions of Corollary
2.8 we have:
(1 (1-
:)
||
10y zz.
B
||
< A
||
Porer (2) || $ (1+
()
B ?
3
This implies
L
1+
B
- e/3/3
Thus, the desired result is obtained. If our algorithm returns an index j from the second part of the minimization, similar argument establishes the correctness of our algorithm.

---

2.3 DISCUSSION
Our work shows recovery even when the noisy nearest neighbor has changed, whereas (Abdullah jet al, 2014) operates in regime where the NN is preserved despite the noise, which is a key conceptual distinction. However, Theorem I.I shows that our algorithm can also be affected by the spectral property of the data matrix. We discuss several aspects of this difference in comparison to the prior work, as well as other aspects of our algorithm below.
Our noise bound for depends not only on O(k-1/4) but also on the term sy sB(B)// One might wonder if this term diminishes as the number of data points n increases, thereby weakening our central claim that o O(k 1/4). However, s sx(B) is a property of the entire d x (n + 1) data matrix B. As n increases, the matrix itself grows, and its singular values are generally expected to grow as well.
8 (B) term in Theorem 1.1
More precisely, for data matrix B whose columns (the data points) have a reasonably constant average norm, the squared Frobenius norm || E., B will grow approximately linearly with Since the squared Frobenius norm for our rank-k matrix B is also equal to the sum of its squared singular values, i.e. [| Σ s; (B)) 2 this growth must be distributed among the singular values. Furthermore, if the data matrix B is nell-comdiiionee-mennnng its singular values are not pathologically distributed and the data points do not collapse onto a lower-dimensional subspace-ther individual singular values are expected to scale proportionally to |B]|p = O(vR). Therefore, for well-conditioned data, the ratio 8x BB)/v/ is expected to converge to a non-zero constant rather than decay to O. An example of a well-conditioned matrix family is a random matrix where each entry is sampled independently and identically from a random variable with mean O, variance 1, and finite fourth moment (Bai and Yin 1993). They proved that for such an m n matrix (m S n), the smallest singular value is almost surely (1 //m/n)². The assumption that the data matrix is well-conditioned is standard for many real-world, high-dimensional datasets.
Comparison Prior Work (Abdullah et al., 2014). Prior work, unlike our algorithm, does not require any assumption on the singular values of the (latent) data matrix. However, this generality comes at the cost of a much stricter noise requirement, where the noise level a must be bounded by an inverse polynomial in the ambient dimension d. By contrast, approach introduces de- pendency on the data's 's spectrum sx (B) but achieves significantly improved noise tolerance with respect to the intrinsic dimension k. Our contribution is therefore most impactful in the common scenario where the ambient dimension d is very high, but the data lies near a low-dimensional, well- conditioned subspace (i.e., large d, small k). We believe this represents valuable and practical trade-off.
Connection between Johnson-Lindenstrane Lemma and Our Results. The upper bounds of a in Theorem I depend on three terms. For the first term to be the smallest, our theorem requires k = Q(In n/²²). This term D(In//²²) also appears in the standard Oohnson-Lindenstrauss (JL) Lemma. The JI. Lemma states that a random projection of n data points from d-dimensional ambient space into a k-dimensional subspace preserves all pairwise distances up to a (1 + e) multiplicative factor. The JL Lemma thus establishes the required dimensionality for oblivious random projection to preserve the geometry of n points, where = 2(n n n/e²) is known to be the information-theorrtiic complexity for the pairwise distance preservation problem.
Our result implies that for SVD to an effective denoising strategy for NNS, the underlying sub- space containing the true signal must itself have complexity that scales in JL-like manner. If k were smaller than this threshold, the k-dimensional subspace would be too simple to robustly encode the identity of the nearest neighbor against noise across all points. In summary, the JL Lemma focuses on dimensionality reduction (from d - k) using random projections. Conversely, our work addresses denoising when the data already possesses low intrinsic dimension k. We demonstrate that if the data has this structure and k satisfies this fundamental complexity requirement, then us- ing SVD enables accurate NNS recovery in a high-noise regime (a = Okk- a regime where standard JI. would fail to preserve the nearest neighbor identity.
7

---

Matrix Split Ratio Choice. In our algorithm, split the perturbed point set into two halves. This 50-50 split ratio is actually a minimax optimal choice. The primary goal of splitting the data to obtain a set of learned singular vectors (e-g. spanning subspace U(2)) that are stochastically independent of the noise in the data we intend denoise (e.g.. A(!). The accuracy of this learned subspace (122) as an estimate for the true latent subspace V depends directly the number of data points used to compute it (i.e. (1 - p)m). A smaller partition size leads to a less stable SVD and a larger error in the estimated subspace, as quantified by the bounds on || Pv| in our proofs (Lemma 2.4. Note that the algorithm's 's overall performance is limited by the weaker of the two subspace estimations. Therefore, due to the inherent symmetry of our algorithm, the 50 50 split maximizes the size of the smaller partition, thereby providing the most robust performance when no prior information about the data's structure known.
Runtime of the Algorithm 1 The rumning time of our methods just involves two SVD calcula- tions on the two halves of the matrix, and using iterative methods, such as those in (Musco and Musco 2015j. each can be done in O(ndk/ min(1, /gap)) time, up to logarithmic factors, where gap 8k/8k+1 1. For our recovery guarantees (Theorem 1.1 we require (BB to be suf- ficiently larger than Then we expect that sx( sy (B) and S σ, which implies gap 8& [A)/s++1(4 (A)) - 1 will be large. This helps both for recovery and for the efficiency of the SVD calculation. We then need to project the data onto the top k components find, which is (Odkk) time.
Requirement to Know the Intrinsic Dimension k. In our setting, we need to know & to run our algorithm. In other words, choosing cutoff k' > k would imply = 0, yielding a vacuous bound. However, real-world data is often full-rank with a decaying spectrum. In practice, selecting k' is valid heuristic to capture signal "leakage" into lower singular values without capturing the bulk of the noise spectrum.
About K-nearest neighbors. Corollary 2.8 yields estimate of the latent distances after sub- tracting the constant noise term. Define the estimated squared distance
23 = [P -kk''
1 1 /5j$5/2
PP A x0n2/2122 2ko2,
and let d3 := |Br, = Ip,; 411 denote the corresponding latent distance (up to the half- splitting reindexing). Under the same noise regime as Corollary 2.8 with high probability we have, simultaneously for all j E [n].
2 E (1
(1+ g)+ d)
Consequently, selecting the K smallest projected noisy distances yields a (1 + -apro-aapto K K-neareest-niighbor set for the latent instance, and the order of the K closest neighbors is preserved up to (1+ O())) distortion.
3 LOWER BOUNDS
In Theorem we showed an algorithmic result for which a E O(1/k1/4) (resp. a E O(e).. In this section, demonstrate that this dependence on l (resp. e) for is optimal by establishing an information-thooeete lower bound showing that prove this hardness result for a computationally easier problem than the one we have addressed. Let Pi..... .a, q be points in R$ We note that reducing the dimension of the ambient space only makes the problem easier in our reduction. Let 81,...,5uy 6g be noise vectors where each component is drawn independently and identically from (0, We observe the perturbed points: P. = P. + 6, and 5q.
1/4/ (resp.
O(e)) is necessary. We
3.1 DEPENDENCE ON THE SUBSPACE DIMENSION k
The following sequence represents a reduction from the original problem to our target problem. Specifically, we starting from our NN recovery problem and making the problem instance easier
8

---

for any potential algorithm solve. If we prove that even this simplified, easier problem is impossible to solve reliably, it immediately implies that the original, harder problem (with the larger gap) must also be impossible to solve. Without loss of generality, assume the distance from to its nearest neighbor is 1. We assume > 0 is a fixed constant throughout this chain of reductions and each step introduces
constant change in parameters.
Given #1. pi...... P... there a unique index j" such that |1g 1Pp-pp-- Py- || S All other points satisfy 1/g P,ll 2 + E. The goal is to output j"
Given P1, 12. the goal is to distinguish between the two cases: (1) and ||2|| ||2|| 2 1, or (ii) |Pp 2 and P2 0. Given P1. the goal is distinguish between the two cases: ii Pl [O, [x). or (ii) P1 ~ (0, [&) and p2 =
0 and p2
To show the reduction from the first problem to the second, we show that the second problem is a special case of the first: Consider the case where the first problem has n 2, q = 0, |P2 1, the only correct answer NN is P1 (p2 is not valid answer). If |f only correct answer is 2. The final reduction step is based on the concentration of the chi-squared distribution. For asymptotically large k this concentration implies that any p N(0, [x) has norm that is almost except with exponentially small probability.
P1
1, P2 0, the
The following lemma is hardness result for the last problem:
Lemma 3.1. Suppose X, Y are random vectors in R& where X ~ N(0, and Y ((, (o++ 2.) Ifo E w(1/ (1)/k//4), then given the unordered pair {X, YJ, no test can tell which distribution the sample came from with high probability.
3.2 DEPENDENCE ON THE DISTANCE GAP
In a similar way as Section 3.1 we reduce the original NN recovery problem computation- ally simpler one to facilitate hardness analysis. The problem reduction details are available in the appendix. We only give the final lemma below:
Lemma 3.2. Suppose X, Y are random vectors in R2, where X (Ne,, 12) and Y N(1+ e) o² Ix). If a E w(E), then given the unordered pair {X, Y}, no test can tell which distribution the sample came from with high probability.
EXPERIMENTS
In this section, we implement and evaluate our main algorithm. First, we show that it empirically outperforms the naive algorithm, suggesting that the denoising effect of the SVD is significant. Second, we demonstrate that our analysis in Corollary 2.8 is tight with respect to the parameter (B).
4.1 EXPERIMENTAL EVALUATION
We first describe the details of our initial experiment. Our main algorithm is simple to implement. As a baseline, we compare it against a naïve algorithm that seleets the index minimizing ||Az, over 1 < j S n, where z/z = e.+1 - ej. This naïve method is affected by the ambient space Rd when determining the noise threshold required for successful recovery, while our main algorithm depends only on the latent subspace dimension A: (specifically. method does not mean the algorithm in the (Abdullah al., 2014p. We could not use them as a base- line because their time and space complexity made implementation infeasible for experimental setup.
O(k-1/4)). Note that this naïve
We evaluate algorithm two real datasets from different domains: one image-based and one text-based. Throughout the experiments, we fix the parameters as follows: n = 3 000, = 30, and 0.05. For given dataset and fixed noise level a,, perform 100 queries compute the success probability. As our algorithm is efficient and simple to implement, all experiments were conducted CPU with M1 chip and 16 GB of RAM. We give the full details of our datasets.

---

zdl dependence thraated
Figure 1: Performance comparison two world datasets (left) and analysis of the noise thresh- old's dependence on the singular value sy (B) (right).
1) Glo This is a set of pre-trained word embeddings where each English word is represented by a high-dimensional real vector. We use the GloVe Twitter 27B dataset, which provides 1 193514 word vectors of dimension 200. We randomly sample 300 to construct the data matrix B.
2) [ MNIST consists of 70 000 images of handwritten digits (0-9) grayscale, of which 60 000 are training and 10 000 testing. Each image is 28 28, yielding 784-dimensional vector of pixel intensities. We sample n = 000 training images (flattened to = 784) as data points.
Preprocessing. To align the real-world datasets with our theoretical model, we first performed rank-k approximation on the data matrix B. We then selected queries and rescaled the data to ensure the nearest neighbor was distance 1 and all other points were at least away. The full preprocessing details are available in the appendix.
Results. Across both datasets, our main algorithm consistently outperforms the naïve algorithm across the full range of a values. In particular, the failure threshold-the smallest a at which NN recovery becomes unreliable-is significantly higher for our algorithm. We observe two character- istic noise regimes: one where the noise is too small to affect the NN, and another where recovery information -hhorrticiyyl impossible. Between these extremes lies meaningful intermediate regime in which the performance of the two algorithms diverges. In this regime, the performance gap is more pronounced when the ambient dimension is large. The qualitative results are con- sistent across both image (MNIST) and text (GloVe) domains, indicating cross-domain robustness. These results illustrate the practical benefits of our approach.
4.2 DEPENDENCE ON s (B)
We now describe the details of our second experiment. While the analyses in Sections 2 and characterize the algorithm's 's performance in terms of the subspace dimension & and the distance gap E, it is also of interest to examine its dependence on s (B). In Corollary 2.8 we showed that our algorithm exhibits a linear dependence: a (s)) Our empirical results confirm these dependencies, suggesting that the analysis is tight.
Data Generation. For the second experiment, we generated synthetic data to analyze the algorithm's dependence on st.B), We constructed the data matrix B via an SVD-bbased approach, allowing us to explicitly control its singular values. A subsequent procedure was used to embed query and its nearest neighbor to satisfy the + distance gap condition. A detailed description of the data generation process can be found in the appendix.
Results. In this plot, we observe clear linear dependence each parameter across the full range of σ. The noise threshold defined as the value of a at which the success probability first drops below 90% for given parameter setting. For each parameter configuration, times to estimate the success probability. These results demonstrate that our theoretical analysis is tight. Note that this does not imply the optimality of our algorithm with respect ste( (B).
repeat the experiment 100
http:/yannn http:///wwm..euu..cc////////////
10

---

ACKNOWLEDGMENTS
The authors were supported in part Office of Naval Research award number N0001421 12647, and Simons Investigator Award.
REFERENCES
Amirali Abdullah, Alexandr Andoni, Ravindran Kannan, and Rohert Krauthgamer. Spectral approaches nearest neighhor search. arXiv preprint arXiv:/488.075: 2014.
William Johnson and Joram Lindenstrauss. Extensions of lipshitz mapping into hilbert space. Contemporary Mathematics, 26: 189-066, 1984.
Piotr Indyk and Rajeev Motwani. Approximate nearest neighbor: towards removing the curse of dimensionality. In Proceedings of the Symposium Theory of Computing (STOC), pages 604 613, 1998.
Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S Mirrokni. on p-stable distributions. In Proceedings of the ACM Symposiun Computational Geometry (SoCG), 2004.
hashing scheme based
Alexandr Andoni and Piotr Indyk. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Proceedings of the Symposium on Foundations of Computer Science (FOCS), pages 459-46494 -6-4, 2006.
Alexandr Andoni, Piotr Indyk, Huy Nguyen, and Ilya Razenshteyn. Beyond locality-sensitive hashing. In Proceedings of the -CAM Symposium on Discrete Algorithms (SODA), 2014.
James McNames. A fast nearest-ncighbor algorithm based on a principal axis search tree. Pattern Analysis and Machine Intelligence, IEFE Transactions on, 23(9):664-97) 2001.
Robert F Sproull. Refinements to nearest-neighbor scarching in k-dimensional trees. Algorithmica, 6:579-589, 1991.
Nikhilesh Verma, Samy Kpotufe, and Sanjoy Dasgupta. Which spatial partition adaptive to intrinsic dimension? In Proceedings of the Twenty-Fifth Conference on Uncertainty Artificial Intelligence, pages 565-574, AUAI Press, 2009.
Yair Weiss, Antonio Torralba, and Rob Fergus. Spectral hashing. In Advances in neural information processing systems, pages 1753-1760, 2008.
Ruslan Salakhutdinov and Geoffrey Hinton. Semantic hashing. International Journal of Approximate Reason- ing, (0(7):969-977 2009.
National Rescarch Council. Frontiers in Massive Data Anolysis. The National Academies Press, 2013, Avail- able from: http: /tt/://wwww /ww. nap http:////cccaclooo.ppppoooooooro
Noga Alon. Problems and results in extremal combinatorics Discrete Mathematics, 273:31-53, 2003.
TS S Jayram and David P Woodruff. Optimal bounds for -ondesn-lindenssrrauss transforms and streaming prob- lems with subconstant error. ACM Transactions on Algorithmss, 93):26, 2013. Previously in SODA' 11.
Christos H Papadimitriou, Prabhakar Raghavan, Hisao Tamaki, and Santosh Vempala. Latent semantic in- dexing: A probabilistic analysis. J. Comput. Syst. Sci., 61 (2):2177-333 2000.
Yossi Azar, Amos Fiat, Anna Karlin, Frank Mesherry, and Jared Saia. Spectral analysis of data. Conference Proceedings of the Annuad ACM Sympusium Theory of Computing, 01 2001. doi: 10. 10.1145/38075.. 380859.
Chandler Davis and W. M. Kahan. The rotation of eigenvectors by perturbation. iii. SIAM Journal Numerical Analysis, 7(1):1-66, 1970. ISSN 00361429. URL http://wwwwjsttr..rrg.. wwt.orr.rg//taa...
2949580
Per-Åke Wedin. Perturbation bounds in connection with singular value decomposition. BIT Numerical Mathe- matics, 12(1):99-11) 111, 1972.
Sean O Rourke Van Vu, and Ke Wang. Random perturbation of low rank matrices: Improving classical bounds. Linear Algebra and its Applications, 540:26-59, 2018. ISSN 0024-3795. doi: https://doi.org/10. 1016///./....laaaa 2017.1 1.014.
11

---

Mark Rudelson and Roman Vershynin. Non-asympiotic theory of random matrices: extreme singular values. In Proceedings of the International Congress of Mathematicians 2010 (ICM 2010) Volumes) Vol. Plenary Lectures and Ceremonies Vols. II IV: Invited Lectures, pages 1576-1602. World Scientific, 2010.
Z. D. Bai and Y. Q. Yin. Limit of the smallest eigenvaluc of large dimensional sample covariance matrix. The Annals Probability, 21(3): 1993. ISSN 0091 2168894X. URL URLLhttp://ww/ jstor. brg/stable/224457
Cameron Musco and Christopher Musco. Randomized block krylov methods for stronger and faster approxi- mate singular value decomposition. Advances neural information processing systems, 28, 2015.
B. Laurent and P. Massart. Adaptive estimation of a quadratic functional by model selection. The Annals of Statistics, 2865):1302 1338, 2000. doi: 00.1114/as010119977339
Luc Devroye, Abbas Mehrabian, Tommy Reddad. The total variation distance between high-dimennn dimeeniionnll gaussians with the same mean. arXiv preprint arXiv:1810.08693, 2023.
A SUPPLEMENTARY MATERIAL
A.1 POSTPONED PROOFS
A.1.1 PROOF OF LEMMA 2.4
Proof. B(D's columns all lie in V. So, 8k+ (B(L)) 0. Thus, instantiating Lemma 2.2 gives:
|P -Pll 2 ||
Sk (B(2))
Note that (22) is d x (3 + 1) matrix. Applying Lemma 2.3 with & == / (n(m2) gives:
PPace Pvll S
2 c|
20
Vi +
22n(8822)
80 80
(4)
8k (BR)
SN (B(2)
su (B(
with at least 1
4nd probability (using n 2 d, 10). In conclusion, the lemma is proved as follows:
Pr [P - -P)
{((()
100
( xz
2 1
4n²
for all 1 < S n/2.
A.1.2 PROOF LEMMA 2.5
Proof. From the definition of C()) and Zy. the vector y : C() E Rd just summation two Gaussian random vectors. Thus, y ~ N(0, 2a) Also, for any basis fui...., ux} of col(()(2), since Praca is projection matrix, the following holds:
Puce Ca)
||
Σ uuF
Note that Puee and (()) are stochastically independent (since PenU depends only on (22) and not on C(1)), Since y ~ (0,220² La) is spherically symmetric, its entries X, uf y are independent N (0, 20 random variables. Hence
X;
(uTv)² = ||-1|2 20²
-
2
where Z ~ x². Now we can apply the Masteatt tail bound LLaurent and Massart 2000 for x2 distribution.
Va 0, Pr Iz k| > 2v kr 2x
<e <
Setting x = 6 6n n, using the Laurant-Massin bound and taking the union over j = 1,2,3... .n. gives the Lemma.
17
12

---

A.1.3 PROOF OF LEMMA 2.6
Proof. We have
BUTT (Py - Pr)
Pr/l Prll| S1PPcc
12
(5)
Applying (4) to the right hand side, the proof completes.
A.1.4 PROOF OF LEMMA 2.7
Proof. yety:= B Pue: and CO),; zj are stochastically independent (Recall that B is not random, but, fixed matrix.) So, yCu)x; x. is real-valued Gaussian random variable ith distribution (0, |Iyll o²). Further, |lvl| < [| since Poee is projection matrix. Now, the Lemma follows by standard Gaussian tail bounds.
A.1.5 PROOF OF LEMMA
Proof. We want to calculate the KL divergence between two distributions. Let Pi (N, and P/ = NO0 (a² + [)). We evaluate this by computing the KL divergence between the joint distributions R1 (z, y) P2()) and R2(2, y) Pi)) Note that these two distribu- tions differ only by swap. Since the KL divergence is additive for independent distributions, the following holds:
DKL DK R2) = DKL (P) + (xz(P)))))
The formula for the KI. divergence between two multivariate k-dimensional gaussian distributions Q N(1,, E1) and Q2 N N(22, Σ2) is:
Σ2 +
|n + (42 - -1 (42 - mn) tr
DRI(Qil(22) 2
log
k
Σ
Using the above formula, we get
0² +1/k)
o²
2Dxz (12) k log
o²
02 + (1/k)
0²
+ l log +2+ (1/k)
+ k (1 (1+ (1/ko²))
1 1
= + k 1 + (1/ko2) + k +
g2 ko4
using 1/(1 + (1) < - + n? for E [0.1] Therefore, the KI. divergence approaches when
= 1/44) This means that it becomes impossible to determine which distribution the observed vector came from as l grows large.
A.1.6 PROOF LEMMA
Proof. Translating both distributions by -e, and scaling by 1/a reduces the problem to distinguish- ing (o, T&) from N ((ee/a)en (01, Jx) while preserving distinguishability. Because the coordinates are independent and identical except for the mean shift in the first coordinate, the optimal test depends only on the first coordinate. Thus, the task equivalent to distinguishing the 1-dimensional Gaus- sian distribution (0,, 12) and N(E/o, 1²). According to (Devroye et al. (002).. the total variation distance between two one-dimensional Gaussian distributions with unit variance is at most half the difference of their means. Therefore, drv (O 12), N( 12)) < e. which implies that based on the observed vector, it becomes impossible to determine which distribution it came from as 0.
13

---

Noise Regime
Magnitude
Random Projection
Abdullah et al. 2014)
SVD (Ours)
<IVVd
o(1)
Succeeds
v Succeeds
Succeeds
0(1/6//4) 2 Lovd
x Fails
v Succeeds
Succeeds
O(1/K2/4) NoVd
x Fails
x Fails
Succeeds
1/12/4 NoVd
x Fails
x Fails
Fails (info-theoretic)
Table I: Comparison of Noise Tolerance Regimes. SVD succeeds in the "Intermediate" regime
where the noise norm large enough to break Random Projections (RP), but structured enough to be filtered by SVD.
A.2 POSTPONED DETAILS
A.2.1
COMPARISON OF NOISE TOLERANCE REGIMES
A.2.2
PROBLEM REDUCTION DETAILS FOR SECTION 3.2
The following describes the original problem and the simplified target problem:
Given pl, .... ... q. there a unique index j* such that ||g Pj+ll S All other points satisfy 11 p,|| 2 + c. The goal is to output j"
(n = 2 and f = 0) Given p2, there is a unique index j* such that || S 1. The other
point satisfies |lp 2 1 + c. The goal is output j*.
(Fix the data generation process) Given pi, P2, distinguish between the two cases: (i) pr
61 and P2 = (1ec) or (ii) P1 (1 + c)0j and P2 = 01.
A.2.3 PREPROCESSING DETAILS FOR SECTION
Our theoretical guarantees assume that the data lies entirely in k-dimensional subspace, which does not strictly hold in real datasets. However, both datasets exhibit low intrinsic dimensionality. as indicated by the decay their singular values. To align with the theoretical assumptions and highlight performance within low-rank subspace, we apply rank-k approximation to the sampled matrix B by retaining only top singular components. This transformation preserves the essential structure of the data while making the setup consistent with our analysis.
For each dataset, we generate 100 query points by projecting held-out data onto the rank- subspace and selecting points whose searest-to-second--eee to the dataset structure, Glo vectors are eligible as query candidates, while for MNIST, queries sampled from the test set. After that, each column is rescaled such that the NN lies exactly distance from the query point, and i.i.d. noise N(0,, o²) is added. Finally, we randomly shuffle the first n columns to ensure that both B(1) and ((2) have rank k, as required by Theorem 1.1
neighbor distance ratio is just above 1+s. Due
A.2.4 DATA GENERATION DETAILS FOR SECTION
Unlike in the first experiment, this experiment is conducted on randomly generated datasets. The purpose here is to find concrete examples that clearly reveal the linear dependence of our algorithm on 84 (B). We fix the parameters as follows: the dependence on 8 (B), we start with the SVD decomposition B XΣY where X and Y are orthogonal matrices randomly generated via QR dccomposition of random Gaussian matrices. The singular values of B controlled by setting the diagonal entries of Σ.
200, d = 100, & 10, and & = 0.05. To study
However, the resulting matrix tion-tha that is, the requirement that the NN lies at distance exactly 1 from the query point, and the second NN is at distance at least + E. To enforce this condition, we proceed as follows. We first generate the first
XΣY may not automatically satisfy the distance gap condi-
columns of B using the above procedure.
Then, we sample a random direction iž that lies in the intrinsic k-dimensional subspace V. Essen- tially, embed the query point g 1 and the n-th point p.. t2 in the space for some scalars
14

---

and f2. The value to is set by starting from too and decreasing it until the distance between the nearest neighbor among the other n - points and t becomes 1 c. Then, we set t2 = f + 1 which makes the distance between the query point and this n-th point exactly 1. This construction makes the query point, its nearest neighbor, and the origin collinear. While one could add noise to these points to avoid this artificial colinearity, we believe would not affect the performance of the algorithms in our context.
15


Reviews:
[{"review_id": "zPyKwrKan9", "reviewer": "Reviewer_LHPh", "summary": "The paper studies the NNS problem in high dimensions and shows that if the noise is corrupted by Gaussian noise, then simply performing SVD recovers the NN of the uncorrupted data. This, I think, is a really nice result. \nThey study this phenomenon for various settings of variance of the Gaussian noise. It also improves the result of previous works that relied on the variance to be inverse polynomial in the ambient dimension.", "questions": "i would say that performing SVD is an expensive process, especially for high dimensional data points. Is there some other way one can do to speed up this proces?\n\nWhy should one believe that data matrix is well condition when the underlying data is the one used in NN? Is there any empirical evidence that the authors can point to?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The strength of the paper lies in the range of the variance for which they can show denoising using simple SVD.", "weaknesses": "It is hard to parse Theorem 1.1. It would be great if the authors had added more discussion on it right after the theorem. \n\n219: lemma not theorem\nLine 237: well-known\nWhy the growth of singular values has to be distributed?\nI am a little confused. Data matrix being well conditioned is a normal assumption in real datasets, but is it also the case for geometric problems like NN?\nMy personal opinion is that having a worse noise assumption is better than that on the data matrix because we can control the latter. I would love to hear the authors’ perspective on this front. \n\nOne important issue with the submitted version is that it takes an unfair advantage of the page limit by making the margin smaller than the ICLR format (at least it looks like that to me; I might be wrong). I wanted to flag this in case other reviewers also have an objection with that. I understand that margin bound is not explicitly stated in the Call for Papers, but this feels wrong to me, mainly due to this line in the Call for Papers: \"Papers with main text beyond the page limit will be desk-rejected.\"\n\nI leave the last point to the meta reviewers and AC to make a judgement on, especially in regards to fairness to other submissions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "U2kCb9uzbf", "reviewer": "Reviewer_N6hW", "summary": "This paper studies nearest neighbor problem while data is corrupted with random Gaussian noise. That is, given arbitrary $n$ points in $d$-dimensional space that can be embedded in a $k$-dimensional subspace, with zero-mean $d$-dimensional $\\sigma$-variance Gaussian noise, the algorithm is able to distinguish the nearest neighbor while all other points are at least $(1+\\epsilon)$ distance away. The paper gives detailed analysis on how large a $\\sigma$ may affect the distinguishability of the neighbor points. The algorithm is based on spectral method, specifically only two SVD calls, which outperforms the prior work that builds on a more complicated PCA tree, however, with an assumption that the $k$-th singular value is large enough.", "questions": "See weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Comparing to the prior work, i.e. Abdullah et al., 2014, this paper achieved an improved noise tolerance with a simple spectral method with two calls of SVD on randomly separated data points. While Abdullah et al., 2014 can tolerate up to Gaussian noise with variance of at most an inverse polynomial of $d$, this paper designs an algorithm that can handle $\\sigma=O(1/k^{1/4})$. On the other hand, the paper further extends the theoretical foundation for spectral methods that perform well on nearest neighbor search problems in many occasions, sometimes even better than the worst-case optimal random projection. The theoretical framework follows from Abdullah et al., 2014 by considering a semi-random model.", "weaknesses": "The paper assumes a random Gaussian noise, which follows from Abdullah et al., seems strong. In this case, the algorithm is highly dependent on a high amount of randomness. Is it possible to find the nearest neighbor when corruptions on $d$ coordinates are no longer independent? On the other hand, given the large top-$k$ sigular values assumption, it is not obvious why random projection will necessarily fail in this case. Therefore, is $\\sigma=\\Theta(k^{-1/4})$ a necessary criteria for spectral methods to outperform random projection? It would be nice to list all noise level thresholds when or when not SVD would be preferred to random projection.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1feqyGside", "reviewer": "Reviewer_7ikB", "summary": "This paper studies nearest neighbor search problem for high-dimensional spaces where the data lies low-dimensional subspace and is coordinate-wise corrupted by Gaussian noise. The authors shows that when the noise have small variance i.e. $\\sigma = O(k^{-1/4})$ they can recover the correct nearest neighbor; for large variance, recovery becomes impossible.", "questions": "1. The model assumes data drawn exactly from a low-dimensional linear subspace corrupted by isotropic Gaussian noise. Could you identify any realistic scenarios or application domains where this setting meaningfully reflects observed data distributions.\n2. Do you think the dependence on the s_k is an artifact of the analysis or it is actually tight?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper establishes tight upper and lower bounds on the noise threshold for nearest neighbor recovery, providing a clear theoretical characterization of when SVD-based denoising succeeds. The proposed algorithm is conceptually simple and well-presented, with a clean and transparent analysis that makes the results easy to follow.", "weaknesses": "I think the main critism here is the setting is too ideal seems a bit far from practical: It assumes the points are exactly in a k-dimensional subspace.  Moreover, the guarantees depend on the singular value of the clean data matrix, which could be very large for ill-conditioned data.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GnFi2oV8BO", "reviewer": "Reviewer_U3vH", "summary": "This paper investigates the Nearest Neighbor Search (NNS) problem where data points, originating from an unknown $k$-dimensional subspace within a $d$-dimensional space ($k \\ll d$), are corrupted by Gaussian noise . The objective is to recover the nearest neighbor of the *uncorrupted* data, given only noisy observations and queries. The authors propose a simple SVD-based algorithm that involves splitting the data matrix, computing the top-$k$ subspace for each half, and then projecting the data from one half onto the subspace derived from the other to find the nearest neighbor . The primary contribution is a proof that this method successfully recovers the true nearest neighbor even when the noise variance $\\sigma$ is as large as $O(1/k^{1/4})$ . This is a significant finding, as it holds in a noise regime where the nearest neighbor in the noisy data may differ from the true nearest neighbor. The authors establish this as a sharp threshold by providing a matching information-theoretic lower bound, demonstrating that recovery is impossible for $\\sigma \\gg 1/k^{1/4}$.", "questions": "1.  Could you please clarify the core technical novelty of your analysis? The data-splitting trick  simplifies the probabilistic argument, but is this the key element that allows you to break the dependency on the ambient dimension $d$ and achieve the $O(1/k^{1/4})$ bound? Or is there a new, non-standard bound or analytical step being used?\n\n2.  The discussion in Section 2.3 regarding the requirement to know $k$ is confusing . You state that using a \"larger dimensional SVD subspace projection\" (i.e., overspecifying $k$) \"may be of use if we want to work with weaker assumptions\" . This seems counter-intuitive. Your bounds in Theorem 1.1 depend on $s_k(B)$. If the true rank is $k$ and you use a $k' > k$, the $k'$-th singular value $s_{k'}(B)$ would be zero. This would make your noise bound infinitely restrictive, not weaker. Can you clarify how overspecifying $k$ could be helpful?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper addresses a practical and fundamental problem in data analysis. The main strength is the substantial improvement over prior SOTA (e.g., Abdullah et al., 2014), which required the noise level $\\sigma$ to be bounded by an inverse polynomial in the *ambient* dimension $d$. This work's bound of $\\sigma = O(1/k^{1/4})$ depends only on the intrinsic dimension $k$, which is a major advancement for $k \\ll d$ scenarios .\n\nThe work extends our understanding of this problem and identifies critical thresholds for $\\sigma$ and providing both an algorithmic upper bound and a matching lower bound. This comprehensive analysis is a key strength. Another significant contribution is showing that the algorithm works even when the noise is large enough ($\\sigma \\gg 1/\\sqrt{k}$) to change the identity of the nearest neighbor in the observed data, a regime not handled by previous work.\n\nThe algorithm itself is simple and clearly explained. The theoretical claims are supported by experiments on both synthetic and real-world datasets (Glove and MNIST), which confirm the algorithm's practical benefits over a naive approach and validate the theoretical dependency on key parameters .", "weaknesses": "The primary weakness is the lack of an explicit discussion of the paper's technical novelty. The analysis appears to rely on standard matrix perturbation bounds (like Davis-Kahan and Wedin) and concentration inequalities. The authors do not clearly articulate what new analytical techniques or core technical innovation enables them to achieve the $O(1/k^{1/4})$ bound, which is the paper's central improvement. It is unclear if the novelty lies simply in the data-splitting algorithm design, which simplifies independence arguments.\n\nThis new bound comes at the cost of a dependency on $s_k(B)$, the $k$-th singular value of the unperturbed data matrix. Prior work did not require this assumption. While the authors argue in Section 2.3 that $s_k(B)/\\sqrt{n}$ is likely a non-zero constant for \"well-conditioned\" data, this is a significant trade-off, especially when data is approximately embedded in a subspace (which is one core motivation of the model considered in this paper); see the question below about overspecification. \n\nThe experimental comparison is made against a naive baseline, not against the (Abdullah et al., 2014) algorithm that serves as the main theoretical comparator. The authors state this was due to the implementation infeasibility of the prior work, but this omission makes it difficult to empirically assess the practical performance gain over the previous state-of-the-art.\n\nFinally, some typos and clarity suggestions\n* \"weel-known\" instead of \"well-known\".\n* In Section 3.1, the query point $\\tilde{q}$ is missing from the problem description (Line 062), which makes the notation for $q$ confusing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)