The Noisy Laplacian: a Threshold Phenomenon for Non-Linear Dimension Reduction
Authors: Alex Kokot
Octavian-Vlad Murad
Marina Meila
Venue: ICML 2025 poster (2025)
Keywords: Dimension Reduction
Denoising
Diffusion Maps
Laplacian
VAE
LTSA
Primary area: general_machine_learning->unsupervised_and_semisupervised_learning
TL;DR: We show that manifold spectral data can be recovered from noisy samples up to a noise dependent threshold, and investigate the performance of other unsupervised learning algorithms in this setting.

Abstract: In this paper, we clarify the effect of noise on common spectrally
motivated algorithms such as Diffusion Maps (DM) for dimension
reduction. Empirically, these methods are much more robust to noise
than current work suggests. Specifically, existing consistency results
require that either the noise amplitude or dimensionality must vary
with the sample size $n$.  We provide new theoretical results
demonstrating that low-frequency eigenpairs reliably capture the
geometry of the underlying manifold under a constant noise level, up to a dimension independent threshold $O(r^{-2})$, where $r$ is the noise amplitude. Our results rely on a decomposition of the manifold Laplacian in the Sasaki
metric, a technique not used before in this area, to our knowledge. 
We experimentally validate our theoretical predictions. Additionally, we observe
similar robust behavior for other manifold learning algorithms which 
are not based on computing the Laplacian, namely LTSA and VAE.

The Noisy Laplacian: a Threshold Phenomenon for Non-Linear Dimension Reduction
Alex Kokot Octavian-Vla Murad
Marina Meila
Abstract
served. However, the theoretical understanding of manifold estimation in noise has proved to be slow in surrendering its secrets; even in the face of remarkable tours de force such as the ones we mention below, progress has been in small steps. The following seminal papers have both advanced the knowledge of what is possible and brought to light the informational limitations posed by the presence of noise for various statistical settings. In 4 5 6) it was shown that manifold reconstruction is possible, and (7) studied the minimax rate of covegence obtaining almost tight upper and lower bounds of n यीž for the Hausdorff error (where d is the manifold intrinsic dimension). However, these, as well as (8), consider reconstruction typically in ambient space R,
In this paper, we clarify the effect of noise on common spectrally motivated algorithms such as Diffusion Maps (DM) for dimension reduetion. Empirically, these methods are much more robust to noise than current work suggests. Specifically, existing consistency results require that either the noise amplitude or dimensionality must vary with the sample size n. We provide new theoretical re- sults demonstrating that low-frequency eigenpairs reliably capture the geometry of the underlying manifold under constant noise level, up to a di- mension independent threshold Or--2), where is the noise amplitude. Our results rely on a decomposition the manifold Laplacian in the Sasaki metric, a technique not used before in this area, to our knowledge. We experimentally vali- date our theoretical predictions. Additionally, we observe similar robust behavior for other mani- fold learning algorithms which are not based on computing the Laplacian, namely LTSA and VAE.
For estimating the Japlace-Beltrane operator, the state of knowledge is less advanced. We recall that the m principal eigenfunctions of AM provide an embedding of a manifold in m < dimensions, by the well known Diffusion Maps (DM) Laplacian Eigenmaps algorithm and its variants. (9) obtains consistency and rates for the problem of Laplacian estimation, albeit with the assumption that the noise ampli- tude decays to 0 with the sample size For non-vanishing noise, (0)) assume the noise is subgaussian and decaying to ( with n and D in every direction, but not in L2 norn
1. Introduction
In this paper, we revisit embedding algorithms such as Diffu- sion Maps (I12). providing a novel perspective how these methods allow for effective dimension reduction. A large literature has been developed to study non-linear dimension reduction under the so-called manifold hypothesis (3), where samples are assumed to be drawn frow low-dimensional manifold. Our goal is to show why these techniques remain effective, even in settings where this assumption is violated, with data having been contaminated with high- eigh--imensional noise.
Contributions Our paper studies the spectral convergence of the noisy manifold Laplacian to the noise-frea manifold Laplacian under realistic assumptions of fixed ambient di- mension D, and fixed noise amplitude r.
Under these conditions we firstly find that only the part of the manifold spectrum below the noise spectrum is re- coverable, with error proportional to the noise amplitude r. This leads to sharp threshold phenomenon the recov- ery of the spectrum of the noiseless manifold's Laplacian A M from (infinite) noisy data. The recovery threshold is ((1rr2) for fixed noise distribution (constant dimension and amplitude), and we discuss how this relates to noise dimensionality in Section 3.1 Eigenvalues and eigenvec- tors above the threshold are essentially irrecoverable, as the
That diffusion maps is robust to noise has been often ob-
'Department of Statistics, University of Washington, Seat- dee USA *Computer Science and Engineering, University of Washington, Seattle, USA. Correspondence Alex Kokot cakokot@uw.edu>.
'Similarly, 5 also rely on D being very large to obtain error bounds (for example n ~ 10 the second paper), hut with exponential sample sizes (in the inverse tolerance and d) they succeed to obtain errors that decrease with n.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

The Noisy Laplacian
entyyeete.Co
the induced Euclidean metric on RP. We assume that M is compact, with > 0. Without loss of generality we take 7 > 1 by appropriately rescaling our coordinates, and we assume our generative distribution j is supported on (.(M). We can identify the tubular neighborhood with tuples (x, e) E .M x Bx) each y E (MM can be uniquely identified by the nearest point zy E .M and the deviation from this point y - -y. More generally, such pairs (x, v) can be identified with elements of the normal bundle NM L..M N,M the normal space at x, via the exponential map exp(x, v). For a map ε,, we denote its pullback by x² and pushforward by πx.
Oeewettr Nelp
in (n Holy
M Eprnatee
Figure I: Random walk Laplacian eigenvectors overlaid on samples from the circle ("clean" data) and annulus ("noisy" data). The eigenfunctions of the circle exhibit typical spher- ical harmonic structure. On the annulus the harmonic eigen- function of the clean manifold is accurately preserved for the first non-trivial eigenvalue; the second in the display captures orthogonal variation due to noise, and the third has a scrambled (aniso+manifol)) signal.
We equip the normal bundle with a Riemannian metric, a positive definite bilinear form I(2,)) : T( NM x T Tiz.o) We will often express g as an inner-produce (,-),, suppressing the point-wise dependency. A metric on an oriented manifold determines unique volume form dptg.
Laplacian operators A denotes the haplace-Beltramm operator (Laplacian) (13), and Ay the weighted Laplacian A,= A + (V log duc, V-) (16) (we may also denote it Ap. with p the density function, again w.r.t the induced Fuclidean metric from RP)), with both operators implicitly taken with respect to the induced metric. For corresponding operators in the Sasaki metric (introduced below), we adorn them with ~-, i.c. Á. When referring to an operator with regard to a specific space, we may denote this with subscript, i.e. AM- We consider these operators their respective Neumann sobolev spaces, denoted (²( = H2(X, n4, (), for X the space of interest (M, (MMM), etc.). When referring to their spectral data, we order the eigenpairs (A,, oz) such that A S X for i S j. We often use functional notation to refer to the operator they correspond to, i.e. )x being the ith induced Laplacian eigenvalue. Denote Px(-) as the projection onto the eigenspaces with eigenvalue < X, or alternatively (- the span of the first K eigenfunctions.
geometry is dominated by the noise.
Secondly, in our approach, we leverage properties of the Sasaki metric (TI) which to our knowledge we are the first to do in this literature. This helps us elegantly disentangle the manifold and noise components of the data distribution, decomposing the Laplacian into horizontal operator along the manifold M and vertical operator normal to it.
Thirdly. we conduct experiments validating this thresh- old phenomenon and demonstrating the robustness of low- frequency cigenpairs to noise on real and synthetic datasets. Finally, we compare with two other manifold learning al- gorithms that do not rely on the Saplacian-Variattii Autoencoders (VAEs) 122 and Local Tangent Space Align- ment (LTSA) 13 and observe similar behavior.
2.1. The Sasaki Metric
2. Notation and Background in Manifold Geometry
Our presentation follows (17 Chapter 2.4).
Here we succintly introduce the Riemannian geometric con- cepts used throughout the paper; see (14) for an introduc- tion to Riemannian geometry, which formally describes the objects listed below. For an embedded, oriented d dimen- sional manifold M C TRD, define the tubular neighbor- hood of radius about M, (.M := {z E RD= By e M, | < r). We will assume M is at least 3 On oc- casion where our results apply to more generic topological structures, we refer to X' as bounded domain with smooth boundary.
2. 1.1. HORIZONTAL AND VERTICAL SPACES
To understand why the induced metric does not adequately capture the desired product structure enabled by the Sasaki metric, consider the annulus displayed in Figure 2 Notice that displacement orthogonally to the circle agrees between the two metrics; lengths and geodesics in one correspond exactly to the other. However, if we consider displacement in the tangent or horizontal direction, the same cannot be said. Visibly, the geodesics of the induced metric follow the euclidean straight lines when possible, and this is particu- larly problematic when we seek to identify the tangents and orthogonals across different points of this set. Ideally, we
The reach 7 of M is defined to be the largest r such that all T,(M) have a unique nearest member of M w.r.t.
2

---

The Noisy Laplacian
would like to identify each point in the tube with its nearest counterpart along the circle, and this idea extends to when we consider directional differentiation. If at one point the annulus we had an operator corresponding to orthogonal differentiation and we sought to replicate this at another point by slowly varying this operation across the domain (i.e. parallel transportation) then it would be desirable if at each point along the way the orthogonality to the sphere was maintained. Thus this requires the metric to adjust for the effect of curvature as our path moves closer and further from the inner-most radius, as well as along the manifold if it is not of constant curvature.
T
T,00
Figure 2: Visualization of the induced(left) and Sasaki(right) metrics on (S*). The grids represent orthogonal coordi- nates and the brown lines are geodesics in the respective metrics.
Fundamental to this problem is an appropriate identifica- tion of a "horizontal space", a subspace of the tangent at a generic point on the tube that corresponds the tangent of the underlying manifold. Precisely, we represent the tubular neighborhood with a neighborhood of the O sec- tion of the normal bundle N.M via the exponential map. Taking local coordinates (Iz, v), x E M, E NaM = RD-d we get a coordinate basis of the tangent space MM, 0/am..... 0/ ar 0/0m,,..... ".00....,,/0u-- As indicated above, it would not be appropriate equate the horizontal the seemingly obvious basis 0/Or,. We must make a selection dependent the curvature of M as well as the displacement at v. Let us compute how movement in the coordinate directions effects the orthogonal e when moving along the manifold. Take a curve " in M that is in- cident to x at t = 0 with tangent velocity a := Σ; a, /0xx Let u(t) be the section of N along Y that is the parallel translation of Thus u() corresponds to curve in N M, u(()= = (x1 (t)...,,, (t),), U1 (t), ..., (t)) and we can immediately compute à;(() = og In our coordinate chart, by construction we also have
2.1.2. METRIC DECOMPOSITION
The Sasaki metric is defined to be
(u, u.) = (T.U., T ud TT. + (K- K- "'),,,,,
orthogonalizing T(r,n) NM H(m.,)) + V(z,a), and inde- pendently preserving horizontal and vertical displacement (8).
For weighted Laplacians on TM(M), we will assume that the respective densities du (w.rt. the ambient measure) fac- tors along the horizontal and vertical spaces, du(x,,) v) dus.p(xz)g(v), identifying q with fixed function on the canonical fiber BP-d. In other words, as made precise in Lemma A. we can generate samples from μ by sam- pling the manifold, then adding orthogonal noise that only depends on the selected point via the direction of the orthog- onal. For example, X generated by sampling M supported on M then adding isotropic Gaussian noise in the direction of the orthogonal meets this requirement. This noise struc- ture is typical in the manifold learning literature (77 19). etc.). We further assume that this orthogonal noise has compact support equal to a ball of radius less than the reach.
0 = (V v)=' = + Σ (0),
j.k
= = + 2.k
r 3.
and thus (0) = - D j. where r are the Christoffel symbols (14) of the induced connection V on N.M. This leads us to a natural definition of the hor- izontal space as H(r,)) == {X : X = Σ, a,0/Oz; Ej Dj (.aav000000 exactly the kernel of the connection map K- (e,,) + N,M, (() KL (E))
2.2. The Sasaki Laplacian for T, (M(M)
The primary utility of the Sasaki metric is the spectral struc- ture it induces. Consider the noisy circle (annulus), which we equip with the product metric S x (a, b). we take the Neumann (insulated) boundary condition, then we see by a separation of variables argument that the Laplace-Beltrame Beltrami operator decomposes as = As + ((abb) =: As @ A,, where is the width bb-al. As r 0. one can compute that the minimal non-trivial eigenvalue of A, grows r with the consequence being that any eigenfunction with smaller eigenvalue must be constant orthogonally to the circle.
El Ei-d(E444 (Eatt + EyssaaTheesaa
As suggested earlier, we would like the orthogonal fibers in the Sasaki tube geometry to be isometric to those of the induced metric, Euclidean balls. This corresponds to the identification of the "vertical spaces" as the tangents to the orthogonal subspaces, spanned by 0/dv,, Vin,.). This space the kernel of n..
The above properties hold in general for the Sasaki metric of the tubular manifold (-MM), as shown in Proposition 2.1
3

---

+ Cr with C only depending on The Noisy Laplacian
below. Before state the proposition, we introduce the following technical artifice that will be useful throughout the paper.
3. Spectral Analysis of Noisy Manifold Laplacian
3.1. The Low Spectrum of the Noisy Manifold Laplacian
Rather than considering differential operators with differ- ent domains T, (M), for r E 1), we fix (M) as a reference space. Then we identify the Sobolev spaces (M)) with (M)) via f + f dr, where 0,(2, v) == exp(x, v//) (z, v/r) called rescaling map. In other words, study the spectra of the contracted operator Aur== == Ao..po it suffices to study its conjugate Apr = o.-11 - p, the weighted Laplacian in the metric S.. = ss,, which has the same spectrum
As saw in the case of the Sasaki metric, the low-order spectrum of the Laplacian bears close resemblance to that of the underlying manifold. We extend these results to the induced metric Laplacian via a perturbation analysis.
Theorem 3.1 (Spectral perturbation for small cigenvalues). Let A be the Laplacian on T, (,(M), r < 1 < т, with mea- sure pi in the weighted case take μu factoring w.r.t horizontal and vertical spaces, p,, := o otherwise let μ., be the am- bient measure. Let 4M be the corresponding operator on M, in the weighted case with respect to the density p. Let A (A( < X /r2.
We verify properties of horizontal- vertical decomposition of the weighted Laplacian analogous to the unweighted case previously presented in (88 20 121.
There exists constant C depending on M such that
Lemma 2.1. Let M,T,(M) μ on (MMM) factorizing w.r.f the horizontal and vertical spaces, and Laplacians A M. Aur as defined above. Then the following hold.
A - )x( S 8AaCr.
Further, for X < 1/22, there exists constant Cx such that
1. Ap.r has discrete spectrum with finite multiplicity eigenvalues, and decomposes as
|| Px(AM) - PA(A)LI 16CxCr,
in particular, for any (m( S X simple, ΦR (Ap,r) (x(Arr)) unit, there exists C' depending on M such that
Aprr AH.p + Av.a
for some operators D. Ava such that (f) π AM. J. Av. (z),))
|| (o(lAM) Oi (1(()))))))))) S &C'AR(AM)),
(fo.,)(fl,;))00) + (Vlogg, f (z)())).
Corollary 3.2. Let P(μ)) denote the Poincaré constant of a distribution p. With the above notation, the Poincaré constant P(pr))=P M.p.
2. The operators &p.rs Av.. and A are non-negative and self-adjoint.
3. Ag. AH. and Av.g commute pairwise; hence, there is a common orthonormal basis )e C (M),, psa) of smooth eigenfunctions such that
In other words, in the low-frequency regime, the Neumann eigenfunctions of A (M) agree up to small error with con- stant orthogonal extension of the eigenfunctions of the base manifold, f π. Thus, procedures like diffusion maps, when truncated to a small basis, perform dimension reduction by implicitly denoising the data. the high frequency regime, such recovery is hindered not only by the magnitude of the perturbation, which is proportionate eigenvalue, but also by the presence of non-trivial "noise" eigenfunctions. In fact, as the noise dimension D - d is typ- ically much larger than the manifold d, even in the Sasaki metric the number of eigenfunctions with no orthogonal dependence negligible the limit. This, along with the shrinking spectral gaps (of the resolvent) and, as previously noted, increasing perturbation size, lead to unrecoverable manifold data in the continuum.
A..ō = X
x1102 Di.
Av. = XY 0i,
1
: (>
XY)d..
p2
These eigenfunctions and spectra X XY are invariant for 0 <r<T
the corresponding
4. For (A I /r3, ci(Apr)) = dc(Ap) o and >x = >.)A)).
Proposition 2.1 states that the spectrum and eigenfunctions of the Sasaki Laplacian of the noisy manifold T, (MM re- cover the noise free coresponding quantities of AM below the noise dependent threshold r - This supports the intuition that the principal cigenspaces of manifold Lapla- cian are robust to noise, and, moreover, that the robustness extends to larger eigenvalues when the noise amplitude r decreases.
We now discuss byproducts of our result. As we see in Corollary 3.2 this spectral approximation translates to guar- antees on mixing times (22) and geometric inequalities (23) that closely relate the concentrated tube to the underlying

---

The Noisy Laplacian
manifold. Our bound also suggests a similar consistency for noise with increasing dimension as verified for empir- ical Laplacian estimation in (10). In typical examples X increases with the dimensionality of the noise, thus yielding the result if coupled with a verification that the correspond- ing perturbation magnitude also decreases. While we see this empirically for orthogonally uniform noise in Figures 5 and [nd we conjecture that such consistency can be verified under generic log-concavity assumption.
900
Sast
Noise threshuld
305
2
202-
Our analysis is geared toward the study of very regular noise structures, and this is more restrictive than one might expect for real data. However, in practice, these same spectral phe- nomena are observed in far more irregular sampling settings so long as the measure is sufficiently concentrated about a low-dimensional structure. We sketch how our approach can be extended to deliver theoretical guarantees in such cases. For μu with smoothly varying tube widtts/orthogonal densities, one can construct natural diffeomorphism t/ such that the support of &. is a tube manifold, and vh, factors w.r.t horizontal and vertical spaces. This amounts to stretching or contracting the measure smoothly to achieve the desired structure. This an isometry if we equip the resulting tube with the metric (w-")""g, for y the original Euclidean metric. Thus, the results of Appendix [3.1 are immediately applicable if we can verify that under rescaling this metric sufficiently approximates the Sasaki. We expect this to be similar to the verification for the induced metric, but we leave this to future work. In the following section we prove generic spectral growth bounds applicable to irregular domains.
302
10
20
30
40
25
Index
Figure 3: Spectral growth of the circle and annulus from Figure D in the induced and Sasaki metrics, eigenvalues empirically estimated.
As shown in Figure below this threshold, the tubular neighborhood has eigenvalue growth reflecting that of the base manifold. Above the threshold, the growth is slower, that is, the counting function N (A) is larger, reflecting its asymptotic behavior as an extrinsic dimensional domain
in R The relationship between Laplacian spectra and coverings is classical, dating back to the original proof of the Weyl Law (25). Several recent papers (26) (7 have bounded the spectral growth of the Neumann Laplacian from this perspective. Leveraging their approaches, we precisely quantify the low-order spectral growth, characterizing it in terms of packings. Note that, in the limit, the typical Weyl law verifies the extrinsic dimensional dependence X 2//D
3.2. Multi-scale Spectral Growth and a Weyl law
As a retrospective, we note that aspects of the spectral phenomenon presented in Section 3.] are present in more general settings. Tubular neighborhoods are particu- lar example of multi-scale distributions, distributions that, in an appropriate sense, have dimension that changes de- pending on the scale which one localizes at. This is made precise via the packing number (T, Pack(T,(MM) e, Il lloo), the maximum number of disjoint cubes with side length and center in T.(M). Packing and the related covering number appear ubiquitously in statis- tical learning when describing the complexity of space, and have been tied to convergence rates of other geometric quantities such as the Wasserstein distance (44).
Theorem 3.3. Let X be bounded domain with smooth boundary, and define
C(k,s) = sup Pack (Bx (Bx k)), xEX
R(s) = inf ps (B((zE)) E))
suP p ((B(z,E))
Then,
N(C(A, 3)
If. in addition, X is convex or has empty boundary, then there exists C' depending on X such that
For e relatively large compared to r, (T, grows at the intrinsic rate -d but as dives below the noise threshold we get the extrinsic -D Not coincidentally, this is likewise seen in the growth rate of the spectra above and below X /r2, measured by the counting function
Pack N(C'E
For our tubular neighborhood model T, (MM, the first of these inequalities implies that eigenvalue frequency below noise level reflects the base manifold.
Corollary 3.4 (Local Weyl law for ATAM)). Let (T.(M) be defined as in the previous sections. Then, for & > 2r.
N(A)= == x(Ax)xxx) S AH--
5

---

The Noisy Laplacian
there exists a constant C > 0 depending only on M, such that C(4,,)e- S Aos-e.
4.2. Validation of Theoretical Results
In this section we empirically validate the predictions of Theorem [.1] For this purpose, we estimate the Laplace op- erators AM and (r-(M) and their spectral decomposition from data using the renormalized Diffusion Maps Lapla- cian ( We do so for all manifolds described in Section 4.1 and for many tubular neighborhood radií r E (0, r) and dimensions of the normal space dn = D - d.
In the results above, we leave many of the bounds expressed in full detail, even though many of the quantities could be collapsed down to a constant. For example, C(4, e) is simply the maximal number of e cubes that can be packed into a 4a X' cube. That this is no larger than 4 is immediate, however it is much smaller (=v 4" for the tube) for not too small, which is frequently the case of interest. Similarly, R(e) tends to for large and 1/2 as E + O. with a global bound depending on how curved the boundary of the domain is.
First, we use the estimated eigenpairs confirm the robust- ness to noise (hoth d,, and r) of the low-frequency eigen- pairs of AT,(M) below the noise threshold A/4 We do this quantitatively by verifying that the error between the low-spectrum eigenspaces (represented by their projectors) and their noiseless counterparts increases linearly with r. Furthermore, we notice a mild decrease in error as D gets larger, as argued in (I0). Qualitatively, we observe that low-frequency >₂ (M)) and &; (A(A))(M)) remain stable as dh is varied and as long as >r (A(),((M)
That the tube is multi-scale also plays essential role in the estimation of its spectral data. At face value, this problem suffers from the curse of dimensionality, with con- vergence rates depending exponentially on the ambient di- mension D. However, the approximation quality of Dif- fusion Maps is proportionate to the Woo distance between the empirical distribution μnn and μ (9). For lt supported on (M), simple application of the triangle inequal- ity yields W (Hm, O oo (T+ (T nula) + r). Thus, achieving estimation error at the order of the bias is an intrinsic dimensional problem.
Second, we show that, as the theory suggests, eigenvectors XY with X, (A(A)((M) > A/ are corrupted by noise, the noise threshold acting as a delimiter between the noiseless and the noisy eigenpairs. Quantitatively, we verify this prediction by computing the empirical correlations between o (AT,, (MO) and Φه (Am) which suffer sharp decrease for eigenvectors above the noise threshold, behavior that is independent of sample size. Qualitatively, we observe that the values of >₂ (x(A),,(M) are perturbed as they approach or go above AV + and that the corresponding eigenvectors are no longer correlated with the coordinate space of M.
4. Experiments
4.1. Data
We experimentally verify the extent to which the approx- imation in Theorem 3.1 holds for both synthetic and real datasets. Here we briefly describe the data used in our ex- periments, while more details can be found in Appendix D
The experiments above are visually depicted in Figure 4 and elaborated upon in the Appendix
5. Other Manifold Learning Algorithms
Although our main theoretical results pertain only to the Laplace operator, we observe the same behavior outlined in Theorem 3.1 and verified in our experiments for VAE (1) and LTSA (13), two manifold learning algorithms not based on Laplacian decomposition.
For our synthetic experiments we sample data from the following manifolds: Sd the S-Shape, and the Bottle (a more complicated manifold described in Figure ? to which we add noise uniformly distributed on ball of radius r in the normal space to the manifold.
Synthetic Data:
As opposed to DM, we have no natural way to evaluate whether a VAE latent coordinate LTSA embedding di- mension &e is low or high frequency. For this purpose we use the regression procedure outlined in Section E.2 Briefly, for the synthetic data we know the noise/normal space coor- dinates that generated each data point. Using these as input, we fit polynomial regression models that attempt to fit the Oi 's as targets. If the model is able to predict the embed- ding coordinates from the noise coordinates, we deem this embedding coordinate to be "hihh frequency' as it encodes noise information.
Real Data: For our real data experiments we use Molecular Dynamic Simulations (MDS) datasets consisting of atomic configurations from three molecules: Toluene(Tol). Malon- aldehyde(Mal), and Ethanol(Eth) from (28). These simula- tions require massive compute power, are extremely precise, and generate atomic configurations that exhibit non-linear, multiscale, non-i.i.d. noise, as well as complex topology and geometry, often lying near low-dimensional manifolds (29). We perform SVD to reduce the ambient dimension to D = 50 and add noise uniformly distributed on a ball of radius r in the ambient space.
6

---

The Noisy Laplacian
First, we observe that VAEs will learn set of embedding coordinates @i that are stable w.r.t. to both and dn and which are indispensable for reconstruction. However, if the latent space has more capacity than that, then the VAEs will use the extra coordinates to encode noise. Second, the em- beddings computed by LTSA, a classical manifold learning algorithm that does not rely on Laplacian estimation, behave similarly the cigenvectors di (AT,(M) we estimated in Section 4.2 using Diffusion Maps.
n- L0k, Nody
n- 606, heldy
nn LON, Clean
n COK, Ceson
100
62
Our results are summarized in Figure S and expanded in Appendix F where we fully describe the models and hyper- parameters used.
8-
6. Discussion and Related Work
(a) Hcatmaps of the empirical correlations between & (Ar, (rows) and Φ (Am) (columns) on S², Notice the sharp decrcase in correlation once X: (()))) > XY /r².
Embedding manifold data in low dimensions by eigenvec- tors has been one of the most successful directions in non- linear dimension reduction (33 BO both practically and from the point of view of the theoretical understanding it allows. Among these algorithms, the DM algorithm of ( using the eigenvectors of (a matrix estimating) the Laplace- Beltrami operator AM of the manifold has been a central subject of study, but the practical success of spectral meth- ods is due to their robustness on real data that rarely satisfy the manifold hypothesis.
K=2 Change Radiss
K=3: Change in Dimersoon
0.26
-3.0
Frbbrtee home
-230
0.20
4.00
3.36
4.50
1803
20000
30090
40000
30093
50000
In this paper, we provide a new perspective on why, and to what extent, this robustness is to be expected. We study the relation between the ideal AM and the Laplace-Beltrann operator A of (MM), noisy version of M.
bpin
(b) Error between the projectors onto the K-th eigenspace of AM (computed analytically) and AT.(M) (estimated) on Notice the linear increase in error as increases (left) and the mild decrease in error as D increases (right).
We show (in Theorem 3.1 that indeed the eigendecompo- sition of the Neumann Laplacian in the perturbed domain differs from that of the intrinsic manifold M by mild error in the low-frequency regime, thus corroborating the traditional wisdom that eigenfunctions associated to small eigenvalues are stable. But our results in Sections [3. and 2.2 also strongly suggest that the recovery is limited the part of the AM spectrum below a threshold (r))), rep- resenting the first non-trivial noise eigenvalue, after which recovery becomes impossible, due to the high density of the noise spectrum above this threshold.
Nosso
rovel
Y
2
V
V
V
A
Furthermore, in Section 3.2 we present more general results and intuitions on the spectral density for a larger class of geometric objects in noise, as we relate eigenvalue growth rate to packing numbers. These results allow for general noise structures, tying into our sketch of how our noise assumptions can be loosened presented in Section 3.1
(c) Qualitative validation of our results on two manifolds: the Toluene molecule(left) and the Bottle(right) with d.. = 3. In the top plots, each path corresponds to (m()),(M)) which are almost constant until >Y (the black line) approaches them. In the bottom plots, we color the coordinate spaces of the manifolds by low-frequency (top) and high-frequency (bottom) di (AT,(M))). Notice the stability of the former as r increases and the sudden corruption of the latter once the noise threshold is passed.
The study of manifold estimation in noise is more than a decade old (3) 4 5 10: 7 3I), and we adopt the standard assumptions of "tubular" i.i.d. noise. But in contrast with previous works that have studied the impact of noise in re- lated geometric (IO) and kernel based (3I) algorithms, our
Figure 4: Summary of the experiments validating our theo- retical results
7

---

The Noisy Laplacian
Nois loval
Note: dimeniionnnooomm
Nose levell
Note Omenson d.
(a) Results for VAFs trained on S for d. = 16 and r in- creasing from left to right. Each panel corresponds to one
(b) Results for LTSA for the S-Shape. Left: Stability w.n. to of the low-frequency embeddings and the threshold effect exhibited by the high- frequency Φi as they become drowned by noise. We color the coordinate space of the manifold by di as increases from left to right. In the next panel, use a polynomial regression model to predict each d, from the known normal space/noise coordinates. When we are able to do so, we can conclude that the corresponding di represents encodes. Right: Stability of Φ1 w.r.t to varying and da E (16, 24, 3to(p))) vs the lack thereof of the higher- @1o(bottom)
de and displays from top to bottom: the coordinate space of S colored by di, the reconstruction of the data without dh. and the prediction of each de from normal space/noise coor- dinates by a polynomial regression model. 21.2.3 are stable w.r.t. to noise, indispensable for reconstruction, and cannot be predicted from noise. Conversely, d4 is not correlated with the coordinate space of the manifold, not important for reconstruction, and easy to predict from noise coordinates.
Figure 5: Summary of results for other manifold learning algorithms.
present work does not require the amplitude and dimension- ality of the noise to change with the sample size. Further, this analysis is agnostic to the particular choice of estimator
recovery not possible, based on the density of noise eigen- values that far exceeds the density of the AM eigenvalues in the spectrum. We leave this for upcoming paper.
(e.g. (I 10)), as we show that the continuum Laplace- Beltrami operator itself has desirable robustness properties with regard to its principal eigenvalues and eigenfunctions. To handle the fixed noise assumption, we introduce new techniques, based on the elegant Sasaki metric concept (T].
Other benefits from our results are as follows. First, practi- cally, by verifying this result in the continuum, we provide novel asymptotic guarantees for (biased) spectral recovery even in the presence of noise. The second benefit is a better understanding of how spectral algorithms like DM provide meaningful dimension reduction. In the noiseless case, it is geometric result that infinite dimensional eigenbases re- cover the geometry of the domain (34; (35). hence seemingly more eigenvectors would recover more information. How- ever, here we show that with noise, using more eigenvectors will overfit the data by recovering the uninformative geome- try of the noise. It is exactly the low dimensional truncated eigenvector bases commonly seen in practice K 36
Our proof technique resembles those employed for Lapla- cian spectral estimation (2).. Central to both arguments is realization of the near isometry between two spaces, in our case the induced and Sasaki metrics, while former works have emphasized comparisons between empirical and population distributions. Studying the effects of noise on the Laplacian and related heat operators has rich literature in Differential Geometry. We utilize key techniques from (20 33).
that provide the highest resolution of the underlying man- ifold. This leads to an interesting tension when compared to learning procedures in supervised settings that rely on infinite Laplacian bases (37), particularly when the signal only depends on the manifold component. In future work, we aim to study this problem in more detail, with the goal of reducing this inefficiency.
While we do not currently have a matching lower bound, we anticipate that the bias proportionate to r is the optimal possible, particularly for less regular noise structures. In the tubular setting, it is possible to exploit our strict noise structure to learn M itself (7), and this can be employed to sharpen the estimates of the intrinsic spectrum and estimate the cut-off for reliable estimation. Note that since our results are in population, if they are tight, no procedure will be able to recover the Laplacian cigenfunctions at a better accuracy. Beyond the scope of this submission, we have considered the recoverability of the eigenfunctions and spectrum above the 22) threshold. We find strong indications that this
What do our results say about the robustness of Diffusion- Maps algorithm in practice? First, note that the error bound (rr) does imply robust, if inexact recovery in real data. In particular, in typical examples as the noise threshold grows proportionately to the noise dimension, our results allow for noise amplitudes of rryD D d which can be quite large.
8

---

The Noisy Laplacian
Second, in real scenarios, noise is often not full D-d dimen- sional, but has multi-scale structure, where the large noise is only in D' < D dimensions. Our results do not depend on D, hence they (approximately) cover this case too. Third, if the eigengaps A (Am) - A (A,) M are sufficiently small, it is possible that the respective ^x(A), ( change or- der, while the combined eigenspace remains approximately the same. Thus, we were to use the eigenvectors of A for obtaining an embedding, the selection of m eigenvectors (m > d being the embedding dimension) may vary between noise level and noise instantiations on the same underlying manifold M.
manifold learning algorithm, this close correspondence is not surprising. VAE the other hand bears direct rela- tionship to DM, however we observe the same qualitative behavior. Fitting our generative distribution with a low- capacity, low-dimensional embedding, we arrive at a par- titioning of the coordinates into manifold components and noise.
A Acknowledgments
This research was carried out mainly in the Statistics De- partment at University of Washington. A.K. was partially supported by by the Department of Defense (DoD) through the National Defense Science & Engineering Graduate (ND- SEG) Fellowship Program. M.M. gratefully acknowledges the hospitality of the DataShape Group INRIA Saclay and of the Institute for Mathematical and Statistical Innovation (IMSI) through the long program on "Data- Material Informatics".
In our theorems, we do not assume that the sampling is uniform; but we make the strong assumption that the sam- pling distribution z factors w.r.t. the horizontal and vertical spaces, in other words, that the noise is orthogonal, has tubular support, and is independent of x. If the noise is not isotropic, or if the noise distribution is not uniform (but still independent on æ), it is easy to see that Theorem 3.1 will continue to hold, albeit with a different threshold of X r where X is the lowest eigenvalue of the noise distribution, as in Section 2.T If the noise becomes highly anisotropic. in other words, if the density of noise eigenvalue decreases (for example, if A has multiplicity 1), then some eigenpairs beyond the noise threshold may be recoverable as well.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Empirically, DM and other spectral algorithms are robust also when the noise varies along the manifold, as can be seen e.g. in the MDS experiments. While our results do not cover this case, we believe that they can be extended, by making the assumption that the noise is approximately i..d. In such case, an additional estimation error will be incurred due to the difference between tubular noise and the actual noise. Furthermore, in future work, we believe we can extend our results to slowly varying departures from tubular noise.
References
[1] R. R. Coifman and S. Lafon, "Diffusion maps." Ap- plied and Computational Harmonic Analysis, vol. 30, no. 1, pp. 5-30, 2006.
[2] M. Belkin and P. Niyogi, "Laplacian eigenmaps for di- mensionality reduction and data representation." Neu- ral computation, vol. 15, no. 6, pp. 1373-1396, 2003.
[3] C. Fefferman, S. Mitter, and H. Narayanan, "Testing the manifold hypothesis," J. Amer. Math. Soc., vol. 29, pp. 983-1049, Feb. 2016.
Our experiments in Sections 4 confirm that the theoretical results carry over to finite samples, where observe eigen- function perturbations on the order of the tube width, as well as perturbation reduction with increased noise dimension. We see this repeatedly in qualitative experiments, where sufficient sample noise and spectrum depth leads to loss of eigenfunction signal. Our results can be combined with those of known empirical estimators of Laplacian eigen- data (32)88) B8), however additional work is needed to confirm these results in the context of non-trivial boundary. For appropriate bandwidth selection for these estimators, the method of (39) can be employed for estimation of the intrin- sic dimension, however as indicated by our spectral analysis, data adaptive procedures such as (40) adequately adjust to multi-scale tubular data.
[4] C. Fefferman, S. Ivanov, M. Lassas, and H. Narayanan, "Reconstruction of riemannian manifold from noisy intrinsic distances," SIAM Journal on Mathematics of Data Science, vol. 2, no. 3, pp- 770-808, 2020.
[5] C. Fefferman, S. Ivanov, M. Lassas, and H. Narayanan, "Fitting manifold to data in the presence of large noise," " 2023.
[6] C. Fefferman, S. Ivanov, M. Lassas, and H. Narayanan, "Fitting a manifold of large reach to noisy data," Jour- nal of Topology and Analysis, 2023. Publisher Copy- right: c 2023 World Scientifie Publishing Company.
The experiments in Section 5 with LTSA and VAE demon-
[7] C. R. Genovese, M. Perone-Pacifinn I. Verdinelli, and L.. A. Wasserman, "Minimax manifold estima-
strate similar phenomenon. As LTSA is principally
9

---

The Noisy Laplacian
tion," Journal of Machine Learning Research, vol. 13, pp. 1263-1291, 2012.
[21] R. Hermann, "A sufficient condition that mapping of riemannian manifolds be fibre bundle," Proceedings of the American Mathematical Society, vol. 11, no. 2, 1960.
[8] M. Hein and M. Maier, "Manifold denoising," in Advances in Neural Information Processing Systems (B. Schölkopf, J. Platt, and T. Hoffman, eds.), vol. 19,
pp.
[22] L.
F, Bach, T. Lelièvre, A. Rudi, and G. Stoltz. "Statistical estimation of the poincaré con- stant and application to sampling multimodal distribu- tions," in International Conference on Artificial Intel- ligence and Statistics, pp. 2753 2763, PMLR, 2020.
MIT Press, 2006.
[9] N. García Trillos, M. Gerlach, M. Hein, and D. Slepčev, "Error estimates for spectral convergence of the graph laplacian on random geometric graphs toward the laplace- beltrami operator," Foundations of Computational Mathematics, vol. 20, no. 4, pp. 827- 887, 2020.
[23] D. Bakry, I. Gentil, M. Ledoux, et al., Analysis and geometry of Markov diffusion operators, vol. 103. Springer, 2014.
[10] B. Landa and X. Cheng, "Robust inference of manifold density and geometry by doubly stochastic scaling," SIAM Journal on Mathematics of Data Science, vol. 5,
[24] J. Weed and F. Bach, "Sharp asymptotic and finite- sample rates of convergence of empirical measures in wasserstein distance," Bernoulli, vol. 25, no. 4A, pp. 2620-2648, 2019.
no. 3, pp. 589-614, 2023.
[11] S. Sasaki, "On the differential geometry of tangent bundles of riewannian manifolds," " Tohoku Mathemati- cal Journal, Second Series, vol. 10, no. 3. pp. 1ep.338-355 1958.
[25] H. Weyl, "Das asymptotische verteilungsgeestzz der eigenschwingungen eines beliebig gestalteten elastis- chen körpers." " Rendiconti del Circolo Matematico di Palermo (1884- 1940), vol. 39, no. 1, pp. 1-49, 1915.
[12] D. Kingma and M. Welling, "Auto-encoding varia- tional bayes." " 2022.
[26] B. Colbois and D. Maerten, "Eigenvalues estimate for the neumann problem of bounded domain," Journal of Geometric Analysis, vol. 18, pp. 1022-1033 2008.
[13] Z. Zhang and Zha, "Principal manifolds and nonlin- ear dimensionality reduction via tangent space align- ment," SIAM J. Scientific Computing, vol. 26, no. 1, pp. 313-338, 2004.
[27] A. Hassannezhad, G. Kokarev, and I. Polterovich, "Eigenvalue inequalities on riemannian manifolds with lower ricci curvature bound," " Journal of Spectral Theory, vol. 6, no. 4, pp. 807-835, 2016.
[14] J. M. Lee, Introduction Riemannian manifolds, vol. 2. Springer, 2018
[15] S. Rosenberg, The Laplacian on a Riemannian mani- fold: an introduction to analysis on manifolds. No. 31, Cambridge University Press, 1997.
[28] S. Chmiela, A. Tkatchenko, H. Sauceda, I. Poltavsky, K. T. Schütt, and K.-R. Müller, "Machine learning of accurate energy-conserving molecular force fields," Science Advances, March 2017.
[16] A. Grigor' "Heat kernels on weighted manifolds and applications," Cont. Math, vol. 398, no. 2006, pp. 93-191, 2006.
[29] M. A. Rohrdanz, W. Zheng, M. Maggioni, and C. Clementi, "Determination of reaction coordinates via locally scaled diffusion map." The Journal of chem- ical physics, vol. 1 134, no. 12, 2011.
[17] T. Sakai, Riemannian geometry, vol. 149. American Mathematical Soc., 1996.
[30] J. B. Tenenbaum, V. de Silva, and J. C. Langford, "A global geometric framework for nonlinear dimension- ality reduction," Science, vol. 290, no. 5500, pp. 2319- 2323, 2000.
[18] L. B. Bergery and J.-P. Bourguignon, "Laplacians and riemannian submersions with totally geodesic fibres." Illinois Journal of Mathematics, vol. 26, no. 2, pp. 181-
200, 1982.
[19] E. Aamari and C. Levrard, "Nonasymptotic rates for manifold, tangent space and curvature estimation," The
[31] N. E. Karoui, "On information plus noise kernel ran- dom matrices," The Annals of Statistics, vol. 38, no. 5, pp. 3191-3216, 2010.
Annals of Statistics, vol. 47, no. 1, pp. 177 - -204, 2019.
[20] V. Nobis and O. Wittich, "A convergence result for dirichlet semigroups on tubular neighbourhoods and the marginals of conditional brownian motion," arXiv preprint arXiv: 1908. 01335, 2019.
[32] J. Calder and N. García Trillos, "Improved spectral convergence rates for graph laplacians on c-graphs and k-nn graphs," Applied and Computational Harmonic Analysis, vol. 60, pp. 123-175, 2022.
10

---

The Noisy Laplacian
[33] O. Post, Spectral analysis on graph-like spaces, vol. 2039. Springer Science & Business Media, 2012.
[34] Bérard, G. Besson, and S. Gallot, "Embedding Rie- mannian manifolds by their heat kernel," Geometric Functional Analysis, vol.
pp. 373-398, 1994.
[35] J. W. Portegies, "Embeddings of Riemannian mani- folds with heat kernels and eigenfunctions," Commu- nications on Pure and Applied Mathematics, vol. 69, no. pp. 478-518, 2016.
[36] Y.-C. Chen and M. Meilä, "Selecting the indepen- dent coordinates of manifolds with large aspect ra- tios," in Advances in Neural Information Processing Systems 32 (H. Wallach, H. Larochelle, A. Beygelz- imer, F. d' Alché-Buc, E. Fox, and R. Garnett, eds.), pp. 1086-00000000 1095, Curran Associates, Inc., 2019.
[37] A. Green, S. Balakrishnan, and R. Tibshirani, "Min- imax optimal regression over sobolev spaces via lapla- cian eigenmaps on neighbourhood graphs," Informa- tion and Inference: A Journal of the IMA, vol. 12, no. 3, pp. 1423-2502, 2023.
[38] D. Dunson, H.-T. Wu, and N. Wu, "Spectral conver- gence of graph laplacian and heat kernel reconstruction in 1s0 from random samples," Applied and Computa- lional Harmonic Analysis, vol. 55, pp. 282-336, 2021.
[39] A. V. Little, J. Lee, Y.-.. Jung, and M. Maggioni, "Estimation of intrinsic dimensionality of samples from noisy low-dimensional manifolds in high dimensions with multiscale svd," in 2009 IEEE/SP 15th Workshop on Statistical Signal Processing, pp. 85-88, IEEE, 2009.
[40] D. Garreau, W. Jitkrittuum, and M. Kanagawa, "Large sample analysis of the median heuristic," arXiv preprint arXiv:1707.07269 2017.
[41] D. Joncas, M. Meila, and McQueen, "Improved graph laplacian via geometric self-consistency," Ad- vances in Neural Information Processing Systems, vol. 30, 2017.
[42] Ba, J. R. Kiros, and G. Hinton, *Layer normal- ization," arXiv preprint UrXiv:1607.064555 2016.
[43] D. Hendrycks and K. Gimpel, "Gaussian error linear units (gelus)," arXiv preprint 1xXi::1666008111 2016.
[44] D. P. Kingma and J. Ba, "Adam: A method for stochas- tic optimization," 2017.

---

The Noisy Laplacian
Appendix / supplemental material
A. Extended Background
This section seeks to clarify basic properties of the Sasaki metric and Laplacian 11
Figure 6: curves on the annulus displayed in the Sasaki metric (left) compared the induced (right).
Example and intuition As motivation, consider circle with noise, an annulus, with inner-radius 0.5 and outer radius 1.5. A natural parameterization for this surface is (0,r) E IR 18/2mZ x (0.5, 1.5), the angular and radial coordinates. With this representation, a simple metric structure is the product metric,
/ |0: 02ll2/2Hz + (r1 - r2)2.
Of course, this structure fails account for the curvature of the circle, as demonstrated in Figure 2 For example, in the Euclidean geometry, two points on the inner-most circle are comparatively much closer than those on the outer-most, while the Sasaki metric returns the same value in both instances. However, if these radii are close together then these values will only differ negligibly (under an appropriate scaling), and the Sasaki geometry recovers the ambient up to small perturbation.
Measure factorization When considering manifolds equipped with a measure we characterize below the appropriate densities for our results are applicable.
Lemma A.1. A distribution p. supported on (M(M) factors along horizontal and vertical spaces and only if X is equal in distribution to M + EM where M is sampled with density on M and EM is supported on the orthogonal to M, such that (1t). Fas d Frr,, for "/s the flow of a basic vector field.
Proof. Let B, be the ball of radius r in D-d, By construction, T, (MM equipped with the Sasaki metric locally isometric the product structure M B,. Indeed, we can follow an argument in local coordinates seen in 18 Theorem 1.5). We take bundle chart in TNM with local coordinates (2r, v, E, n). Due the decomposition T(r,v) N 1 ((..)) @ V(z,e). adopt local frame ......, 6a, .,,..., -d such that the d; span the horizontal subspace, and the th; the vertical. As these subspaces are orthogonal, we can wlog adapt our coordinate system so that (a,, v) are such that 0/Ox; = Φ,, 0/Ov; the and thus our metric is the product metric on X x V. The left factor is isometric to a domain in M as the Sasaki metric Riemannian submersion, and the right factor is isometric to B, by (18] Proposition 5.2). Classical computations (17 Section 2.4) yield that such coordinates can be constructed about m .M via the exponential map TNM. (z. - exp (ar + v), Hm,o M, E Vm,o N, x, localized appropriately.
Now, let us assume first that the normal bundle of M is trivial that the isometry above was global. In this case, the assumption that y factors w.r.t horizontal and vertical spaces can be expressed equivalently μ being a product measure on M x B, by the above isometry. In this case the equivalence is trival as flows of basic vector fields leave B, invariant.
In general, as the flow of % from any initial point m E M is a compact path, we can cover it by a finite collection of bundle charts, for each of which the claim is verified. Hence, by the compatibility of these charts, the claim holds across the whole path.
12

---

The Noisy Laplacian
B. Spectral Analysis
B.1. General Properties of the Sasaki Metric. Proof of Proposition 2.1
The proof of Proposition 2.1 consists series of steps, each in supporting statements proved separately. See Scction for relevant defniition//assumpiinn...
Lemma B.1. Let V(,,e), then
KK-,uK-VII VV,,K-Vf((,,))... (K+u, V
For M.M,
| (=-1(0) (ū,
Vü, Ss dy = (u, [ Jx-1(0) f f
where we denote by the unique element of H(s,)) such that πT u (the horizontal lift).
Proof. The second is an immediate consequence of 18 Proposition 3.14). For the first, by definition, u(f) = (u, Vf = (K-u, K-Vf))
0f and the identification is immediate. Now, u(f) Ei u4 dvc
Lemma B.2. Apr has discrete spectrum with finite multiplicity eigenvalues, and decomposes
Aprr = A.t + Ava
Proof. It follows from 20 Section 2.1) that
Åp.r -i, An + _ Av oir (Vlgd((oo)))) V.)sa
We first verify that
of (V log d(o.)()).)) V.)sao, (Vlogp, n. V.M + Vogg, K V-)
change of variables yields d(ar.u)) (du)) (o,,) (o).). hence
(V d(ar,,)) V-)sa = lVlog p. n. V.MMM + (Vlogo K K-V
where the final equality follows from p, being horizontal/verttcal respectively, and we identify them with the corresponding functions on M, BO0, 1). Noting that differentiation commutes with the pullback, we see
(V d(gd(or)))) V-)sao, (V log D, m. Vo (V (Vlogo,g, K Vo..)NM
(o, Vog n. T. TM V K- V
V logp, T. V.M +
logg, K V-)NM.
where the last incquality follows from the Sasaki metric being the canonical variation relative to π (18). The final composition with Ty,, maps the above inner-produce (function) from T, (M) to Ti (M) as desired.
We now verify that
Av. Av + (V Io l, V-)),, ΔHр AH + (V logp, V.)
have the desired properties. From
18 Definition 1.2), we have Ar (f) A Afo.n((l.,)(0)) hence by Lemma B.1
(v.(f)(zz = AB (()) (V log g. V ((m)())),
i.e. the weighted Laplacian the ball. For the horizontal operator, the proposition similarly follows from Proposition B. as (x-1(0) AnJ dg A. (fa- f dg) by (88 3.9).
13

---

The Noisy Laplacian
Lemma B.3. The operators Å p.r. V and H. are non-negative and self-adjoint.
Proof. Integration by parts combined with the Neumann boundary condition yields
K f gAvaady / g Vf)du / SAvagdu
/ AAH.pgdy= = - (T.V sAnzgdn.
Lemma B.4. Ap.ro D..p. and Dv. commute pairwise, thus there is a common orthonormal basis {0i]i= (M of smooth eigenfunctions such that
DHPR: No Av.0: No. Aproi (2." 1 No) =: Aerdi.
-
(1)
Note that these eigenfunctions and spectra X X are invariant for <T<TM
Proof. oog n. V.)TM. (V logoo; K V-) NM are operators the horizontal and vertical tangent spaces, respec- tively, hence they commute, and they commute with Av. Aи respectively as seen in the argument of (18) Proposition 1.6). This implies that the operators can be simultancously diagonalized, i.e., the existence of a common basis of eigenfunc- tions.
(1(A,) Lemma B.5. For >e((Aa))) S (( = T and (d = -A,Ap)
Proof. By Lemma B.1 if Φ; an eigenfunction of Av.g. its fiber-wise restriction <xl=-1(x)) must be eigenfunction of the corresponding weighted Laplacian on the ball. As its eigenvalue smaller than A /r², it must correspond to the eigenvalue, This implies o; is constant fibre-wise, in particular dx(x,, v) Sx-1(0) del= (xx) dg. Thus, by Proposition B.
0p AH.p + Av.g A..pd AM.P / xx)
di x1)x-1(2) dg.
Thus for Φb to be an eigenfunction, it must be that fx-2(e)) (s)) ((s) dq. as a function on M, is an eigenfunction of AM.p call it f. Further, for all v. (r( u) = f(x), or in other words, o f o π as desired, and Ap. = AM.pf o = for Conversely, any f an eigenfunction of AM,p with eigenvalue < X /r2 corresponds some di as above.
B.2. Perturbation Argument
Our first aim is to analyze the effects of the noise on the (weighted) manifold Laplacian, namely to quantify the error between AT,(M) representing the Laplacian operator of the "noisy" manifold T, (MM), and the "noiseless" manifold Laplacian A A. particularly as pertains the spectral data associated the principal eigenvalues. More precisely, we will be concerned with eigenvalues below threshold of the order 2 showing that Proposition 2.1 holds approximately for (T,(M)- We study both the unweighted case, where the sampling density μ T, (M) is uniform w.r.t. the induced measure from RD, and the weighted case where smooth, non-degenerate factors along horizontal and vertical spaces. Throughout this section the assumptions are the same as in Section
The main idea is that the Sasaki metric closely approximates the induced metric on T, (MM) follows from 200 Proposition 6) that, under rescaling, the residual between the induced metric ,r on T, (-(M) and the Sasaki metric (s,r on the order of the tube width.
Lemma B.6 (Sasaki metric perturbation). For the rescaled induced metric {t, b,, let Ar denote its relative distortion w.n the rescaled Sasaki metric (., :)aa,r := (a)., o )sa Then I - Arl1 & Cr for a constant C depending only on the manifold M.
14

---

The Noisy Laplacian
Proof. From 20 Proposition 6), have
S) = (n, S)sa.r "y7,,iip R Ssa, + (1,,)
for some H, smooth and uniformly bounded for all S 1, and Rw the Weingarten map (or shape operator) 17 Chapter 3). The middle term, function of the curvature of the ambient manifold, vanishes as the ambient Euclidean space is flat. Hence get perturbation of the desired order.
Corollary B.7. Let μ be the induced measure and MSa. the measure induced by the Sasaki metric. There exists constant C depending on M such that
| dp/dusall 5 11= O(Cr), - Arloo S Cr.
1-
Proof. From Proposition B.6 we have
-rllss I rr|xx/110 S
for some C' depending on M. Now, dp/ dpea = det A,, and the above bound on the operator norm implies
(1 (1-Cr) Cr)) I det Ar I (Cr +1);
from which the inequality follows.
Next, to compare the spectral decompositions of åp.r and A, we use a variational argument, studying the Dirichlet forms of the two operators. As it will be of interest us compare operators relative different underlying densities (Sasaki vs induced), this requires an identification between the corresponding spaces of Sobolev functions H2 (14) H2 (Usa). Even though these spaces coincide, as a simple analysis such as (33 Proposition 5.2.2) reveals, some care is needed as the norms are not the same, i.e. the I norm of the same function will differ depending on the measure. What we require is that they are nearly isometric, that these norms can be made arbitrarily close as r - 0. For operators on different domains, in this case the two sobolev spaces, one must find an identification between their domains for which the identified operators are comparable. This leads the technical notion of
equivalence.
Let A, A be non-negative linear operators H, H' respectively. A, A' are d-quasi-unitarily equivalent if there exists J H H', J': H! + H such that
|| 2, |J - J'l J - J'
+ 1) JJ' + 5, |J + 1- (A'+ 5
From this framework, the main result we will need is 33 Theorem 5.2.6), which restate follows.
Proposition B.8. Let Ay. A' be weighted Laplacians with relative distortion A and p: dv/dp. Let J H (1) - H²) and J': (v) + H² (n)) be the trivial identification maps Ju = u, J' f = f. Then for
8= ===max(1/ 12 - 1/ 1pp 1/2 1/2 1/2 - /2 1/2 1b0),
8: max o0 ||I Alloo):
Ays Ai are 48 46-quasi-unitarily equivalent. à < 1/2 then they are also 16ō-quasi-umitarily equivalent.
The following is a consequence of 33 Proposition 4.3.1) and the previous results, providing general relationship between the Sasaki and induced spectra.
Corollary B.9. There exists constant C' depending on M such that, for 8(r) = 1c 0(r), (f (()( < 1/2,
(Ax(A,) - X (A+) < (A,(),)(()) Further, there exists constant C₃ such that, for 5(r) <
[|Px(A,) - (A & 16C,5(r), in particular, for any du Aa( S simple, du (λ,)) 6x (A,) unit, we have
l (A,) dre (Ar))l S [2Cx + (A,) 1)]8(r))
15

---

The Noisy Laplacian
Corollary B.10. There exists a constant C depending on M such that, Cf S 1/2.
(Ao(Ap)r) - dn (A & 8d4 (Am
Further, there exists constant Cy such that, for Or S (1+A+
[IP.(A,) PA(A+)lI S C6,,Cr, in particular, for any dde (Ar) S simple, d& (Axr)):: ); dR (Az,)) unit, we have
(A &u (1 S [20x + (A))(())))))))))))
Proof of Theorem 3.7
This result follows from the above results in tandem with Proposition 2.1 part 5.
Proof of Corollary
3.2
This corollary follows immediately due to the relationship P(4) = (1(
C. Multi-Scale Spectral Growth
C.1. Packings
A A 1 || packing of space X, X; = ( (..lc((X.e.))-1))) is maximal collection of points xf such that min ||a 2 2 e. The packing number Eack(XX,,,11 II) is exactly the quantity of elements in the packing. Covering numbers Cover(X', 2e, [I) are similarly defined, but rather than a separation requirement, the union of the neighborhoods of the cover elements should be the whole space X. and the cover should be a minimal collection that achieves this. In both notations, we suppress the dependence on the norm when it is understood.
It follows that X₂ is also 28 cover of Xz. Pack e) 2 Cover(XX, 8) otherwise, if a point was 2a distance from every member of this set, it could be included while maintaining the separation property, contradicting the maximality of this set.
C.2. Proof of Theorem
We prove Theorem two steps. First, focus on upper-bounding the counting function. We follow the details of (26 Lemma C.1. Let X be a bounded domain with smooth boundury. Then,
N(C(4,e)) 3). (Pckk(
Proof. We aim to construct collection of orthogonal Neumann functions with controlled dirichlet form growth. By the min-max characterization, this upper-bounds the growth of corresponding eigenvalues. The simplest way to do this is to ensure that our functions have no common support, hence 1 orthogonality follows trivially. This is naturally achieved by packing, although the boundary of our domain requires slightly specialized approach. That is, near the boundary, the ball around a point in the subspace topology may be very degenerate, necessitating a more careful construction. This task has already been undertaken in (26), and we reference the essential results.
Let NN 0. By (26) Corollary 2.3), if supzex such that
S p(X)/N then one can construct A X
((X) m(A,) 20(4,)) ((A,,A) 2 3E.
Let AS denote the f-tteniing of A,, and let be the collection of indices such that su(A}) 2 (N/)) By subadditivity, it is immediate that |75l < N/2. Hence, for any i E Ig. by (26) Proposition 3.1), one can select Sa unit norm with Neumann boundary conditions supported on A such that R( < 4C(4, As the support of these functions is disjoint, they are an orthonormal set of at least N/2 functions, hence
4C(4,))
AN/2 <
52
16

---

The Noisy Laplacian
follows that (4, sex e))( s x(X)/N implies AN/2 4C(4, Notice that
Pack(X, s) & /(/)/ inf ((B(x,=))
sEA
hence (C)) ()( S p(X)/Ni is satisfied for 44, S Pack(X 8)
suPLex p(B[r,]]) that is
infarx ((B(ae))
4C
Pack(X io ((M())))) D ((B(ec))
as desired.
For the remaining inequality, we follow (27).
Lemma C.2. For X compact and convex or closed without boundary, there exists a constant C" depending on X such that
Pack(X,,) NN(C'=
Proof. The structure of this proof similar in flavor Lemma C.I again subdivide our domain, this time via packing, and consider the moments of different Laplacian eigenfunctions restricted these disjoint balls. Precisely, for X., consider the map
((B(2,))) JB( Sdy
b(f)
R Pa)
PPO S BB polee fdu
Let {di) be unit Laplacian eigenfunctions, and E(A) spanfo:: : X S }} for some À >> 0. Suppose that there exists E E(A) such that b(f) 0. To fall in the null space of b, f must be mean across each of the given subdomains. Intuitively, this requires strong variation for our function, which we quantify via Poincaré-type inequalities on each of the balls, forcing the corresponding Laplacian eigenvalue to be large.
Making this precise, we have x(B(a;;)) E)) SB(at .e) [du for all i Pack(XX,)) particular, we can use Proposition
2.1, Proposition 2.1), and the realization of X, as 2: cover to bound
| TRAn>EIR
Σ S 1=1 M(g,26)
1
Adp s SC' Σ I
n
(V / |V
B(z)22))
where C' is constant that depends on the dimension. Note that the first inequality is strict as if no two balls had non- trivial overlap then another ball could be adjoined to the packing. To see the final inequality, we must show that every X' contained at most C(2, E) of the Bax 2e) balls. Take B(x 2e). Observe that or E Bax, 2s), and in particular, for any two such points covering x, xf, 3 E B(x, 2s). Thus, by the separation condition, there can be most Pack (1x, 2e), e) of covering æ. For f E (()) we have
J Pd 211 / |VS
X-1
hence b(f) = 0 implies --1 < C2C(2, Thus for X C2C(2, b is an injection. In particular, this implies that
dim E( (2( S Pack(X, E), that is
Apack(X,c) 2 2CC((C(((2
D. Further Data Details
D.I. Synthetic Data
17

---

The Noisy Laplacian
(a) Circle(S*)
(b) Sphere(S²)
(c) S- S-Shape
(d) Bottle
Figure 7: Samples from the four synthetic manifolds used in our experiments colored by the first twelve o: (M) estimated using Diffusion Maps. In subfigure d), only the first 3 ambient coordinates of the Bottle manifold are shown. The manifolds have intrinsic dimensions dg- = 1, dga 2, dsshape 2, Bottie
Throughout our experiments we will use four synthetic smooth manifolds: The unit circle 5", the unit sphere 5?, the S S-Shape, and a new manifold that we created which will refer to the Bottle(See Figure This latter manifold is parametrized by:
DM
S
2
S
2
3
S S-Shape
2
3
sin (sin( )))
Bottle
2
4
cos (T.() + (sin( ))) ( 2r²
(21,
Table 1: Synthetic manifolds'
dimension
for (21, [0, x [0, 1] and the sigmoid function.
The intrinsic dimension d and 'usual' ambient dimension Dbefffore they are embedded again in an ambient space RD with DM I D where noise will be added) of the synthetic manifolds can be found in Table D We sample points uniformly from S and 5 while from the S-Shape and the Bottle we sample coordinates uniformly and map them to the 'usual' ambient space. This sample then embedded in larger dimensional ambient space of dimension D where noise added uniformly on a ball of radius analytically compute the
in the normal space which has dimension d, = D d. For four synthetic manifolds normal space at every point. We repeat this process for various E [0, r) and d,, We sample many points as we consider necessary depending on the experiment, but for most cases where we are not interested in exploring the effects of sample size, we sample = 5000 points.
D.2. Real Data
For our real data experiments we use three Molecular Dynamic SiMulations(MDDS datasets:
Toluene(Tol), Malonaldehyde(Mal), and FFth. MDS simulations dynamically generate atomic configurations which, due to interatomic interactions, exhibit non-linear, multiscale, non-i.i.d. noise, as well as non-trivial topology and geometry. MDS are a heavily used tool, with many hours of high power computing devoted them. For more information on the MDS dataset refer the reader to (28)
DM
Tol
50
Mal
50
Eth
50
MDS data is originally generated in 3--Nmm coordinates. We process this raw data to ensure the invariance to translation and rotation before we estimate the Laplace operators. For this, we obtain an Euclidean group-invariant featurization of the atomic coordinates as a vector of planar angles a; 3 (%+ representing the planar angles formed by
Table
2: Real manifolds' di-
mension
triplets of atoms in the molecule. We then perform SVD this featurization, and project the data onto the top D = 50 singular vectors to remove linear redundancies. Thus, all three MDS datasets will have the same ambient dimension D. 50. Their intrinsic dimensions d can be found in Table while visualizations are provided in Figure
We add noise uniformly distributed on a ball of radius r in the ambient space for various r and d,. Noise added in the ambient space because, as opposed to the synthetic data, we don't 't have access to the reach 7 or to the normal bundle the MDS manifold. We do this for various r. We sample n 7500 points for all our experiments.
18

---

The Noisy Laplacian
(a) Toluene(Tol)
(b) Malonaldchyde(Mal))
(c) Ethanol(Eth)
Figure 8: Samples from the three MDS datasets: Toluene(Tol), Malonaldehyde(MMa)), and (Ehhnol(Eth) colored by the first twelve di (MM) estimated using Diffusion Maps. The manifolds are embedded in RR3 using 61,2,((AM) but they have intrinsic dimensions or = dasal = 2, d 2.
E. Further Details on Validation Experiments
We conduct a series of experiments validating the threshold phenomenon and the robustness of low-frequency eigenpairs to noise predicted by our theoretical results on the datasets described in Appendix [ For this purpose, we need to estimate various Laplace operators and their eigenpairs as they have no analytical formulas that we can use(S" being the exception). We generate multiple datasets representing samples from (,M)) for multiple increasing values of the two main noise parameters interest: r(the radius of the tubular neighborhood) and d,, (the dimension of the normal space which is related to the ambient dimension by D dn + d). Theorem 3.1 predicts that low-frequency eigenvectors oi (i(A),(M) are stable w.r.t. to these, while the noise threshold XY /r² acts delimiter between the noiseless and noisy eigenvectors. As such, we develop both quantitative and qualitative methods to investigate this behavior.
E.1. Estimating the Laplace Operators and their Eigenpairs
We rely Diffusion Maps(I) estimate the Laplace operators AM. AT, (M)) and their spectral decompositions. We select the bandwidth required to compute the affinity matrix per dataset basis using the geometric self-consistency algorithm of 4I). We do so for all manifolds described in Section for many tubular neighborhood radii r E (0, (when the reach known), and dimensions of the normal space d, = d. For most of our experiments we use an embedding size of m 24, but some case we use m > 24.
E.2. Qualitative Verification of the Theory
To validate the threshold phenomenon and the robustness of low-frequency eigenpairs to noise predicted by Theorem 3.1 we observe the behavior the eigenvalues (((Ar.(M)) and cigenvectors ob (A(A,,()) of the Laplacians estimated in Section
E.1 Jas r and d, are varied.
First, in Figures and 10 focus the paths which the eigenvalues trace r increases. Furthermore, we keep track of the noise threshold and observe the effect that has the stability of the (AAT.())) We notice that, the theory predicts, the cigenvalues well under AY /r" are almost constant, while the higher frequency ones become volatile with downward trend as they approach or surpass the noise threshold. Furthermore, we observe that increasing the noise dimension d,, (and implicitly increasing D) has no bearing on this effect.
Second, in Figures || and 12 we perform a similar experiment, observe the behavior of the eigenvectors Φ) (A,, instead. order Visually, there should be clear correlation between the values of the eigenvectors and the manifold coordinates, indicating that Φb (AT,(M)) correctly captures the structure of M. When that is not the case, expect to see random patterns over the coordinate space. Additionally, since for the synthetic manifolds we know the noise/normal space coordinates each sampled point, we fit polynomial regression models that use these as inputs and the Φ; as targets. If the model is able to predict the embedding coordinates from the noise coordinates, we can safely conclude that Φ. (,(A,,()) encodes pure noise. In our experiments we use polynomials degree 2. Since we do not know the coordinate spaces of the MDS manifolds, we use the lowest- frequency $1,2,3( AA)) of the noiseless manifolds instead. These experiments, which confirm our predictions,
their degree of corruption by noise, we color the coordinate spaces of the manifolds by dv (AT,,, (M))
19

---

The Noisy Laplacian
(a) Sphere
(b) S-Shape
(c) Bottle
Figure 9: Stability w.r.t to r and d, of the low-frequency eigenvalues for three synthetic manifolds: Sphere(a), S-Shape(b), and Bottle(c). Each path corresponds to one X; (A))),(M)) with its log value on the y-axis evolving as r increases from left to right on the x-axis. The frequency of the spectrum increases the up y-axis direction. The noise level Aÿ /r22 is represented by the black dotted line. On each we have, from left to right, increasing noise dimensions d, {2, 3, 6, 16, 24, 32). Note that the eigenvalues remain mostly constant long they below the noise threshold. However, this changes when they approach or surpass XL /r2. This phenomenon is largely independent of d,,
Toluene(Tol)
(b) Malla
(c) Ethanol(Fth)
Figure 10: Stability w.r.t of the low-frequency eigenvalues for three real MDS datasets. Each path corresponds X, ((AT(()) with its log value the y-axis evolving increases from left to right the x-axis. The frequency of the spectrum increases in the up y-axis direction. In all plots d,, = 50 and, opposed to the synthetic data, the noise is added in all ambient directions. The noise level AY / is represented by the black dotted line. Note that the eigenvalues remain mostly constant as long as they are below the noise threshold.
20

---

The Noisy Laplacian
summarized in Figures
and 12
while display how the regression models identify 'noise" (r(A), in
Figure 14
F. Further Details on VAE and LTSA Experiments
E.1 VAE Experiments
VAE( Variational Autoencoder) 12) is generative model that leams a probabílistic latent representation of data by combining deep neural networks with variational inference. optimizes a lower bound on the data likelihood by encoding inputs into a latent space with Gaussian prior and decoding samples back into the original space.
We repeat adapted version of the eigenvector qualitative experiments outlined in Section F.2 and observe that VAE embeddings behave similarly to those obtained by DM. However, there is no natural way to evaluate whether VAE's latent coordinate Φ; is low or high frequency. For this purpose we use the regression procedure outlined in Section E.2 Furthermore, we evaluate the ability of the decoder to reconstruct the output without using Φ;, but using all the other coordinates. the polynomial regression model is able to predict Φ; from noise and if the decoder doesn't require Φ; for proper reconstruction, we say that Φ; high-frequency. Conversely, Φ; is indispensable for reconstruction and cannot be predicted from noise, then we call this latent coordinate low-frequency. We observe that this latter is stable w.r.t both and d Furthermore, if the VAE has more capacity than need, then it will use the extra coordinates to encode noise. Our experiments are summarized in Figure.
For all our VAE embeddings we use the same network which has an encoder with FC layers of sizes (64, 128), an embedding size of m = 4, and a decoder with FC layers of sizes (128, 64). We use Layer Normalization (42) and GELU activation (43) between the hidden layers, a batch size of 256, Adam optimizer (44), and a weight of 0.1 of the KL-Divergence loss relative the reconstruction loss.
F22 LTSA Experiments
LTSA(Local Tangent Space Alignment) 13 a classical manifold learning algorithm that does not rely on Laplacian estimation. Instead, it computes local linear coordinates for the neighbors of each point and aligns these local representations to obtain global embedding. We repeat the eigenvector qualitative experiments outlined in Section E.2 and observe that LTSA computed embeddings behave exactly the same those obtained via DM and in complete agreement with Theorem
For all our LTSA embeddings we use an embedding size of m = 12 and & = 32 nearest neighbors without cutoff radius. We only run these experiments on the synthetic data. Our results are summarized in [4 For all our LTSA embeddings we use an embedding size of m 12 and k = 32 nearest neighbors without a cutoff radius. We only run these experiments on the synthetic data.
21

---

The Noisy Laplacian
Noise dimension d
Noise level r
Noise level r
Noise level r
Noise level r
Frequency
Frequency
Frequency
Frequency
M
1:00
(a) Sphere
Noise dimension d
Noise level r
Noise level r
Noise level r
Noise level
Frequency
Frequency
Frequency
Frequeno
(b) S- Shaae
Noise dimension d,
Noise level r
Noise level
Noise level
Noise level
Frequency
Frequency
Frequency
Frequency
(c) Bottle
Figure 11:
Stability w.r.t to and d, of the low-frequency eigenvectors for three synthetic manifolds: Sphere(a), S- Shape(b), and Bottle(c). We color the coordinate spaces of the manifolds by low-frequency(top) and high- freghrrrqueccyboottom (AT-LM) Notice the stability of the former as r increases and the corruption of the latter once the noise threshold passed. On each column we have, from left to right, increasing noise dimensions d, E (4, 8, 16, 24). We notice, interestingly, that (and thus D d d,,) increases, the effect of noise on the eigenvectors with the same frequency mitigated. This is to be expected as X increases with the dimension, however more detailed perturbation analysis is necessary to rigorously verify that the perturbation magnitude decreases with dimension.
22

---

The Noisy Laplacian
Noise dimension d
Noise level
Noise level
Noise level r
Frequency
Frequency
Frequency
Figure 12: Stability w.r.t to r of the low-frequency eigenvectors for the three real MDS datasets: Toluene(Leeft) Malon- aldehyde(Middle), and (Rihh.)(Right). We color the coordinate spaces of the manifolds(for the MDS data these will be the 01,2,3 AM) by (wwffrequeccyttp) and ligh-frequennyyboottmm) e, (A)).)))) Notice the stability of the former increases and the corruption of the latter once the noise threshold is passed. In all plots d, 50 and, as opposed to the synthetic data, the noise is added in all ambient directions.
(a) Sphere
(b) Bottle
Figure 13: Results for VAES trained on 52 and Bottle for d, = 16 and r increasing from left to right. Each panel corresponds to one d; and displays from top to bottom: the coordinate space of the manifold colored by d., the reconstruction the data without o. and the prediction of each Φ from normal space/noise coordinates by a polynomial regression model. $1,2,3 are stable w.r.t. to noise, indispensable for reconstruction, and cannot be predicted from noise. Conversely, Φ1 is not correlated with the coordinate space of the manifold, not important for reconstruction, and easy predict from noise coordinates.
23

---

The Noisy Laplacian
Noise dimension
Froq
(a) Sphere
Noise dimension
Frequency
Frequency
Frequency
(b) S- S-Shape
Noise dimension
Noise level
Noise level
Noise level
Proquency
Frequency
Prequeno
(c) Bottle
Figure 14: Stability w.r.t to and d, of the low-frequency embeddings and the threshold effect exhibited by the high- frequency ones obtained using LTSA for three synthetic manifolds: Sphere(a), S-Shape(b), and Bottle(c). We color the coordinate spaces of the manifolds by Φi. Notice the similarity with Figure TT] As before, increases from left right, polynomial regression model predict able do so(the diagonal
while on each column we have d, {16, 24, 32). On the left-hand side the oi 's from the known normal space/noise coordinates for all r's and d, 16. When lines tell us when that is the case) can conclude that the corresponding d; represents pure noise.
24


Reviews:
[{"review_id": "DQ9cJCI2C9", "reviewer": "Reviewer_j76L", "summary": "the authors provide a theoretical analysis that shows that Laplacian eigenfunctions capture the geometry of the underlying\nmanifold, without needing the noise amplitude or dimension to vary with the same size.  The main technique leverages the so called Sasaki metric in Riemannian geometry. They conduct experiments and also observe similar behavior in other non Laplacian based dimension reduction methods.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewers for the constructive reviews! Geometric Data Analysis (GDA) is a small area, and your attention to it is appreciated.\n\nHere we respond to the main points raised by all reviewers.\n\nIs the result suprising and new in its particular area? \n\nOur sharp threshold result is actually surprising, because in the noiseless case, when samples are _on_ a manifold, the degradation in the eigenvectors is gradual, with no threshold. We show that if noise is added to the samples, the degradation is catastrophic at a predictable threshold. This was not expected from existing theory. \n\nMoreover, this threshold depends ONLY ON THE NOISE, not on other (unknown) properties of the manifold. This is also surprising, since so many other DiffMap properties depend on injectivity radius, reach, volume, etc.\n\nThird, it also suggests that *anisotropic noise* may paradoxically make the estimation of the eigenfunctions easier, due to widened spectral gaps.\n\nFinally, it adds to other indirect evidence that estimating a manifold by the eigenfunctions of the Laplacian, even though beautiful theoretically, may not be robust in practice. The authors plan to focus on LTSA in future work. [Note that embeddingless methods to estimate a manifold exist, their behavior is well studied, and _different_ from what we discover in this submission.]\n\nPractical implications:\n1) Our result is an __impossibility results__. We show that estimating the Laplacian e-vectors has informational limitations, __even under strong assumptions__.  An impossibility result directly impacts further analysis under weaker assumptions. \n\n2) If noise can be estimated, then from our analysis, the threshold will be known, and we will know which e-vectors belong to the manifold.\n\n3) The experiments on VAE suggest that the threshold phenomenon we discovered is more general, and this begs to be known.\n\n4)  UMAP the most popular of Neighbor Embedding methods uses the eigenvectors of the Laplacian to seed their embedding. Thus our result may be relevant to the UMAP users. More precisely, depending on how one uses UMAP, and how one avoids other unrelated artefacts of this heuristic, the threshold may become relevant or not. \n\nWe will include comments 1) and 2) in the final version of the paper to clarify the implications of our study.\n\t\nWe are aware this work is of a somewhat \"niche field\", and we thank the reviewer who expressed this fact. Indeed, Neighbor Embeddings are vastly more common. This reality will color the decision on this paper, whether it's explicitly stated or not. \n\nWe understand that ICML may make the strategic decision to favor papers based on their area. When such a decision is made, it is not just affecting the authors, it is also implicitly telling the people who might read this paper that ICML the flaghips ML conference has no place for GDA (for example). \n\nMore to the point, the theoretical properties we uncover are broadly relevant. As we have already discussed, our results have immediate importance for popular algorithms such as UMAP, and empirically we see similar threshold phenomena may affect other non-Laplacian embeddings. Thus our work is not only a result regarding one specific spectral analysis of a dataset, but a new informative perspective connecting denoising and dimension reduction.\n\nWe now focus on reviewer specific points.\n\nThe convergence result by Dunson, Wu, Wu has several overlaps with our work. That paper establishes guarantees for Laplacian estimation through empirical samples.  As we establish properties of the continuum limit of these estimators, these results can be combined to assess the quality by which noisy samples from a manifold can be used to recontstruct intrinsic Laplacian data, although not without caveats:\n\n1. Our main results establish $L^2(\\mu)$ approximation guarantees, differing from the $L^\\infty$ result of DWW. One potential path to allign these is to extend our analysis to an appropriate RKHS topology, namely a high order sobolev space, from which a convergence result would then imply the desired sup-norm convergence.\n\n2. The results of DWW are not technically applicable to our setting. They assume data to be drawn from a closed manifold, a condition tube manifolds violate. Showing that their result hold in our setting is non-trivial, although it can most likely be addressed using standard techniques.\n\n3. The rate of convergence would also be of key interest. We expect this to be a multi-scale phenomenon similar to the spectral growth we analyze in our paper. We expect an initial estimation rate on the order of the intrinsic dimension of the data, as has been shown in other results which relate Laplacian approximation to covering and packing numbers.\n\nLastly, we thank the reviewer for their constructive feedback on the readability of the paper. We can adjust our presentation to emphasize the relationship between Sasaki and induced metrics in the main text rather than the appendix.", "claims_and_evidence": "yes, the claims are generally supported. The mathematics is, to the best of my ability, sound. The experiments, while not exhaustive, do support the claims of the authors.", "methods_and_evaluation_criteria": "yes. The experiments demonstrated the cutoff phenomenon as predicted by the theory.", "theoretical_claims": "I only checked the main statements of the theorems in the main text. Those theorems appear sound to me.", "experimental_designs_or_analyses": "Yes, I checked the soundess of the experimental design. They are fine.", "relation_to_broader_scientific_literature": "This is a theory paper that provides advancement on the theoretical analysis of popular algorithms that are broadly used in scientific applications.", "essential_references_not_discussed": "How does the current work related to prior work on L-infinity convergence? \n\nSPECTRAL CONVERGENCE OF GRAPH LAPLACIAN AND HEAT KERNEL\nRECONSTRUCTION IN L∞ FROM RANDOM SAMPLES by dunson, wu and wu", "other_strengths_and_weaknesses": "The main weakness of this paper is motivation and readability. \n\nSince most ML readers are likely not familiar with the Sasaki metric, I suggest the authors spend more time and text to introduce the metric and how it differs from traditional ones and provide more intuition.", "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": "vdQkt0EUig", "reviewer": "Reviewer_BJ7A", "summary": "This work brings of the interesting Sasaki metric into manifold learning and Laplacian Enginmap, and prosed theoretical analysis results to support low frequency eigen recovery under noise constrains defined in abstract. \n\nStrengths: the high-level idea of introducing Sasaki metric, with both \"tangent\" and \"normal\" concept, or as \"horizontally\" and \"vertically\", and with informative recovery threshold, which is linked with noise amplitude. \n\nExperimental results on both synthetic data and real data, are presented to support Theorem 3.1, and include results from LTSA (ref. 3) and VAE (ref. 2), which are not Laplacian decomposition-based methods. \n\nReferences:\n\n1. R. R. Coifman and S. Lafon, “Diffusion maps”, Applied and Computational Harmonic Analysis, 2006\n2. D. P. Kingma and M. Welling, “Auto-encoding variational bayes,” 2022.\n3. Z. Zhang and H. Zha, “Principal manifolds and nonlinear dimensionality reduction via tangent space alignment,” SIAM, 2004.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewers for the constructive reviews! Geometric Data Analysis (GDA) is a small area, and your attention to it is appreciated.\n\nHere we respond to the main points raised by all reviewers.\n\nIs the result suprising and new in its particular area? \n\nOur sharp threshold result is actually surprising, because in the noiseless case, when samples are _on_ a manifold, the degradation in the eigenvectors is gradual, with no threshold. We show that if noise is added to the samples, the degradation is catastrophic at a predictable threshold. This was not expected from existing theory. \n\nMoreover, this threshold depends ONLY ON THE NOISE, not on other (unknown) properties of the manifold. This is also surprising, since so many other DiffMap properties depend on injectivity radius, reach, volume, etc.\n\nThird, it also suggests that *anisotropic noise* may paradoxically make the estimation of the eigenfunctions easier, due to widened spectral gaps.\n\nFinally, it adds to other indirect evidence that estimating a manifold by the eigenfunctions of the Laplacian, even though beautiful theoretically, may not be robust in practice. The authors plan to focus on LTSA in future work. [Note that embeddingless methods to estimate a manifold exist, their behavior is well studied, and _different_ from what we discover in this submission.]\n\nPractical implications:\n1) Our result is an __impossibility results__. We show that estimating the Laplacian e-vectors has informational limitations, __even under strong assumptions__.  An impossibility result directly impacts further analysis under weaker assumptions. \n\n2) If noise can be estimated, then from our analysis, the threshold will be known, and we will know which e-vectors belong to the manifold.\n\n3) The experiments on VAE suggest that the threshold phenomenon we discovered is more general, and this begs to be known.\n\n4)  UMAP the most popular of Neighbor Embedding methods uses the eigenvectors of the Laplacian to seed their embedding. Thus our result may be relevant to the UMAP users. More precisely, depending on how one uses UMAP, and how one avoids other unrelated artefacts of this heuristic, the threshold may become relevant or not. \n\nWe will include comments 1) and 2) in the final version of the paper to clarify the implications of our study.\n\t\nWe are aware this work is of a somewhat \"niche field\", and we thank the reviewer who expressed this fact. Indeed, Neighbor Embeddings are vastly more common. This reality will color the decision on this paper, whether it's explicitly stated or not. \n\nWe understand that ICML may make the strategic decision to favor papers based on their area. When such a decision is made, it is not just affecting the authors, it is also implicitly telling the people who might read this paper that ICML the flaghips ML conference has no place for GDA (for example). \n\nMore to the point, the theoretical properties we uncover are broadly relevant. As we have already discussed, our results have immediate importance for popular algorithms such as UMAP, and empirically we see similar threshold phenomena may affect other non-Laplacian embeddings. Thus our work is not only a result regarding one specific spectral analysis of a dataset, but a new informative perspective connecting denoising and dimension reduction.\n\nWe now focus on reviewer specific points.\n\nOn dimension estimation. Thanks for bringing up this point. [Little, Maggioni, IEEE 2009] present a dimension estimation in noise algorithm. They show that when performing local PCA at a well chosen radius the singular values have the largest eigengap at $d$ equal to intrinsic dimension. In other words, the noise and geometric eigenvalues separate. \n\nRather than directly estimating the dimension, it is also worth considering another perspective suggested by our paper. Dimension can be somewhat misleading. As seen in our analysis, high-dimensional manifolds can act as if they are low-dimensional if analyzed at an appropriate scale. Thus quantities such as covering numbers, or as popularly used in Laplacian estimation, median distance between datapoints, become more relevant in assessing the complexity of the data. If one was to assume that their samples were indeed generated from a tubular neighborhood, a simple estimator for intrinsic dimension could be the rate at which a random subsample covers the whole dataset when a relatively small number of subsamples is selected. As a dual perspective, for a generic dataset where one may not even adopt this strong tubular assumption, one may look at these same covering numbers and use them to assess an \"intrinsic dimension\" of the data.\n\nOn the citation of Belkin and Niyogi, we agree that this is more than appropriate to reference in our paper, and we will gladly include it. Regarding $r$, as mentioned by the reviewer, this is defined in section 2, however we can more clearly indicate that it is the radius of the noise where appropriate.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I looked Theorem 3.1, Theorem 3.3, and appendix section B and C, though not very carefully for examination.", "experimental_designs_or_analyses": "Laplacian and non-Laplacian based methods on both synthetic and real data are included in section 4 & 5 & appendix, all look reasonable.", "relation_to_broader_scientific_literature": "NA", "essential_references_not_discussed": "The following paper is one of the foundation works in the area of manifold learning, in particular for Laplacian methods, feel should be cited. \n\nM. Belkin and P. Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation, 15:1373–1396, June 2003", "other_strengths_and_weaknesses": "As seems related, manifold intrinsic dimensionality estimation, not explicit discussed in this work right, and feel will be interesting to see discussions in this line. \n\nFor real data with noise, often even the rough intrinsic dimensionality is challenging, and consider low frequency eigen recovery with theoretical analysis support, then guess perhaps under certain conditions dimensionality estimation can be more reliable.", "other_comments_or_suggestions": "Questions: not sure if I missed this, the noise scale \"r\" is defined in the abstract and mentioned section 2 too, though, it seems not see the clear definition or guess mostly as section 2.1 (the part refer to ref. 6, 19) as is.", "questions_for_authors": "NA", "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": "DK7cip9hqM", "reviewer": "Reviewer_Jzfg", "summary": "The authors focus on manifold learning and the effect of noise on the Laplacian operator in that context.\nThe paper is mainly a theretical study with some experiments to back up the claims.\nThe scope of the experiments is rather limited as they must fulfill strong assumptions (manifold data, uniform noise).", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewers for the constructive reviews! Geometric Data Analysis (GDA) is a small area, and your attention to it is appreciated.\n\nHere we respond to the main points raised by all reviewers.\n\nIs the result suprising and new in its particular area? \n\nOur sharp threshold result is actually surprising, because in the noiseless case, when samples are _on_ a manifold, the degradation in the eigenvectors is gradual, with no threshold. We show that if noise is added to the samples, the degradation is catastrophic at a predictable threshold. This was not expected from existing theory. \n\nMoreover, this threshold depends ONLY ON THE NOISE, not on other (unknown) properties of the manifold. This is also surprising, since so many other DiffMap properties depend on injectivity radius, reach, volume, etc.\n\nThird, it also suggests that *anisotropic noise* may paradoxically make the estimation of the eigenfunctions easier, due to widened spectral gaps.\n\nFinally, it adds to other indirect evidence that estimating a manifold by the eigenfunctions of the Laplacian, even though beautiful theoretically, may not be robust in practice. The authors plan to focus on LTSA in future work. [Note that embeddingless methods to estimate a manifold exist, their behavior is well studied, and _different_ from what we discover in this submission.]\n\nPractical implications:\n1) Our result is an __impossibility results__. We show that estimating the Laplacian e-vectors has informational limitations, __even under strong assumptions__.  An impossibility result directly impacts further analysis under weaker assumptions. \n\n2) If noise can be estimated, then from our analysis, the threshold will be known, and we will know which e-vectors belong to the manifold.\n\n3) The experiments on VAE suggest that the threshold phenomenon we discovered is more general, and this begs to be known.\n\n4)  UMAP the most popular of Neighbor Embedding methods uses the eigenvectors of the Laplacian to seed their embedding. Thus our result may be relevant to the UMAP users. More precisely, depending on how one uses UMAP, and how one avoids other unrelated artefacts of this heuristic, the threshold may become relevant or not. \n\nWe will include comments 1) and 2) in the final version of the paper to clarify the implications of our study.\n\t\nWe are aware this work is of a somewhat \"niche field\", and we thank the reviewer who expressed this fact. Indeed, Neighbor Embeddings are vastly more common. This reality will color the decision on this paper, whether it's explicitly stated or not. \n\nWe understand that ICML may make the strategic decision to favor papers based on their area. When such a decision is made, it is not just affecting the authors, it is also implicitly telling the people who might read this paper that ICML the flaghips ML conference has no place for GDA (for example). \n\nMore to the point, the theoretical properties we uncover are broadly relevant. As we have already discussed, our results have immediate importance for popular algorithms such as UMAP, and empirically we see similar threshold phenomena may affect other non-Laplacian embeddings. Thus our work is not only a result regarding one specific spectral analysis of a dataset, but a new informative perspective connecting denoising and dimension reduction.\n\nWe now focus on reviewer specific points.\n\nWe believe our work has many practical implications, and we will dwell on its implications for DM embeddings in particular. The sharp threshold phenomenon indicated by our results gives clear guidance to practitioners about the limitations of Laplacian embeddings. In practice, one may argue that this is already well understood, as low dimensional embeddings are typically preferred. The benefit of our results is that they provide new rationale for why this is essential, and moreso, how one may select a cut-off. In future research, techniques to analyze the structure of the noise may be developed to estimate exact cut-offs. Further, our theory suggests that ``uninformative\" eigenfunctions catastrophically deviate from the underlying manifold structure, thus standard techniques to promote parsimony are effective at removing this uninformative information.\n\nStill dwelling on this point, not all papers that consider Laplacian embeddings advocate for low-dimensional bases. For example, in [Green, Tibshirani, 2021], infinite dimensional bases are employed for non-parametric regression. Our work provides an interesting complementary perspective on this. For signals that have little dependence on the noise, our results indicate that there is very little benefit to exceeding the \"noise threshold\". This opens up many questions about how this can be leveraged to improve learning rates.\n\nIt is an excellent point raised about more refined results being possible for LTSA, as a connection to the Laplacian exists as seen in works such as [Ting, Jordan, 2018]. We plan to pursue this in future research.", "claims_and_evidence": "Manifold recovery in spite of noise.\nFirst use of the Sasaki metric.\nThe main claims are reaonable and apparently proved in a sound way.", "methods_and_evaluation_criteria": "Looks sound (mainly theoretical proofs).", "theoretical_claims": "No.\nThe claims are mainly theoretical/mathematical and they largely exceed my paygrade.\nAs said above, the claims sound reasonable and there is no real surprise in the results (rcovery wrt noise level).", "experimental_designs_or_analyses": "Well illustrated experiments of manifold learning back up the claims.\nMainly synthetic data owing to the strong assumptions of the theory (manifold data only, constant/uniform noise level).\nSome (very specific) real data is used in additional experiments.", "relation_to_broader_scientific_literature": "Good.", "essential_references_not_discussed": "Good.", "other_strengths_and_weaknesses": "The paper is well written and relatively easy to read for a theoretical one.\nAs most theoretical papers, the contributions are mainly proofs that have little impact on the practice.\nThe domain of interest (manifold learning with spectral embedding) is a niche (compared to DR with NE, e.g.).\nThese minor shortcomings do not decrease the value of the contribution for a slected audience, most probably.", "other_comments_or_suggestions": "/", "questions_for_authors": "Can you refine your assesment LTSA? Same behavior but really no link? LLE not using explicitly a Laplacian but does it implicitly, as shown later. Possible to come to a similar result?", "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:

Meta-review: This paper analyzes a threshold phenomenon in nonlinear dimension reduction using Laplacian Eigenmaps applied to noisy high-dimensional data. The main contribution is a theoretical result showing a sharp transition in embedding quality as a function of the noise-to-signal ratio. The analysis is mathematically sound, drawing on tools from random matrix theory and perturbation analysis, and it offers insight into the limitations of spectral methods under noise.

Reviewers found the core result technically solid, though some noted that the scope is narrow and the practical relevance could be more clearly articulated. The empirical evaluation is minimal, serving primarily as a sanity check. The authors are encouraged to discuss potential generalizations to other methods or noise models. Overall, while focused, the work contributes a well-posed result to the theory of spectral embeddings.
Decision: Accept (poster)