Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
Authors: Shiyu Wang
Mariam Avagyan
Yihan Shen
Arnaud Lamy
Tingran Wang
Szabolcs Marka
Zsuzsanna Marka
John Wright
Venue: ICML 2025 poster (2025)
Keywords: Manifold Denoising
Learning-to-optimize
Primary area: optimization->everything_else

Abstract: Learned denoisers play a fundamental role in various signal generation (e.g., diffusion models) and reconstruction (e.g., compressed sensing) architectures, whose success derives from their ability to leverage low-dimensional structure in data. Existing denoising methods, however, either rely on local approximations that require a linear scan of the entire dataset or treat denoising as generic function approximation problems, sacrificing efficiency and interpretability. We consider the problem of efficiently denoising a new noisy data point sampled from an unknown manifold $\mathcal M \in \mathbb{R}^D$, using only noisy samples. This work proposes a framework for test-time efficient manifold denoising, by framing the concept of  "learning-to-denoise" as  *"learning-to-optimize"*. We have two technical innovations: (i) *online learning* methods which learn to optimize over the manifold of clean signals using only noisy data, effectively "growing" an optimizer one sample at a time. (ii) *mixed-order* methods which guarantee that the learned optimizers achieve global optimality, ensuring both efficiency and near-optimal denoising performance. We corroborate these claims with theoretical analyses of both the complexity and denoising performance of mixed-order traversal. Our experiments on scientific manifolds demonstrate significantly improved complexity-performance tradeoffs compared to nearest neighbor search, which underpins existing provable denoising approaches based on exhaustive search.

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
Shiyu Wang 12 Mariam Avagyan 12 Yihan Shen 32 Arnaud Lamy" 12 Tingran Wang" 12 Szaboles Márka 4.2
Zsuzsanna Márka 62
John Wright 172
Abstract
1. Introduction
Learned denoisers play fundamental role in vari- ous signal generation (c.g., diffusion models) and reconstruction (e.g., compressed sensing) archi- tectures, whose success derives from their ability to leverage fow-dimensional structure in data. Ex- isting denoising methods, however, either rely on local approximations that require a linear sean of the entire dataset or treat denoising as generic function approximation problems, sacrificing effi- ciency and interpretability. We consider the prob- lem of efficiently denoising new noisy data point sampled from an unknown d-dimensional mani- fold M E DR using only noisy samples. This work proposes a framework for test-time efficient manifold denoising, by framing the concept of Searning-to-denoiss as (learning-to-optinn optimizze" We have two technical innovations: learning methods which learn to optimize over the manifold of clean signals using only noisy data, effectively "growing" an optimizer one sample at a time. (ii) mixed-order methods which guarantee that the learned optimizers achieve global opti- mality, ensuring both efficiency and near-optimal denoising performance. We corroborate these claims with thcoretical analyses of both the com- plexity and denoising performance of mixed-order traversal. Our experiments on scientific manifolds demonstrate significantly improved complexity- performance tradeoffs compared to nearest neigh- bor search, which underpins existing provable denoising approaches based on exhaustive search.
Denoising is core task in signal and image processing. Denoisers also play fundamental role in state-of-the-an approaches to signal generation and reconstruction. Dif- fusion models generate intricate images from pure noise, via a sequence of denoising steps; learned compressed sens- ing methods reconstruct accurate medical and scientific im- ages from incomplete, indirect measurements, again via a sequence of denoising steps. While these iterative proce- dures produce high-quality results, they are computationally costly: a sophisticated learned denoiser needs to be applied repeatedly to produce a single output. The test-time cost of denoising is major bottleneck for both high-resolution image generation and real-time image reconstruction.
Accurate denoising is critical, because the denoiser encodes prior knowledge about the set of images of interest (natural, medical, scientific, etc.). These images reside near low- dimensional subsets of the image space, which are often conceptualized as low-dimensional manifolds; learning to denoise tantamount to learning these manifolds.
(i) online
In this paper, we study a model manifold denoising problem, in which the goal is learn to denoise data lying near a d-dimenisonal submanifold M of a high-dimennional space Rº. As we will review below, there are extensive literatures on learning to denoise, and learning manifold models from data. However, there is relatively little work on provably learning test-time efficient denoisers. Existing methods with provable good manifold denoising performance involve lin- early scanning large datasets. As a baseline, nearest neigh- bor search across a minimal covering set has worst case complexity at least O(De where end is the size of the dataset required to cover the d-dimensional manifold, and D is the cost of computing distance in the ambient dimension. On the other hand, more practical neural network models currently lack guarantees of performance and efficiency.
Department of Electrical Engineering, Columbia University Data Science Institute, Columbia University 'Department of Computer Science, Columbia University "Department of Physics "Istiitute of Advanced Studies (iASK). Chernel utca 14, Koszeg, 9730, Hungary "Columbia Astrophysics Laboratory 'Department of Applied Physies and Applied Mathematics, Columbia Univer- sity. Correspondence to: Shiyu Wang <sw3601 @columbia.cdus.
We bridge this gap, developing and analyzing a family of manifold denoisers that are (i) test-time efficient, (ii) accu- rate, and (iii) trainable. Our main idea is to cast the problem of denoising new, noisy test sample x as an optimization problem over the a-priori unknown Riemannian manifold
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
M. This enables us draw on tools from Riemannian optimization, to develop methods which converge to small neighborhood of the ground truth - significant efficiency gain vis-a-vis exhaustive scan. The code for our framework and experiments is available at httpttt/////.... / /ttttbb..//uub./gt/g//pp/.....b. tht... com/ shiyu- www.://ooddda.oooooooo Traverrsarrav
resolution, and inpainting (Venkatakrishnan et al. 2013
Zhang et al., 202T). A high-quality denoiser not only re- moves noise but also encodes structural information about the data, making it powerful tool for complex inverse problems. Recently, diffusion models have demonstrated that iterative denoising can effectively model complex data distributions, emerging as a powerful generative modeling technique (Ho et al. 2020 Song & Ermon 2019).
One challenge stems from the unknown nature of the mani- fold and observation of only noisy samples. To apply ideas from Riemmanian Optimization, proximation of the manifold. Our framework addresses this by learning the optimizer directly from noisy data via an online algorithm. The method uses the manifold's low dimensional structure and learns local linear models to facil- itate movement in the tangent direction. Another challenge that optimization methods converge to critical points, in- cluding suboptimal local minimizers. To address this, we build tunnels (Figure 4 to allow escape from each local minimizer. When stuck at a suboptimal local minimizer, we select the tunnel which would bring us closer to the target point, an idea reminiscent of graph- based nearest neighbor search (Malkov& & Yashunin 2018).
need an accurate ap-
With the advance of deep learning, generic ML architectures
such as FCNNs, CNNs (Tlesammi & Ilesanmi 2021) trans-
formers Yao et al. 2022), or the U-Net (Fan et al. 2022)
have demonstrated strong denoising capabilities by learning to approximate denoising functions, a concept known as Their effectiveness largely stems from their ability capture underlying low-dimensional struc- tures in data an idea explicitly leveraged in autoencoder- based methods (Vincent et al. 2008). However, these mod- els do not directly incorporate the low-dimensional structure of the data, leading to considerable inefficiency in com- putation and scalability. Furthermore, as neural networks function are black-box models, they often lack theoretical guarantees or clear interpretations.
Our method, with high probability, achieves near optimal denoising error | æ;ll S no vd with test-time computa- tional cost O (C(M, (CL dd + D x 82 (M)). where (MM is novel complexity measure which quan- tifies the cost of escaping local minimizers, C(M, .))) depends on the diameter and curvature of M, the step size 5 and stopping tolerance (1. and c, c' are numerical constants.
Given that high nigh-dimensional data often reside near a lower-dimensional submanifold (Tenenbaum et al.) 2000 Fefferman et al. 2016), incorporating manifold structure into denoising tasks so-called manifold denoising (Hein) & Maier 2006 - has emerged as a rapidly growing area of interest. In the theoretical literature on manifold estima- tion and denoising (Genovese et al., 2012), the predominant methods are based on local approximation (Fefferman et al., 2020 Yao et al.) 2023), and while they offer near-optimal theoretical estimation and denoising guarantees, their test- time efficiency suffers- - each new test sample requires a linear scan of the entire dataset. Likewise, many empiri- cally effective methods (e.g., (Hein & Maier 2006; Gong] et al. (0100) for manifold denoising rely on nearest neigh- bor searches, resulting in high test-time cost.
2. Relationship to the Literature
Denoising has a long history in signal processing and ma- chine learning, evolving from early statistical techniques to modern deep learning methods. Traditional denoising tech- niques leverage structural assumptions about the clean sig- nal x;. For smooth signals, courier-based methods suppress high-frequency noise (Wiener 1949). Sparsity assumptions have given rise to wavelet shrinkage and dictionary learning techniques (Donoho| 1995 Elad & Aharon| 2006). In im- ages with self-similarity, methods such as nonlocal means and BM3D leverage repetitive patterns to enhance denoising performance (Buades et al. 2005] Dabov et al. 2007). Low- dimensional subspace methods, c.g.pprincipal component analysis and the Karhunen-Loève transform, approximate signals using fewer basis components to filter out noise (Does et al. 2019 Aysin et al. 1998).
In this work, we develop test-time efficient denoisers using ideas from Riemannian optimization (Absil et al. 2008 Sato 2021). Standard approaches in this area require M to be known priooii. Several recent works (Sober et al. 2020
Sober & Levin 2020 Shustin et al. 2022) develop manifold optimizers for unknown M, using local affine approxima- tion (via moving least squares). While this approach is inspiring, it encounters the same test-time efficiency issues as the above manifold denoisers, since these approximations are formed on-the-fly by linearly scanning a large dataset.
Recent developments in signal reconstruction and genera- tion have placed denoisers in more central role: accurate denoiser serves as an implicit model for clean signals. The plug-and-play framework leverages denoisers as implicit priors within iterative optimization, enabling flexible and efficient reconstruction across tasks like deblurring, super-
We develop test-time efficient denoisers by learning Rieman- nian optimizers over a particular geometric graph, which approximates M. We draw inspiration from graph-based nearest neighbor search (Malkov & Yashumin 2018), while leveraging the low dimensionality of M to avoid costly
2

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
(MMSE) denoiser when is small | The projection problem manifold optimization problem
can be interpreted
Unknown Manifold
we seek to minimize the function fo over smooth Rie-
Noisy Test Sample
mannian submanifold M of I...
x
Noisy Training Data 21, 21,...,22 N
Figure 1: Problem Setup. I = 11,2 + 21,...,, NN
NN; + nN are noisy traning samples from an unknown manifold M c PP.. x = D + x is the noisy test sample.
Optimization Trajectory
C' loo((E))) steps for an E-accurate solution Exhaustive Covering
ambient-space distance calculations.
(C/s)² points for an e-accurate solution
3. Problem Formulation
Figure 2: Dimension scaling advantage of optimization for searching Riemannian manifolds. Brute force search (the core of SOTA provable methods) requires test-time compu- tation exponential in intrinsic dimension d = dim(M).
Our goal is to learn to denoise data sampled from a d- dimensional submanifold M of D. We observe iid training samples 2i...., IN E R generated as
E training sample
Tr clean signal
2, moise
(3.1)
Dimension Scaling Advantage of Iterative Optimiza- tion. The optimization problem (4.1) could, in principle, be solved a variety of ways. One simple approach is to compute Pa on dense grid of samples -1,.... qM M, and select the sample q, with the smallest objective value. As illustrated in Figure 2 such exhaustive search becomes increasingly inefficient as the manifold dimension d in- creases. While exhaustive search is not a method of choice for solving smooth optimization problems, it plays a crit- ical role in Mate-offthe-as theoretical manifold denoisers Yao et al. 2023). ). At their core is local approximation of M, formed by selecting near neighbors of x by linearly scanning dataset ......, &N which is large enough to densely cover M - a form of exhaustive search.
with signal Zt,s ~ Hig, distribution supported on M, and noise zj mid (O),a)), independent of the signal. Figure] illustrates this setup. Our goal is to produce f P + R such that for new samples æ = Ø2 + 2 from the same distribution, fx, +) R F2, i... f denoises æ. We seek f satisfying the following properties:
[D1] Provably Accurate Denoising: near-optimal denois- ing performance (x) =tllž l1 S do with d the intrinsic dimension of M and a the noise standard deviation.
[D2] Fast Evaluation at Test Time: f can be applied to new samples with computational cost C(M))(L + edd yd, where Dd is the cost of projecting from ID. to RRd, and add the cost of searching d-dimensional manifold.
A more scalable alternative is to produce a by iterative optimization - e.g., by gradient descent. The objective function pa is differentiable, with gradient Vala.. = =q-a x. The Riemannian gradient of Pe point q M is the projection of V onto the tangent space M of M at q:
[D3] Data-Driven Learning: f can be learned using only noisy training samples.
Below, we introduce a trainable denoising method based on manifold optimization, which achieves [D1]-[D3].
grad [p]] PT,, M (ipa(g).
(4.2)
This is the component of the gradient along the manifold M, and direction of steepest ascent on M. A Riemannian
4. Denoising and Manifold Optimization
gradient method (Absil et al. 2008) steps along M in the direction of - -grad| [p setting
Since the observed signal æ is a noisy version of some signal Dn on the manifold M, one natural approach to denoising is to project x onto M, by solving
q" =xp, (-t grad[(px()))
(4.3)
min (g) = bl1 1=12. MEM
(4.1)
Indeed, letting fM)SE( = arg argmin, miny Ez,, + 2) xa1l denote the MMSE denoiser, we have that [[ P. [z]]l= = O(o). on a set of x of measure - O()). Other statistical criteria, such as maximum a a-posteriori (MAP) also lead to manifold optimization problems: in the Bayesian setting in which have prior density Ps . R clean signals, the MAP estimate minimizes bllq x: m112 > A Ps Pb(g) over M.
the solution E to this problem can be interpreted proba- bilistically as a maximum likelihood estimate of x;; when the underlying manifold has a uniform distribution; it also accurately approximates the minimum mean squared error
3

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
where / >> 0 is step size, and exPa TT.M - M is the exponential map, which takes direction (tangent vector) E Tq M to new point expy(v) in .M.
Definition 5.1. [Tangent Bundle Graph] A tangent bundle
graph G on vertices V -1,....,A consists of set of undirected first-order edges E² S V x V, where each element is denoted as u + v and
As shown in Figure 2 with appropriate t, this method con- verges linearly to the global minimizer T, provided it is initialized close enough to ã - this means that the method requires C' (og() steps to reach an E E-approximation of ã. Inspired by this observation, we seek test-time efficient denoisers that emulate the gradient iteration 44.3 There are two main challenges in realizing this idea: first, we do not know MM- - we only have noisy samples 21,.... N. Second, the optimization problem (4.1 can exhibit subopti- mal local minimizes; to guarantee the performance of our denoiser, we need to ensure convergence to the global opti- mizer. Below, we sketch our approach to these challenges, deferring full construction to Section 6
Landmarks Q: qi E ID for each vertex i = I,..., ,....,,,, M, Tangent spaces T: T, = span(U,) with orthonormal basis U. E RDxx each vertex = :...: M, Edge embeddings 3: fu-v Pr. (g. qu) E Tu for each first-order edge u + U E E², where Pr. (g. qu) U (q. qu)
Based on these objects, we can approximate the Riemannian gradient of yo as grad (4:) = Pr, (q: - 2).
First-order (Gradient) Steps over the Tangent Bundle Graph. The edge embedding fu-v represents direc- tion in the tangent space T., which points from v, and negative Riemannian gradient - -grad (q.) at qu is our desired direction for movement. A very intuitive update rule is simply to move from the vertex ut which satisfies
Challenge I: .M is a-priori unknown. Our approach is to learn an approximate Riemannian optimizer from data. We will approximate the manifold with a collection of land- marks q).-.., q which are linked by a geometric graph G. As illustrated in Figure 3 we will equip this graph with all of the necessary structure to enable optimization - par- ticular, an approximation the tangent space to M at each landmark, which enables us approximate the Riemannian gradient, and edge embeddings which enable us to traverse the graph in the negative gradient direction.
ut = arg max 1000-0311
(-grad[ga) Euno).
(5.1)
The test-time cost of computing a gradient step is O(Dd + d (w)). Here, deg* (u) is the degree of the vertex u. i... its number of first-order neighbors. The ((dd) term is the cost of computing the Riemannian gradient, while the d deg' is the cost of searching for a neighbor of u which maximizes the correlation in (5.1)
Challenge I:: Suboptimal Minimizers. The distance function (xx()) may exhibit suboptimal local minimizers. For example, Figure 4 (left): the point q is a local minimizer of the function y (g) blq q- a=112-
Zero-order Edges and Steps. The gradient method de- scribed above efficiently converges to the near-critical point. However, it may get trapped at local minimizers. To ensure global optimality, we propose mixed-order method which takes both first-order steps, based on gradient information, and zero-order steps, based on function values.
In Section 6 below, we will show how eliminate subop- timal minimizers by appropriately modifying the graph G informally, by adding "tunnels" that allow local descent to escape local minimizers and obtain the global optimum.
5. Mixed-Order Optimization over M
We add an additional set of edges ES, which we term zero- order edges to the graph G. We use the notatior 4 v if and are connected by zero-order edge. As outlined in Algorithm [ at each step, our mixed order method first attempts a gradient step, by selecting the first-order neighbor whose edge embedding is best aligned with the negative gradient. If this step does not decrease the objective value, the algorithm then performs a zero-order step, by choosing
As described in the previous section, we build an approxi- mate Riemannian optimizer for M. Our optimizer operates over collection of landmarks ......, qM- To traverse this set of landmarks, we need to be able to (i) approximate the Riemannian gradient of our objective function So at a given landmark q. and (ii) to choose which landmark a+ to move to next, based on the gradient. The following definition contains the required infrastructure:
"We use Tú, To. interchangeably to denote the tangent space at landmark 4; or vertex i. We also use Tę M when q; E M.
"The points shown in Figure represent the landmarks, which serve as a discrete approximation of the unknown manifold. To- gether with connecting edges, they form a structured domain for optimization. All components - landmarks, edges, and related quantities are learned directly from noisy data via our online learning algorithm described Section 6
*In the language of Riemannian geometry, the &.-+o are in- tended to represent the logarithmic map lo% (4.).
'In the paper, we use u 9 and qu O qu interchangeably to denote the zero-order edge from landmark qu (vertex u) landmark qu (vertex v).
4

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
22:
Data
Tangent Bundle Graph
Optimization
11.....1 NN
Landmarks gi subspaces span(U;)
Figure 3: Learning a Manifold Optimizer from Samples. Given data samples 2 NN (left), we construct an approximation (center) to M which consists of landmarks ....... qM. approximate tangent spaces, and geometric graph G' whose vertices are the landmarks. Right. We approximately optimize over M by optimizing over the graph G.
Local Descent
Local Descent
each landmark q, first-order edges E* and zero-order edges E which have been previously described in Section 5.1 The algorithm processes incoming data sequentially. For each new noisy data point œ. we perform mixed-order man- ifold traversal (Algorithm T using the existing traversal network (Q, E E"). Manifold traversal outputs a vertex which corresponds a landmark q, which locally minimizes the squared distance (p(()) 2 2119 1 The resulting vertex is taken an input to Algorithm
M
M
M'
Test Point xt Local Minjmizer
Added Tunnel
Global
Minimizer
Suboptimal Minimizers
Domain Augmentation
Local is Global
Depending on ae (q:), we encounter one of three scenarios:
Figure 4: Eliminating Suboptimal Minimizers by Adding Tunnels. Consider a test point æ. with corresponding ob-
Inlier: Landmark qi is sufficiently close to x (i.e., l| æll S R(i)). The noisy point æ is denoised using the local model at qi by setting E = q: + Pr. (x - q:). The point æ used to update the local model, by updating the landmark qi (as a running average), tangent space T,, (using incremental PCA see Appendix D). and edge embeddings, setting Eij Pr., (q; q,) Vi 4 E²,
jective function (q) = l|q - x: 2=12- Left: point q is local minimizer of (q) over M. Center: We modify the
domain MM to connect q and æ adding a "tunnel" connect- ing these points. Right: local descent over the augmented domain M' converges to the global minimizer æ.
the zero-order neighbor with smallest objective value:
If l/q: - æ=| R(i), we perform exhaustive search, scanning all landmarks to find q the global minimizer. Based on ||q. - ø|1, we distinguish between two cases:
u arg min Pa (v).
(5.2)
This operation requires us to compute the objective function Pe at each of the zero-order neighbors u of u. Thus, the computational cost is O(D deg" ( (u)). When and deg" (u) are large, the cost of a zero-order step is significantly larger than that of first-order step - this is why our method prioritizes first-order steps. However, zero-order steps are essential guarantee global optimality. In the next section, we will show how to construct G to ensure that the mixed- order method converges to a global optimum.
q: is a suboptimal local minimizer: If ||q. x|| S R(i.). i.e., q: is close enough æ,, we build tunnel i, from q, to q: use q. to denoise and use to update the local model at q.
x is an oullier: No existing landmark is close to We make x new landmark qM, and build first-order
edges M A j when l|qur 9₃ll S Rubre and initialize local model at gMs
6. Learning to Optimize over M
As more samples are grouped into this landmark, the cumu- lative effect of noise diminishes, gradually reducing both the landmark's 's deviation from the true manifold and the error in its tangent space estimation. The threshold R(i) for accepting inlying data points æ is allowed to vary with the number of data points assigned to given landmark qi (see Section and Appendix
The proposed mixed-order method can efficiently navigate the manifold M. However, M is a-priori unknown and only noisy samples are available. We next propose an online learning method (Algorithm D that learns mixed-order optimizer directly from noisy data.
Our online learning algorithm produces a set landmarks Q = { tangent space T; and edge embeddings E, at
By processing one sample at time, the online learning approach distributes the computational cost of training over
5

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
Algorithm 1 Manifolldrraverall
Input: Network G, a E R?, initial vertex f-1 1
while not converged do
g U 9:)
iF arg max j:ibb (g: Ety).
if
1 æll < |1g: ælI then
i 1
Figure 6: Growing Traversal Networks from Scientific Data. Visualization of 2048-dimensional gravitational waves, We show clean samples (orange), landmarks (blue dots), first-order edges (blue), and zero-order edges (green). As the online algorithm sees more points, learns an in- creasingly good approximation to M. Number of training points: Left: 1.000. Middle: 10,000. Right: 100,000.
else
i f- arg min
2 |1a - æll
end if
end while
Output: i
time and ensures memory efficiency, enabling it to adapt to large and high-dimensional datasets.
Algorithm onh.iineeeaaiiiiiffoooattttttaaa
Input: Current network a e ER.
- MamifooldTrreeerraa...aaa if
After seeing enough samples, Algorithm 2 creates a set of landmarks Q, which forms a discrete approximation of the manifold M, along with a geometric graph that captures both the local geometry of the manifold and its global con- nectivity (Figure D). This structure enables efficient and accurate navigation for new noisy sample at test time.
q: 15--- æ112 I _((i) then
Denoise via < +
Update local parameters yi, Tú, else
i, + arg min, و|q x112 if ql.. - x112 S R(i.) then
qi is a local min, add a zero-order edge 9 i, Denoise æ. update qi,: Ti.
else
Create new landmark qM f
Connect it to neighboring landmarks within Rabes Initialize local parameters TM, Eas
end if
end if
Output: = FV
Figure Growing Traversal Networks for Synthetic Manifolds. Growing manifold traversal networks on the Swiss roll and Möbius strip three different times during early training. First-order edges (blue) allow navigation along M; zero-order edges (red) ensure global optimality.
mixed-order traversal is both accurate and highly efficient, corroborating the conceptual picture in Figure 2
We analyze a version (Algorithm 3) of the mixed-ordes -rddrr method, which consists of three phases: a first-order Phase I, which, starting from an arbitrary initialization, produces an approximate critical point qi a zero-order Phase II, which jumps to point qu in a CTM neighborhood of the ground truth ag. followed by first-order Phase III, produces point Dm within distance Cka /d of xt--
7. Theoretical Analysis
Our main theoretical result shows that the proposed mixed- order traversal method rapidly converges to a near-optimal denoised signal. We study the behavior of this method on noisy input æ at + z, with 2; an arbitrary element of M, and and (N, o²). Here, the goal is to produce an output & x xz in particular, we would like to achieve | æ; & ovd, which is optimal for small dr
Complexity of Escaping Suboptimal Minimizers. A key element of Algorithm 3 (and more generally Algorithm [ is the use of zero-order edges (or tunnels) to escape suboptimal critical points. The complexity of this step of the algorithm is dictated by the number of zero-order edges emanating from the point qi,- There is a clear geometric interpretation to this number, which is illustrated in Figure a point q E M is a critical point of the distance function
Our analysis assumes access to an accurate collection of landmarks& Q = {qi..... } c M and their tangent spaces T as well as appropriately structured first-order and zero-order edge sets E' and E - in a nutshell, we prove that given an appropriately structured traversal network,
6

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
ab Rubbes S &2oVV d for some a 2 40. Assumptions F.:: F is minimal collection of edges satisfying the following covering property: for distinct 9. q E
222
if E q Na with
11
1) 2 6 + caoVay diam(M) + log(ō- diam(M)).
there exists a zero-order edge q i q" with q" E BMld' CsTM).
Normal Space q + M
With high probability in the noise z, Algorithm with pa- rameters
q is a critical point of Pe., = 211q - x1 and Paa = = q 221l2 over M
Ra = Rubrs - 6,
Figure 7: Critical Points of the Distance Function. The point q is critical point of the distance (g) 2 1 for any point satisfying x E Ng.M. The vista number S(M) bounds the number of æ for which this is true - i.e., the number of æ for which q is a local minimizer. This in turn bounds the number of tunnels which must be added to ensure that local descent converges to global optimizer. In the example illustrated here, S(M)= = 3.
e1 > Rabrs diim
croad 12 V diai(M) + log(ō- - diamdi (M))..
c2> Gg ma 1ooVd.
produces an output q, satisfying d 22)) S 262 with overall number of arithmetic operations bounded by
Pi (g) = 1 æ - qli3 if and only if x - q E Mg. Hence, the number of (clean) larget points 2; M for which q is critical point is given by the number of intersections of M with the normal space q + M. Inspired by the geometry of this picture, we denote this quantity S(M):
o (ID
e 1og(a)d + (ID+
(diam?
1 +
R8 ) Dx
$2 M (M))
E1
Here, TM is the reach of M, i.e., the radius of the largest tubular neighborhood of M where the projection PM is unique (Federer, 1959). The assumption VvD < CITM en- sures that, with high probability ||=|| S TM. the projection PM (z)) is close to 27 in the geodesic distance d.M
$(M)
max # [MN (q NgM)]. (7.1) QEM
Because Phase I of our algorithm produces approximate critical points, we work with a stable counterpart to this quantity: let NyM = Ng B(0, 7) denote an r) dilation of the normal space at q. We set
The extrinsic geodesic curvature is the supremum of ||i|| over all unit speed geodesics Yt) on M. This quantity measures how "curvy" geodesics in M are. diam(M) is the diameter of M in the intrinsic distance dy. $2 (M) upper bounds the number of zero-order edges per landmark.
(7( = max (( M,, (7.2) QE.M
This result shows that given accurate land- marks, tangent spaces, and first-order and zero-order graphs, the algorithm converges a max k., 1 /d neighborhood of Zyg. which is best achievable up to constant when is bounded. The algorithm admits upper bound on the re- quired number of arithmetic operations. (Dd + e log(a)dd) is the computational cost of taking one first-order step, as Dd comes from projection of the D-dimensional gradient into the d-dimensional tangent space, and de log(a)d repre- sents the cost of comparing the d-dimensional dot product between the negative Riemannian gradient with all first- order edge embeddings, with number of neighbors bounded by ed' log(a)d
Interpretation.
where MtSS, p. r) denotes the covering number of set in metric P with covering radius r. Intuitively, this counts the "number of times" the manifold intersects the dilated normal space N As will establish in Theorem 7.1 this quantity upper bounds the number of zero-order edges at each landmark (i.e. deg" (q)) required for global optimality.
Main Result. Our main result is as follows:
Theorem 7.1. Let M C. D be a complete and con- nected d-dimensional manifold whose extrinsic geodesic curvature is bounded by K. Assume x diam(M) 2 and DD S CITM-
oVD Assumptions on Q: The landmarks Q = (gi...... } C M are d-separated, and form 8-net for M. under the metric d (: ). Assume ō S diam M.
( Nō represent the total number of first order steps taken. ( represents the number of steps on the path from qi (initialization) to qi- Since the initialization could be arbitrarily bad, in this phase we can only guaran- tee decrease in the value of a (q), so naturally diam" diam?(M) (M)
c,6
Assumptions on E²: First-order graph ES1 is defined such that u 2 V E F.1 when I|q.- - gullz S Rubers Assume
7

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
Algorithm 3 101Traversal
racy tradeoff' compared to Nearest Neighbor over the same set of landmarks. Additional experiments image datasets and comparisons with autoencoders for gravitational wave denoising are detailed in Appendix G
Input: Network G, x E RP, RR,RR, E1, 62 R1,
Initialization [Phase I]
while [Pr - 9.)1l2 >G 6 do
-raagg (P Pr. (- qi) - Pr (g= - -2)112
Traversal Network Construction for Various Manifolds. Algorithm 2 grows the manifold traversal network, process- ing one sample at a time and learning tangent spaces and landmarks in the process. Figure reveals the graph con- struction process during early training for the Swiss roll and Mobius strip (intrinsic d = ambient D = 3). The fig- ure provides visual confirmation of the fact that first-order edges (blue) capture local information (clearly visible in the Möbius strip), and zero-order edges (red) create tunnels that help escape local minimizers (clearly visible in the Swiss roll).
end while i + i
in f arg min
9, - 2112 (Phase II)
i <- in (Phase III)
while |Pr 9:) > 62 do
<- arg min (D(O.R.) Pr. (x= q.) Pr, - -9:)112
end while im +i
Output: qim
In addition to synthetic manifolds in RR, we also grow traver- sal networks on high-dimensional real-world data. We learn denoiser on a dataset of 100,000 noisy gravitational waves (Abramovici et al. 1992 Aasi et al., 2015) using the online method as described in Algorithm Data are D = 2048- dimensional, with intrinsic dimension d = 2, depicted in Figure: [ We refer the reader to the Appendix B.I for data generation details.
captures the worst case initialization. The o represents the minimal decrease in each step: since the landmarks Q forms a ō-net of the manifold, each gradient direction is approxi- mately covered, and each first order step have gradient norm at least c by definition of the stopping criterion. On the I other hand, R represents the number of operations from Zu so when
to qen. By construction qi E (M we consider (x: the new objective function, the worst case initialization is 1 and on this scale each gradient step is guaranteed to walk along the manifold, giving us 6-decrease in the intrinsic distance to æh--
Improvement of Denoising Performance with Stream- ing Data. We measure the performance of our learned denoiser on dataset of 100,000 noisy gravitational waves. Figure g shows the training error of the learned denoiser. The training error across the first n. data points is given by
Finally, the D S2 (M) represents the cost of the zero order step from qú the 6i c1-approximate critical point for yPx. to qin the point that lies intrinsically close zg. TM (M) is new geometric quantity that we' we've defined, and it cap- tures how much M intersects its own dilated normal space. Intuitively larger y (M) means one would expect more local minimizes while performing first order descent. No- tably $7 (M) can be exponential in d in the worst case manifold, in which case our algorithm behaves similarly to nearest neighbor search. Intuitively, the parameter 6 (and corresponding requirement 17 on the zero order edges) cuts out a tradeoff between the complexity of the first order phases and the complexity of the zero order phase.
MSE-
1 π
Σ
| - 22.0112
(8.1)
where 2; is the denoised point, and 24. is the ground truth. We plot the theoretical lower bound as o²d and see that the denoiser error decreases, showing potential to converge to the optimal theoretical lower bound.
Test-time efficiency vs. Denoising Performance. We investigate the tradeoffs between performance and com- plexity for our mixed order method, and baselines such as nearest neighbor (NN) search. After obtaining a traversal network (Q, E E²),, we compare using the follow- ing experimental setup. For NN and our method, we search over the same set of landmarks Q. We measure accuracy in mean squared error (same metric as in (8.1)) and complexity in number of multiplications. An important parameter in Algorithm 2 is the denoising radius R(i) which controls the complexity by determining the number of landmarks created.
Tradeoff:
8. Simulations and Experiments
In this section, we visualize the traversal networks con- structed using Algorithm Sapritthm@acrosss across synthetic manifolds and high-dimensional scientific data. Our experiments show that denoising performance of Algorithm improves with increased number of training data, indicating that the algo- rithm effectively learns to denoise. Based on experiments with gravitational wave signals, we further demonstrate that Algorithm 2 acchieess better test-time complexity and accu-
Conceptually, R(i) measures distance between a noisy point xr and the the landmark that best describes Throughout
8

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
Training Ervor Curve
Computational Complexity Accuracy
log of (#Muliplication per sumple)
Manifold Traversal (R constnnt)
Mean Squared Eiror (Tain)
Manifold Traversal (R decreasing)
Neares Neighbor
0.33
MT training
60
ond
0.00
o'D
2.3
0:35
20-
0.30
23000
43000
09000
00000
300000
Number of Samples
0.003
CADS
0.040
0043
0.000
Mean Squared Error
Figure 8: Training Error: Training error decreases with the number of training points. We train denoiser with 100,000 noisy samples with parameters R(i), Rabrs The error curve shows the potential to approach the theoretical optimal o²d.
Figure 9: Test-Time Complexity-Aceuracy Tradeoff of Mixed-order Method versus Nearest Neighbor. Over test set of 20, 000 noisy points, our proposed mixed-orde method achieves better tradeoffs compared to nearest neigh- bor search over the same set of landmarks.
Algorithm 2 the landmark error decreases, and R(i) should be reduced accordingly. Hence, we define general formula for R(i) as follows:
known and only noisy samples are given. The framework incorporates an online learning method to construct an aug- mented graph for optimzzing on the approximated mani- fold, and a mixed-order method that ensures both efficiency and global optimality. Our experiments on scientific man- ifolds demonstrate that the proposed methods achieve superior complexity-accuracy tradeoff vis. nearest neighbor search, which is the core of many existing provable denois- ing approaches. Furthermore, our analyses show that the mixed-order method attains near-optimal denoising perfor- mance, assuming the online learning method produces an ideal graph, and we provide complexity analyses for the mixed-order method under this assumption.
R(1) Vo DDDD o
(8.2)
where the first error term D comes from noisy points 2, and the second term a² D2D/N, comes from the fact that there is distance between landmarks and the true manifold. Initially, a landmark q: is created using one noisy point æ. As more and more points are used to update landmark q and other local parameters at vertex i, local approximation gets more and more accurate, and the distance between the landmark and true manifold should decrease. This is why we divide the error 2 by N;, the number of points used to update landmark qi and other local parameters, making R(i) smaller. Lastly, ad term comes from the error |PMæ 2g 1/2 across the manifold M sec Appendix F
A promising future direction is to establish theoretical guar- antees for the accuracy of the landmarks generated by the online learning method, as they play a crucial role in denois- ing performance. The current learning method dynamically builds edges in the graph as needed. Another potential av- enue for future research to develop sparser network using pruning techniques while maintaining global optimal- ity, which could further improve test-time efficiency. More broadly, we aim to leverage this designed method to study the traversal properties of natural datasets across a wide and diverse range of datasets. Additionally, integrating this method as a denoiser block within signal generation and reconstruction architectures could be a valuable direction, potentially accelerating the entire process.
Figure summarizes test-time accuracy versus complexity of the proposed mixed-order method, comparing it to nearest neighbor scarch. We do this comparison based on a test set of 20, 000 noisy points. By varying R(i) and Rabes (see Table in the Appendix for details), we obtain twelve different networks {[Q;, Tj. E,. FD.. J2 We compare method of network with nearest neighbor search over the same set of landmarks Q,- The details can be found in Appendix G As shown in Figure D manifold traversal achieves significantly better complexity-accurall compared to nearest neighbor search. Figure illustrates that decreasing R(i), as the number of samples N; assigned to landmark qi increases, leads to better accuracy compared to maintaining constant radius.
trade-offs
9. Conclusions
We introduced a novel framework for test-time efficient and accurate manifold denoising when the manifold is un-
9

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
Acknowledgements
Aysin, B., Chaparro, L., Grave, I., and Shusterman, V. Denoising of non-stationary signals using optimized karhunen-loeve expansion. In Proceedings of the IEEE- SP International Symposium on Time-Frequencr and Time-Scale Analysis (Cat. No. 98TH8380) pp. 621-624. IEEE, 1998.
The authors gratefully acknowledge support from the Na- tional Science Foundation, through the grant NSF 21 12085. Shiyu Wang also gratefully acknowledges support from the Chiang Chen Industrial fellowship. The authors are grate- ful for the generous support of Columbia University in the City of New York. The authors would like to highlight the inspirational and community creating role of NSF's CCF- 1740391 grant. The authors thank Davit Shadunts for his contributions to refactoring and organizing the codehase used in the final version of the paper.
Boucheron, S., Lugosi, G., and Bousquet, O. Concentration inequalities. In Summer school machine learning, pp. Springer, 2003.
Brand, M. Fast low-rank modifications of the thin singular value decomposition. Linear algebra and its applications. 415(1):20- 2006.
Impact Statement
Buades, A., Coll, B., and Morel, J.-M. A non-local algo- rithm for image denoising. Computer Vision and Pattern Recognition (CVPR), pp. 60-65, 2005.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Dabov, K., Foi, A., Katkovnik, V., and Egiazarian, K. Image denoising by sparse 3-d transform- domain collaborative filtering. IEEE Transactions on Image Processing, 16(8); 2080-2095, 200,2299,,00000 2007.
References
Aamari, E., Kim, J., Chazal, F., Michel, B., Rinaldo, A.,
and Wasserman, L. Estimating the reach of manifold.
Does, M. D., Olesen, J. L., Harkins, K. D., Serradas Duarte, T., Gochberg, D. F., Jespersen, S. N., and Shemesh, N. Evaluation of principal component analysis image de- noising on multi-exponential mri relaxometry. Magnetic resonance in medicine, (1(6):3503-3514 2019.
Electronic Journal of Statistics, 13(1):1359 1399, 2019. doi: 10.1214/19-E151551. /ttttps:///ooi org/ 10. 09.1244119-EJ1159
Aasi, J., Abbott, B., Abbott, R., Abbott, T., Abernathy, M., Ackley, K., Adams, C., Adams, T., Addesso, P., Adhikari, R., al. Advanced ligo. Classical and quantum gravity, 32(7):074001, 2015.
Donoho, D. L. De-noising by soft-thresholding IEEE Trans- actions on Information Theory, 41(3):613-627, 1995.
Elad, M. and Aharon, M. Image denoising via sparse and redundant representations over learned dictionaries. IEEE Transactions on Image Processing, 15(12):333-3775, 2006.
Abramovici, A., Althouse, W. E., Drever, R. W., Gürsel, Y., Kawamura, S., Raab, J., Shoemaker, D., Sievers, L., Spero, R. E., Thorne, S., et al. Ligo: The laser interferometer gravitational-want observatory. science, 256(5055):325-333 1992.
Fan, C.-M., Liu, T.-.,, and Liu, K.-H. Sunet: Swin trans- former unet for image denoising. In 2022 IEEE Interna- tional Symposium on Circuits and Systems (ISCAS), pp. 2333-2337. IEEE, 2022.
Absil, P.-A., Mahony, R., and Sepulchre, R. Optimization algorithums on matrix manifolds. Princeton University Press, 2008
Federer, H. Curvature measures. Transactions of the Ameri- can Mathematical Sociery, 93(3):418444 491, 1959.
Adler, R. J. and Taylor, J. E. Gaussian inequalities. Random Fields and Geometry, pp. 49 49-64, 2007.
Fefferman, C., Mitter, S., and Narayanan, H. Testing the manifold hypothesis. Journal of the American Mathemat- ical Society, 29(4):983-104) 2016.
Agustsson, and Timofte, R. Ntire 2017 challenge on single image super-resolution Dataset and study. In Proceedings of the IEEE conference on computer vision and pattern recognition workshops, pp. 126-135, 2017.
Fefferman, C., Ivanov, S., Kurylev, Y., Lassas, M., and
Narayanan, H. Reconstruction and interpolation of mani- folds. i: The geometrie whitney problem. Foundations of Computational Mathematics, 20(5): 1133, 2020.
Arora, R., Cotter, A., Livescu, K., and Srebro, N. Stochastic optimization for pea and pls. In 2012 50th annual allerton conference on communication, control, and computing (allerton). pp. 861-868 IEEE, 2012.
Genovese, C. R.,, Perone Pacifico, M., Isabella, V., Wasser- man, L., et al. Minimax manifold estimation. Journal of machine learning research, 13:1263--223 2012.
10

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
Gong, D., Sha, F., and Medioni, G. Locally linear denoising image manifolds. In Proceedings of the Thirteenth International Conference Artificial Intelligence and Statistics, pp. 265-272. JMLR Workshop and Conference Proceedings, 2010.
Vershynin, R. High-dimenssoonll probabiliy: An introduc- tion with applications in data science, volume 47. Cam- bridge university press, 2018.
Vincent, P., Larochelle, H.,, Bengio, Y., and Manzagol, P.-A. Extracting and composing robust features with denoising autoencoders. In Proceedings of the 25th international conference Machine learning, pp. 1096-1103, 2008.
Hein, M. and Maier, M. Manifold denoising. Advances in neural information processing systems, 19, 2006.
Ho, J., Jain, A., and Abbeel, P. Denoising diffusion proba- bilistic models. Advances in neural information process- ing systems, 33:6840- 6851, 2020.
Wiener, N. Extrapolation, Interpolation, and Smoothing of Stationary Time Series. MIT Press, 1949.
Yan J., Wang*, S., Wei, X. R., Wang, J., Márka, Z., Márka, S., and Wright, J. Tpopt: Efficient trainable template op- timization on low-dimensional manifolds. arXiv preprint arXiv:2310. 10039, 2023. Submitted to IEEE Transac- tions on Signal Processing.
Ilesanmi, A. and Ilesanmi,
Methods for image denoising using convolutional neural network: review. Complex & Intelligent Systems, 7(5):2179-2996 2021.
Leohacher, G. and Steinicke, A. Existence, uniqueness and regularity of the projection onto differentiable manifolds. Annals of global analysis and geometry, 60(3):559-587, 2021.
Yao, C., Jin, S., Liu, M., and Ban, X. Dense residual transformer for image denoising. Electronics, 11(3):418, 2022.
Malkov, Y. A. and Yashunin, D. A. Efficient and robust approximate nearest neighbor search using bierarchical navigable small world graphs. IEEE transactions on pattern analysis and machine intelligence, 42(4))824- 836. 2018.
Yao, Z., Su, J., Li, B., and Yau, S.-T. Manifold fitting, 2023.
Zhang, K., Zuo, W., and Zhang, L. Plug-and-play image restoration with deep denoiser prior. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
Nitz, A., Harry, I., Brown, D., Biwer, C. M., Willis, J., Dal Canton, T., Capano, C., Dent, T., Pekowsky, L.,, De, S., et al. gwastro/pycbe: v2. 1.1 release of pycbe. Zenodo, 2023.
Sato, H. Riemannian optimization and its applications, volume 670. Springer, 2021.
Shustin, B., Avron, H., and Sober, B. Manifold free rie- mannian optimization. arXiv preprint 0322:9220,.03269 2022.
Sober, B. and Levin, D. Manifold approximation by moving least- projection (mmls). Constructive Approxi- mation, 52(3):433 4788 2020.
Sober, B., Ravier, R., and Daubechies, Approximating the riemannian metric from point clouds via manifold moving least squares, 2020.
Song, Y. and Ermon, S. Generative modeling by estimating gradients of the data distribution. Advances in neural information processing systems, 32, 2019.
Tenenbaum, J. B., Silva, V. d., and Langford. J. C. A global geometric framework for nonlinear dimensionality reduction. science, 290(5500):2319-2333, 2000.
Venkatakrishnan, S. V., Bouman, C. A., and Wohlberg, B. ald--and-play priors for model based reconstruction. In 2013 IEEE global conference on signal and information processing, pp. 945-948. IEEE, 2013.

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
Appendix
A. Main Claims
Theorem A.I. Let M R.P be a complete and connected d-dimensional manifold whose extrinsic geodesic curvature bounded by
Assumptions on M Assume k. diam(M) 2 and o /VD < 640 T.M-
Assumptions on Q Suppose that the landmarks Q? = {qi....................... qm} C. M are å-separated, and form a ô-net for M, under the metric d Assume 5 S diam(M).
Assumptions on E First-order graph E. is defined such that b E E when ||qu qull2 S Rabrs- Assume Rubrs S 22 / for some 2 40. 64
Assumptions on Ed E is minimal collection of edges satisfying the following covering property: for distinct q. E EQ. q M with
n 2 + + 14 dimmm + log(diam(MM) log(() + log(7),
(A.1)
there exists a ZOE q
0 q" with q" Bmll', 1 TM).
With probability at least 1 4e to (5)
the noise z. the Algorithm 3 witt parameters
Ra= = Rubra
(A.2)
Rnbrs
61 >
+
n: dd)
(A.3)
0.55
3
+16koV (diam(MM (inkovdddddaamMMM + log(a) - log(()) + log(diam(MM)) + log((10))
(A.4)
22 > C max (I, 13ova
(A.5)
produces an output q. satisfying
dm v4)) 2e2
(A.6)
with an overall number of arithmetic operations bounded by
(10diamm (10diam?(M)) ((M) + 2002
Dd + d (1++42
+ kō
+ D x 87 Ter TM
(M)
(A.7)
where (7) follows the definition in Equation 7.2
Proof. With the above assumptions and the combination of Proposition A.3 Proposition A.4 and Proposition A.5 it's easy to show that with probability at least 1 4e- -(5) in the noise the output of the algorithm q, satisfies
dm(q.. (u..).))))) xt) < 2Eg,
(A.8)
and phase and phase III use at most diam"(M)+2+ + ws
steps, and phase II takes most D x $" 1oo
(M) operations.
0.1666
Suppose Sqn C M the minimal set that 160 covers the (q No) M under the metric du((,)) :), with n 2 6 + 5 a (4 (4 @ + 10va). From the definition that (.M) = max (q Nz d :), ),,)) where
p(S, denotes the covering number of set S in metric with covering radius r, we have | n7( + N2) n.
M).dM(; 160 TM) < $"
TM
12

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
For any q E 2, the landmark Q d-covers the manifold, it d-covers Sq We denote the minimal set of landmarks that 5-cover Sq,y 2s. Then for any q' 2. q + Ny. there exists point Sqn such that dm( 100 TM- Since E Sq. there exists landmark q" 2s such that (s, q") s 6.
Therefore, for any q' + Ng there exists q" E 2s such that
1
V2
1
dmld', q") ddldd dd((, S 160 TM +ō5
TM +
TM S
TM
(A.9)
160
40 * 64 * 640
80
where we used 8 Ruize, a 40, Rabrs I Lo ovd. D, and ovD S 640 TM assumed in Theorem A.1 from the third-to-last step to the second-to-last step.
a
As a result, the set {a + q" Vq" 2s} satisfies the covering property in the assumption on E.. Since E is the minimum collection that satisfies this covering property, the number of zero-order edges at q, i.e., (q) satisfies
deg"(4) s Ka 9 q" V4" E [ - 1 S 8" TM
(A.10)
And we note that projection of the gradient onto the tangent space takes the cost of D * number of operations, and choosing the first-order neighbor takes the cost of d * maxq. F The number of arithmetic operations of zero-order step is D * max deg" (q), where D comes from the Euclidean distance calculation, and max deg" (q) is bounded by the defined geometric quantity $" TM (M). Combined all of terms above, we end up with the bound on the number of operations performed by our algorithm.
Fact A.2. For manifold M with reach TM and extrinsic curvature bounded by K, we have
TM S 1/k.
(A.11)
See Proposition 2.3 in Aamari et al. 2019). We used this fact directly in the following proofs.
Proposition A.3. Let M C TRD be complete and connected d-dimensional manifold whose extrinsic geodesic curvature is bounded by K. Suppose the landmarks {qu} are d-separated, and form a ô-net for M, and that the first order graph E
satisfies u 1 v E¹ when l|q.- - qulll S Rubra. and that 406 S Rubes S TM. Assume S diam(M) and x diam(M) Z 1.
Then with probability at least
(A.12)
in the noise z, the first phase of first-order optimization in Algorithm 3 with parameters
Rs Rubrs - 8,
(A.13)
Rnbrs
1 >
+ diam
(A.14)
0.55
3 3
+ +16ka Vd diam(M) + log(a) - log(()) + log(diam(MM) + log(100))
(A.15)
(A.16)
produces qú, satisfying
grad[px (qth))))(( = |Pr,, (x q.1)ll2 S
(A.17)
using most
diam diam?(M)) + D
(A.18)
0.1375c.0
steps.
Proof.
We can bound the total number of steps by dividing maximum initial distance by the minimal distance decrease over each first-order step.
13

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
We note that
So (o(())) 11:,0 - 2:12
< 1:000 221l22 2 + ||
(A.19)
diam diam² (M) + ||
We let E be the standard unit variance Gaussian variable, for any 0 < t < 1/2, we have
P||| F|| 2 20² = =[1 > 2D]
= =P(cAl&1 2 2
(A.20)
s eaD
e-2n 2:17
(1 21) 9
where used Markov's inequality from the second line to the third line. In particular, can pick t 1. so with probability at least 1 - - 2 in the noise z, we have
Φa (a(gx) S (M) + 20 D.
(A.21)
Now we will analyze the decrease over each first-order step from u to at. We have
1
(a((t))) - (g
= (||x= qut 112 ||0 - 12)
2
(A.22)
1
2 1qu11 - qu.12 (Pr. (x Pr. (q. qw)) - (PN. (x - qu),PN, (qu -qw)).
We apply Lemma B.1 to bound the first term and Lemma B.8 to get a high probability bound on the last term, setting ( = 30
Next, we apply Lemma B.3 and Lemma B.4 to bound the second term, which dominates the decrease in the values of the objective function after taking a first-order step. As a reminder, the step rule Algorithm is
and
ut = arg min Pr. (x - qu) -Pr, (q. =4))l2
(A.23)
bb
We observe that before phase in Algorithm to
terminates,
|Pr, (x: - gw)ll 2 > R2 holds. Then the step rule is equivalent
Pr. (a: Gu) Rs PT (q. qu))
au))
at
arg min u-v
(A.24)
|rr (a: qu) 1|2
in which we have
(a--a) Ru
Ra. Applying Lemma B.3 there exists u 1 E'. such
|Pre (x- 2
that
|P (x- (e-9u)ll Ra - Pr. - qu)
Pr, (w-qa)
I 8 + 2 RR From the construction of this step rule, we have
1
Pr, (w-qu) (m-,,
R2 Pr. (qut qu) <
Ra Pr. (g. gw)]| S 5 + HRR Thus when in # qu qu): Pr, (q. qu)) 2 0.55||Pr, (ar (..) |l (q. qu) Il2.
Pr, (w-qu)
Pr., (u-qu>ll
applying Lemma B.4 we have (Pr, (ar
Combining all the above results, conclude that with probability at least - c 1o-- in the noise z, we have
2 < Pr. (qui qw)ll 0.55 (x qu) 1221 (q.1 qu)ll2 + x(diam(M) + v20 E + 3oVdd (g.. -wwll
2 3
palqu)) Px (g.)
(A.25)
14

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
Given our assumption on e and applying the bound of |*| in Lemma A.3 together with the assumption that diam(M) and h: x.diam(M)) 1, it follows that before Phase ends, have
0.55 Pr. (x - qu)ll2 > 0.55c1
2
8
2R
+
dM)
3
3
+ +16ka Vdy (diam(M) log(a) log(o) + log(diam(MM) log(100))
2
8
> nRbr
3
diam(M)
3
+ M + log(a) log(6) + log (ciam log(100)
2
8
nbb
diam(M + 8Kσ d SKO / log |E|)
3
2
8
> R
(diam(M) + o / log E + 30 30ve)
3
3
(A.26)
together with Prr (qu+
an) 12 S l1 - qu S Rubesi then we have
0.55 Pa (g(()u)) Pax (qn) S - s- Prr (gut - qu)]l2||PT_ (x - q.)]l2-
(A.27)
In the following, we develop a lower bound for ||Pr, (qu1 - qu))l2 Let y [0, 1] + M be a minimum length geodesic joining qu and qu+ with constant speed d qu+ ) where 7(0) qu 7(1) qu+ Then we have
|rr (qut qu)ll2
Pr. (7(1) 7(0)
Pr. (fr }(a)da) )ls
((0)
Pr. (b)cdaa
2 11Y(0))12
Pr. (b)
a=0 b=0
2 I+x(0)11
Pr. (b))lb))22 dbda
(A.28)
6=0
2 11Y(0)112
K x dbda
0=0
d
kdutngutt q.)
2 dlu(qut,quu)
w 3
where in the third line we' we've used the fact that (() lies in the tangent space of gu. in the forth and fifth lines we applied triangle inequality, and in the final lines we' we've used assumption that d. (g qu) TM and the landmarks 5-separated.
Plugging this back into Equation A.27). we have
0.55
-0.55
Pa (g
Prr (x.
qw)ll2 <
8c1-
(A.29)
2
4
Lastly, combining this result with Equation
A.2 yields the desired upper bound on the number of iterations.
15

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
In the following proposition, we let
M
(A.30)
denote the 17-dilated normal space:
N {or RP |P Mul2 5
(A.31)
Proposition A.4. Assume 8 v diam(MM, xdiam(MM and ovD 640 TM- Suppose for every a E Q and every distinct q' q + M with
1 E1 +ō 140 diaammM))) + log(diam(M)) - log(o)) + log(7),
(A.32)
there exists ZOE q q" with q" E BMll'' 1 TM) Then, with probability at least 1 2e 2 in the noise z, whenever qú satisfies
80
[P mla 5 5
(A.33)
the second phase (zero-order step) produces qu satisfying
d 23,5 0.1/K.
(A.34)
Proof. From Lemma A.2 we have
Q < (1 + 41 diam (laaaa)))))))))))
(A.35)
which gives us that
log |0| < dlog
( 41+4 diam diau)()))
(1 8- diam(M)e dhaum(M)) (eiamm)))
< dlog
(A.36)
< d (log (76-1 diam diam(M) (M)) + x diam(MM)
where we used the assumption that d < (Ma and x diam 2 from the first line to the second line. Together with the assumption on 7), we have
n n + (4v
(4ylog log
O 10v
(A.37)
Under these conditions and the assumption that o DVD D least 1 2e - in the noise, qin = arg min 7':9; 9 llq' x satisfies
640 TM. applying Lemma C.3 conclude that with probability
1
1
1
dm(az, qmm) - 20 TM
TM + +6 -
TM + Rubrs S TM + TM = TM-
(A.38)
20
20
20
20
10
Proposition A.5. Assume o D S tdd TM- Suppose the landmarks {qu} are 8-separated, and form a 8-net for M, and
that the first order graph ES satisfies u + E when ||q.. - 400l2 S Rubess and that
V2
408 < Rubrs S ovd.
(A.39)
64
Initializing qi E (MMxx, with probability at least
10
(A.40)
the third phase of first-order optimization in Algorithm with parameters
Rs, Rubrs 5,
(A.41)
16

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
22 Cmxx (N, 1oovdd
(A.42)
for some C' > 0, produces qsu which satisfies
dm xz) S 2c2.
(A.43)
using most
8
(A.44)
kō
steps.
Proof. Let
qar = q" ".."".".. .².....
(A.45)
denote the sequence of landmarks q¹ produced by first order optimization in Phase III. Let j. E U denote the number of iterations taken by this phase of optimization. If the algorithm terminates at some finite j., we have
P 4.. (a q²x) > S E2.
(A.46)
Below, we will prove that indeed the algorithm terminates, and bound the number of steps j. required. To this end, we will prove that on an event of probability at least
La Tod
(A.47)
the iterates o' (j = 0, 1, ,.) satisfy the following property:
d xx) S max
cıjö, Ci max 1JoVd
(A.48)
10k
This immediately implies that there exists C2 such that for all
C2
j
(A.49)
the iterates q¹ satisfies
dm(4 .x,) v C1 max(R: Ilovd.
(A.50)
Step Sizes. Our next task is verify AA488.. We begin by noting some bounds on the step size dm - construction, for each j,
By
V2
l 4'll2 S Rubrs S oVd.
(A.51)
Since we know _ 2 TM. D 2 d, and we've assumed TM 2 640g we have
V2 Voo,
Rabrs
min
TM. 200
(A.52)
64
Since q', 1/ .M and || 1 q21l2 s TM. applying Lemma
B.5 we have
V2
1
dn(q +1 qq)) S 2| q'1l2 S min
d
(A.53)
32
100k
From Lemma A.5 take / = 2/2 odd, with probability at least 1 - e io the random variable
T max
sup y JcBBulee11//hhee7,MMMMM
(0,2),
(A.54)
satisfies
/2
Tmax 2 4
oodd
(A.55)
which gives us /2 Lo < Tmax. Hence on an event probability at least 1 e de, for every j.
V2
1
Tmax 1
d1 q²) < min
min
(A.56)
32
100k
8
100k
In particular, this implies that the condition on the step size in Lemma D.7 is satisfied.
17

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
Radius of Decrease.
From Lemma A.4, with probability at least 1 -- Tmax satisfies
T max S C2 max(K, 1oodd
(A.57)
and hence the distance condition Lemma D.7 is satisfied whenever
C max(k, 1oovd S dm(p x2)) S
(A.58)
10k*
Proof of Equation (A.48). We proceed by induction on j. For j = 0, 9a = Tu E (M Tox) and so A.48 holds.
Now, suppose that (A.48) condition holds for iterates 0, l.....j - 1. By Lemma D.7 if
1
C. max((n,, dmll' (alllaa xz) S
(A.59)
10k
then
dm 2g))
d xgg) :
(A.60)
d -1 , -22
(A.61)
1
10s c2(j -1)6 c2j6
(A.62)
1 c2jō.
(A.63)
10k
On the other hand, if d (q" .x))= < Cs (Kc, 1 Jovd, we have
dmll' oz)
v d a.) + duld.g'
(A.64)
V2
s Cs max 1lo/d+
ova
(A.65)
32
Co max 1lovd.
(A.66)
Combining, have
d S max
o2j8, Co max (x, 13ova
(A.67)
10k
and A.48 is verified.
Proof of Termination. We next verify that under our assumptions on e2, the algorithm terminates. For an arbitrary point q (a 1/k), let (1l) denote geodesic with (00) 3tg
((1) = q and constant speed d (2 q). Then
|TaMi(2: - 9)112 = Pramo(o)+ + S /"
(b)
6-0
(6(0) [ S Promm(b)abula
Ja=
| + +|I"
Prove(b)dddda
===
(A.68)
s dd q)
PsaMo(() abda
a=0
s ddu q)
(2 q)dbda
Ja=0 b=
< ddn(0 q)
kedh (x), q)
dm q). 2
18

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
Comparing this lower bound A.48), obtain that for any 62 cC max(k, (,, loydd after at most
(A.69)
10c2kd
steps, the algorithm produces point q satisfying
Pr... M(2 q"))l| 5 E2.
Pr
(A.70)
and hence the algorithm terminates after at most 10rgnd steps. To be more specific, Lemma D.7 gives 02 algorithm stops after at most xā steps.
80 so the
Quality of Terminal Point. Finally, we bound the distance of qin q to æz By reasoning analogous A.68 obtain that for (x 1/x)
1
PraM(ax - و)](2 2 _dv(0z..).
(A.71)
This immediately implies that
d ) s 202.
(A.72)
claimed.
B. Phase Analysis
Lemma B.1. With the assumption Rubes
TM for any qu qu M and u + Ed, we have
4 1Prr (qu qu) 112:
qq 2u112 - 3
(B.1)
where Tu the tangent space at qu E M, and Pr. is the orthogonal projection onto Ta.
Proof. For the self edge u + u E E., it's easy to show that |/qu 9. = (q. q..) 1 0.
Now we consider the situation when - E (u * v). By the theorem 2.2 (Aamari et 2019) and theorem in
(eederer 1959,, we know the reach TM of the manifold M satisfies
| - Lo 10
TM =
inf E. P|, (qu qu) 112
(B.2)
where N₂ is the normal space at qu E M, and PN, is the orthogonal projection onto the N...
Thus, for any u 3 u E (u & v), we have
1g qu 11
TM S PN. (qu qu)
(B.3)
By the rule of connecting first-order edges, for any edge + U E.,, we have |1 - qull2 S Rybrs-
By assumption, Rabs I TM, thus for first-order edges u + v(u # v). we have:
l1qu qul $ Rabes
< TM
(B.4)
||gn 1u11
2 PN. (gu qo) 112
Square both sides, we obtain:
1g. q. > 4 (q.. q:) l12-
(B.5)
Since the tangent and normal components are orthogonal, we have l|q,. - qu.11 = P| (q. q.) 113 + I|,. (q.. qu) 113. Therefore, we have:
Pr, (g.. qo) 12 3 NN. (g.. qo) l13
(B.6)
19

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
Consequently, have
l1qu --.l2 Prr, (qu. qu) 11 PN. (qu qu) 11
- Prr, (qu qo) l + 3
Pr. (qu qu) 1
(B.7)
= Ill (q. go) qn) 112-
This completes the proof.
Lemma B.2. For any w: E B(qu, Ra) n,M there exists U u:u : E E such that
11;; qu S 6.
(B.8)
Proof. Since the landmarks form a 8- cover of M, and Rabes = a ó(a 2 40), there exists v E V such that l1q. wy 212
S
8= Rabes-
From the triangle inequality, we have
1u qull2 $ 11q. w:l12 + 111, qull2
Rybrs + Ra
(B.9)
Rybrs + a Rybrs
a
a
Rubrs-
From the rule of connecting first-order edges, we know + v E EL, This completes the proof.
Lemma B.3, For any w E Tw. with ||ll|| I Rai there exists U : u 1 v E E such that
1
w Pr, (qu qu) |l2 S 5 +
2 R
(B.10)
Proof. Consider constant-speed geodesic 7 [0, M, 7(0) qu: -(0) with |wi|2 I Ra. Let 7(1) w.
From the fundemental theorem of calculus, we have
+ f' x(t)dt.
(B.11)
Therefore,
1|0;
qulll
7()dd
< 1
[|x(t)]
dt
(B.12)
||
< R.
This means wn E B(q,, R,). By lemma B.2, there exists v. 1, E E!, such that ||l gull2 1 8.
By fundamental theorem of calculus, we also know
(11) x(0) [ 7(t)dt
1=
- + [ (110) + I' {(s)ds) di
(B.13)
==
=((0) + + + (s)dddt.
20

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
Then have
w; qu / I"
{(s)dsdt.
(B.14)
1=0 o=0
Since E Tw we have
TPP (Fr ((s) ((s)dod()
w Pr. (w) = Pru (wy qu) - PT.
(B.15)
Hence we know
w - PT. (q: qu)ll2 = Pr. (w: - q..) - -Pr. ( [ (())ssdt)
Pr, (q. qu)
1=0 ==0
Pr. (w: -qu) -qu)-Pr -Pr (f l' is)
1 1|0g qull2 + -1111/
{(s)dsdt
1=0 ==0
(B.16)
$ 8 +
(+ss)
1 6 +
k
2
5 RRa
2
Lemma B.4. For any Qu E M and x + qo let u + W E² satisfies:
Pr. (x qu)
Rs Pr. (g. qu) 5ō+ nR
(B.17)
Prr, (x qu) 112
Then we have
(Pr. (x Pr., (g. -q)) 2 0r5 (x qu) 11a|1Pr, (qo - qu) 112.
(B.18)
Proof. Let 87 8 2x Given global constraints that 1 Rubss 2 40 and Rubes S TM S 1/k.
5T 1 Rubes + }xx(1
1 R2
R₂
(1
R
1
+ x(1 Pahes
a(1
1)
(B.19)
(1 1
5
From the assumption we have
Pr. (xr qu)
Rs Pr, (q. - qu) 5d..
(B.20)
Pr. (x qu) ll2
Square both sides of the equation B.20 we have
R² + Prr, (g. 9n) 113
Pr. (x - qu)
Ru, Pr. (g. qu)) )
so.
(B.21)
| (x qu) 1|2
21

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
Then have
Pr, (a -qu) [rrr (x -qu) ll
Ray Pr. (g. qui)
R 07
Pr. (q. qu.) l
2
(B.22)
V Rh 87.1Pr. (q: Qu.) 112.
Therefore, we have
of R
(Pr, (x qu), Pr. (q. - -a)) 2
Pr. (ar qw) 1121Prr (g. qu) 112.
(B.23)
Substituting our result from eq
B.19 (o) eq (3233) we have the following inequality:
(Pr. (x qa), Pr. (g. -u)) 2 0.55 (æ qu) I1al|Pr. (g. qu) 112
(B.24)
Lemma B.5. qu: qu E .M l|q. -ulla TM. have
dmlquu qu) S 211qu. qo 9ull2,
(B.25)
where d .) is the intrinsic distance along the manifold.
Proof. Let q: = qu t(q. qu), [0, 1]. From Theorem C in (Leobacher & Steinicke 2021
know
d
dl Pulad (I l1 PMlla:l) -1 PT PromiajMMaa. qu).
(B.26)
Therefore, we have
Pmiqille
$ (I - PaMlael)) Plppl Ma -u)ll2
dt
|1g. -qull2
1 k/q 10-0-Mpp PMMlqell2
11qu - qull2
ad(qr,.M)
119. - 4u112
$
(B.27)
min(
11::
qu 2. l1. 1
qo qul12
S
quil2
q..
-uule
1 KTM
2 q.
where in the second line we've used the property that Vn, |[T(()]]] S s||m]l,, and in the last line we've applied the fact that TM S L/K. Then the intrinsic distance along the manifold is
d
dm qu)
<
-
Pm
Anl4illladt
dt
1=0
(B.28)
21|g= qull2dt
t=u
211g.
qu1l2-
This completes the proof.
Lemma B.6. For any qu, qo E M, we have
PN.. (q. - -w) l12 - nddilqu. qu).
(B.29)
22

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
Proof. Consider the geodesic 7 [0, 1] M CDD with constant speed ||0||2, where > (0) -ur 7 (1) Qu-
Then the
intrinsic distance between the qu and qu is:
d qu) -
110|/2dt = 1
(B.30)
1=0
From equation (B.13) and the fact +(0) E Tus we have
[PN.(v(1) - 11.1-// L(e (
(B.31)
1N.. (9: -4u) 112 = 1P (1) - ( (0))l22
'' 3 (s) dsdt
PN.
2
7 (s) dsdt
1=0 ==D
I1 (s) 11adst
(B.32)
x||b||2dsu
1=0 6=0
x||1012
ni ( (qw. qv).
This completes the proof.
Lemma B.7. If qui Qo E .M and ||q. 2ulla S TM, we have
8 1:|Prr. (g. qw) 112
I1PN. (qu qu) 112 3
(B.33)
Proof. Given qo E MM and l|q, qo 12 S TM. from lemma
B.5
we know dM qu) < 2
qu - 2u112. From lemma
B.6 we have IP, (q. qu) lle I 1nd (qu. qu). By lemma B.1 we have l|qu qu I P (qu qu) 112 Then we
have
1
PNN, (q. qu) 112 S
Rid
(qu: qu)
2
2n 4u
qo l12
(B.34)
8
Pr. (qu. qu) 11..
3
This completes the proof.
Lemma B.8. For any t > O, with probability at least
20 in the noise, for any qus qu M and u 4 E!
12
(PN. (xc qu), PN. (q. qw)) S 8 x(diam(M) + 22 log E + P), (g. q.)
(B.35)
Proof. As 3 v EL, we have ||q.- S Ruhrr S TM from the construction of E We decompose the left hand side in equation (B.35) as follows:
PPN. (x qu), PN. (g. -q.)) (PN. (x: qu), PN. (q. qu)) PN. (g. qw.))
(B.36)
23

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
From lemma B.7 have [P, (g: qu. ) l12 S E (g. Qu) 11 Then the first component the right hand side can be rewritten
(PN, (#yg qu) PN. (g. qu)) S a4 qullal|PN, (qu (o.--a))
8
(B.37)
diia &ddiam MIlPr, (q: qu.) 12
3
Now consider set of random variables with
Xy (2.11) DEV.
(B.38)
PN. (g. qu)
qu)
Yu + E² Vu,rev
y
PN. (q. qu))l2
Because 2 ~ O Xy follows the distribution Xy ~ NO, g²), and y is a Gaussian process. We first bound the expectation of the supremum of this Gaussian process (uupwyy Xy1 by starting from
e e' pey X=1 = Bit supyey Xy]
$ Ble suy Xx]
|
(B.39)
$ Ele" xb
i=1
= Y le 20
AA > 0.
Take logarithm of both sides, we have
E[sup x,) S log |
o²t'
(B.40)
yEy
2 log | the right hand side of equation (B.40) minimized, and we obtain
When t'
E[sup Xyl S 220 [Y]. yey
(B.41)
By using BorelI-TIS inequality (Adler & Taylor 2007 for any f >> we have
P(sup Xy
E(sup X 1) 6 yey
(B.42)
wEY
This implies
(-(22) 2, PNN, (gu qw)ll2/
PN. (q: qu.)
+2
Elsup Xyl St) 1
6202
(B.43)
wEy
Therefore, with probability at least 20 we have
- (2, - qu)) 5 PN (go qu) (2) Xy] + t)
DEY
< PN (q. q.))ll(V220)) Tog Y +
(B.44)
xx1 Pr. (q. q. q..))l(( log Y t).
by lemma B.7
22 20
Plug equation (B.37) and equation [.44)). with probability at least
we have
(PN., (#: qu) PN,, (q. qu)) (z, PN. (q. qu))
< (PN. (xt qu), PN., (g. qu)) + sup (z, (N. qu))
(B.45)
8 (xdiam((M) + 22 log Y + 1) Pr. (g. qn)ll3
< 3
We conclude the proof by noting that Y E
24

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
C. Phase II Analysis
Lemma C.1. Given noise vector -iid (0, )²), lel H = maxgeq || Pr.M=/| Then, with probability at least 1 6- T we have
1 a ( (4vlog [Q] 100V))
(C.1)
Proof. For any landmark q, we define set Sq {0 E M ||||| 1). From Corrollary 4.2.13 in (Vershynin 2018),
know that for any 8, Sg can be 8-covered by at most
1+122)
= =(1 (1+ ) points. In particular, we can choose d = 1 and
672
let Cg be 1/2 cover of Sg such that [Cyl S 5t.
We let SQ
Uq and Co UqeQCq. Then, we have
H max (u, z) uESQ
(C.2)
< max (v, 2) + H1 wcCq
(C.3)
2
(C.4)
this implies
2 2 max (v, x²) cCCq
(C.5)
Let liz)) max (u,z). and since it's 1-lipshitz function in z, by applying gaussian concentration inequality, have
(1((2) - (((2))-(((2))) 2 Se
(C.6)
We then bound its expectation. For any / > 0,
[B]h(z)) s B[ctth(=)l]
Ele max.eco (1,2))
s Σ Ble
(C.7)
vECq
1Coletote
Take logarithm of both sides, have
log CCal o2t
E [[h(2)] <
+
(C.8)
t
2
When 6= /2log (Col
the right hand side of equation C..) is minimized, and we obtain
E[h(2) v20 log Col v20 5 log Q|-
(C.9)
Plugging this result back to C.6 we have
P (M(z) V2o / /logg 5 + log Q 2 8) < 6 20
22
(C.10)
Picking s = 30 /d, this implies with probability at least - - 3, we have
(v. 2) = h(2)( s o (V(2log 5)d 2 log [Q| + ++3V) s (oo/))/oV//00) (V/2l0 [2] +Vd)
max BECq
(C.11)
Plugging this result back C.5 have with probability 2 -
H < (2 log Q1 + 10vd)
(C.12)
25

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
Lemma C.2. Suppose for any landmark q' E q + No with
n n 4 4olog|/1 +
(C.13)
there exists zero-order edge - q', such that
d' E BMil"m cATM),
(C.14)
where ó is the covering radius for Q, e > O, and ca S T0
Then, for æ 2; + 2, with probability at least 1 1-6 in the noise z, the following property obtains: for every point q
such that E q Ng. there exists zero-order edge q o q"d for some q"" Ba CaTM 5).
Proof. For 2 z 2 M, we have
PI, - cc
(C.15)
By the covering property, there exists q" E Q, such that
dm(#;; q²)) S
(C.16)
Since
Pr. (x - 9)112 2 Prr (q" 9)1l2 Pl, (a); - -d")ll2 - -l|Pr, =1,
(C.17)
we have
|| Pr, (q" -2)112 - Pr (a: q 2")l22 Pr =|12 S.
(C.18)
Together with Pr. (z:: 9²) S 10: 4'll2 I 6. and Lemma C.1 then with probability at least - e we have
22d
Pr.((' --112 56+0+
(C.19)
S 17.
By assumption, there exists a zero-order edge q 3 d' such that q' E BM(d" . Then
dmld', x3) s d q²)) + dx((""
(C.20)
S CTTM +
Lemma C.3. Assume oVD S CITM for some C1 S 640 and for any landmark q" E q + No, with 2 6 + 5 +
4 (oglog Q 10va). where 5 is the covering radius of Q and 0, there exists zero-order edge q 9 q' such that
q' (m CMTM). where ca S 40' Then, for any noisy x H, + where E q + No with probability at least dd in the noise, q" arg min "'gg..g' llq' æ112 satisfies landmark q" E BM( (2ca + 16G))T + 25)
1 2e
Proof. Given the assumption, lemma C.2 guarantees that with probability at least - 2 there exists landmark q" and a zero-order edge q - q"", such that q" E (B CITM + 8). Since q" = arg min q' "g' l| - ælly. we know that
l|q" - - I ll x1/2.
(C.21)
which is the same as
||q" - By - =2|2 S 11q" 2g =112.
(C.22)
From triangular inequality, have
l|qa 2zl12 22 I I1q" 12 + 2|12112
(C.23)
N = (v R | 5m)
26

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
12
Since g(z) |||1| is -llisschitz function in and |||| - ovD, then with probability at least 1 e 2n?
we have
2 5 SVV tt.
(C.24)
Take t Do then with probability least 1 c-
2p. have
||=||2 S 4ov S 4C1TM,
(C.25)
which implies with probability at least 1 e 28, we have
l1q" -Dall2 - 11"" 24l12 + 80ITM S (c4 -81)MMM + SM.
TM.
(C.26)
The last inequality follows from the conditions c₁ 1/40, 1/640, Rabrs/a S TM/40. Together with the fact that on this scale (æ q²) x 2||q" 2z 12, we have
dm 9') 9') (2c4 + 16c))TM 26.
(C.27)
D. Phase III Analysis
Lemma D.1. Consider the first-order edge u 1 v. Let E.. = Pr. (q. -q)) denote the edge embedding, where Pr., the projection operator onto the tangent space Tu of the manifold M at landmark qu. Let y [0,1] M be geodesic joining qu and qu with constant speed |l1|2. where 7(0) qu, 711) qu- Then, for all E [0, 1). we have
Ewvl12 l12 - Rdd (qu. qu). IIx(t)
2 Mid
(D.I)
Proof. From Taylor expansion, we have
qu = qu + {' Haadda.
(D.2)
a=0
Therefore E.o- Pr. - raa)aa Then
27

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
7(1) Pr. [ i(a)da)
[|((1) Eav 2|2
a=
7(0) /" 7(0)db- - -rr. f' (1(0)
[ 3(0)db) da
=
==
10-
I 7(b)db
Jo-o I"
Pr. (bbddbda
h=
2
'' 7(b)dbda S.'o (f
-f Pr.3(6)(bb) da
Pr. (1))66))6))
PN.. (wbdd
Pr. (bbdbb))bb
da
b=0
bbt
1 bim Pb)j(b)dbb)) da
PN. (b)db
(D.3)
+++ |a +1)x:|10122 da
[2t a) da [ da <||0|1
a=0
a=t
(2t²
+ 1/4 1/²) x||0||2
2 +²
x||e11
3
2 x|10113
2
Lemma D.2. For any and F4 y M, let
T Tima
sup ICB
(0,2),
(D.4)
Then if dy) S 1/k, we have
|| log, grad[pa](1)) (3) < (Rdu xx)) + Tmaxx
(D.5)
Proof. We first decompose the left hand side into
|| logy x; - grad((p=(())))
logy Dy ( (1))21
(D.6)
< logy x; + PryM (x: 8)112 + |P
Consider a geodesic n [0, 1] -> M with constant speed
||0,,12. where my() y. (1) 24. then we bound the signal
28

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
term (first term) of the above bound:
--logy 21 + P - -y)12 -n(00 + PraM S ri(a)da)
2 +
())) + Proso M [ (i(0)
[ 0=
r((b)d)
da
PE
n(b)dbdaa
a=0 b=0
(D.7)
[((b)l22 dbda
b==
11 1id
a=0 bo=
2 n 0z:)
Since ( 1/K), we have
|PrMMæll2 S T max.
(D.8)
Combining the above, we end up with the result.
Lemma D.3. For any point z and Ty y M, les
T Tmax
sup y /cNnx
(0,2),
(D.9)
fd 1/k, then have
gradl (1))l2 S dd.(v.x;)) + Tmax.
(D.10)
Proof.
(gradl(>> (1))l2 PT (y - x3)12
(D.11)
S
$1| Pry.n(y a;)1l2 + PT,
It's easy to show that Prym(( =200l22222222222 - dnly x.). Let
T Tmax-
sup /
(0,2),
(D.12)
then we have
ProM=ll1 I Tmax.
(D.13)
Combining the above two bounds, we end up with the desired result.
Lemma D.4. Let : [0, 1 M be a geodesic in a Riemannian manifold M. Take any initial vector vo E Ms, and let ve be its parallel transport along up to time t. Then
|| - voll2 < 3xt 3nt|/oollallil11.
(D.14)
Proof. When paralleling transport vn E M along the geodesic Ç, we have
d v. 11(ve. ((t). dt
(D.15)
From fundamental theorem of calculus, we have
Uo
I1(va. E(a))da.
(D.16)
Jazo
29

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
From above and applying Lemma 8 in Yan* al. 2023 we have
1 vol12
l1 (la))da
[l(var t(a)) 11 da
(D.17)
3xl|waollll1lladd 3nd vo a| Ś112-
Lemma D.5. Lety [0, 1] - M be geodesic joiniig qu and qu with constant speed, where y(0) = qu; ((1) = qu- Then, for all t [0, 1]. we have
M - Mlypo I 33/2kdl//ll
(D.18)
Proof.
|| ProooMMlop
sup
(PracsM PTy(orM) 2ll2
|w||==]
PPaao P)) (la + w1 l|
sup
==
(D.199
(PTxas)M PT)o))M) w 1 ++|[(Ppg || Procosm) w l12
sup
w 1==
Prammm211 - willl + ||lll++||rrrpmp || 1|,
sup
w 1=
where W|| PT M
W1
P 7:o) M W.
Together with Lemma D.4 we bound the first term || Mr) 1l l22
Pr P
w
= min || - 21ll|
h
$ Io 11 - w1ll2
(D.20)
< 3xd 3n1//2/llllll//|
Here Io is transport operator which transports vector in M to the Ty(1) M along the geodesic
We next bound the second term PI Prec 2
Pr (r MW
112
Pr Pr 2oo ww
< |/ ll2
P Prxce P Tynny
|
Pri M Ps PrecessM
||w]l|
sup
P Pr M
||
||will
sup
P (r
(D.21)
|| m
I.uET
||will l12
sup
|1(I - Proco) ull2
|. M
||w
ll2
sup
min
1 2el2
( M hET M
<
||wllla ll2
[ ( u/l2
sup
< 3kt ||||||| Bewlwllee 11211
30

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
Therefore,
|| M 11ll22 + P Prac ||w]|==1
sup
sup |
3xd//5122(111 + l/wallla
sup |
3v 3
(D.22)
-3v2xtll
Hence
MT - Plyoo S 33
(D.23)
Lemma D.6. Let y [0, + M be minimum length geodesic joining and qut with constant speed dm qu+) where 7(0) qu 7(1) = qut- Suppose for any I E [0, [0, d dM)()()), (b) S 1/8, then, we have
0.55
1
(grad[(ex) Suut) S 2
-T mmax dml qu+) _d ((0)
2
1 + 3322ldd Aut )dm(((d)))))))))) + 2T + ld qut) 2xl (ull Qut)) dulluu
(D.24)
Proof. We note that
(grad[(=](>(t))) Euu+)
(grad ( Emu-) + (grad((ea((((t)) grad Emn+)
(D.25)
< ggaad[ppl ( Emn + llgrad[[2 (r)(t)) grad[eal(>(0))1 dm qut).
For any x + qu. our first-order step rule is equivalent of choosing
Pr. (x qu) Pr. qu)
u
arg
min -UE-
Ru
||Pr, (x qu)ll2
Then, lemma B.3 guarantees that there exists a satisfies Equation B.17 17 From our step rule, we know that ou also
and satisfies Equation B.17). Together with Lemma B.4 and (T(() xx;) 1/ kx have
(grad (())), Emu+) S -0.5 ||rad (x)o))))(((())]])))))))))))))))) E ll2
S -0.5
(I (xg - -000) (110)ll-11P2roooeeer
(E)co)M221)) 11 ll2
S 00.5
dd(()(0), (1 (1- ( =ddm(>(0)) 22,)
-Tmax/ ddu(qug9n) qu+)
(D.26)
0.55
[dd(((()) mx)) - mmax d
2
where from the second to the third line we've used the same argument from equation (A.28) to lower bound PIyrosM (Iz- - (0)))l by dx)()(0), mx) ) (1 ( 2.)) and ||E.u+ by dd au+) And we can bound (ara((p)((>(())) grad (=)((()))
(77()))=((7(t))) grad[ezl(< - (1 Pr Piycone) (r((t) - (0(t)
+ (Pryo)M Pr.co 2112
+ PeecosM - (1))
(D.27)
< PI Pryco dnm()(t),
+ P + |||
+ PT (T()) - (0)))l
31

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
Together with Lemma
D.5
we have
P
ProcosMloop dm(r((), S 3v2ntd qu (dd()(d))))))))))
(D.28)
Since 7(t) E BM 1/k) Vt E [0, 1/, we have
PrzunM2222 - Tuax:
(D.29)
hence
| + Pryco S 2T max.
(D.30)
From Taylor expansion on the geodesic we have
Percoi I i(a)da a==
-
2
PrrcooM f
[ (b)cdb da
(((0) +
6
(D.31)
|OOOE +
Pr Prxoo,u((bbdbuuu
Ja=O Jo=
1 S Ed qui)
kt xxt (uu.
Therefore,
[ggad((aa(<(())) grad grad()=](7(0))1 S 332nttdd Au+ (on mamax + Ld qu+) dst2dru (u qu+).
(D.32)
Combining all of things above, we have
-055
1 (ddn(z, 7(0)) Tmax dulluu qut)
(grad[(p=((7((t)) Eau+) ) S
2
+ (3Vnntdu(au qu )dm(((t), 2x)) + 2mmax + td qu ) 1 dullqu qui)) du qu )
(D.33)
Lemma D.7. Suppose
Iu E (M( \ (M CTmax);
(D.34)
for some constant e S 0.1, C 321, with
T Tiax=
sup (
(n, z),
(D.35)
and
dm(guu S min
T Timax
(D.36)
100%" 8
then
1 de du qut).
dylgut, 2x) I dm xx))
(D.37)
80
Proof. Let y [0, + M be minimum length geodesic joining qu and qui with constant speed d. gu where 7(0) = qu: (11) = 9.+- Then we have
dm qu+) du(xz2, qu) au)=1 f d
dt dd( 7(t)
d dm da v) -=)(1)" :30)) di
(D.38)
t
dy
logy(t)) Dy
logy(t) 02ll2 511) dl.
t=
32

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
We further decompose the integrand follows:
(o) 32
(t)
|| (0g Øgll2
1
(-10gy(1) my + grad(su)(((tt)) - (ra)) 4(1) Suu+ Suv+
|| (og)(1) #4ll2
1
(grad[<p](<7())) Sout) + +((-(1 1--ogy(() 2i (rrad()a((>((())))))))))))))(())
(graa]()
Eout)
dm(r(()) m4)
(D.39)
We will proceed to use Lemma D.6 to bound the first term, Lemma D.2 to bound the second term, and Lemmas D.] and D.3 to bound the last term. In order to apply these lemmas, we observe that Vt dn))), x;) S dM xz. +
dm (M)), 7()) & dm()((),, mn)) + dd(((()) (11) S + 100m S 8x
Thus from Lemma D.6 we have
(grad[<22) (7){)) Sau+)
0.55
2 [dm(za, ((0) Tiax
dm(quu qu+)
2
3v 3 qu+ (dm(d(()))))))))))o)))))))))))) 1b6) + maT + (d qut) + 1 5 du (ut)) dmlan qu-)
+
1 1 da 7(1) ddu((uu qut) + 1 [ dn (ovs qu+)
3/2 d lut) + 27 max + dm au+) + 200 dm
dn (qus qu+)) dmleun lu+)
+
8
1 dd 7(1) + 5
max + 2dm(quu d aut)
(D.40)
Similarly, from Lemma D.2 we have
(- log oy - grad[(=((((0)) $
| -logy()) at -
-grdgad(eaalee -grad()a](>(()) -19(0)
2 xxlu(7(t), + Tmax
du(qu..uut
(D.41)
1 dd(()(t). + Timax
ddllaur qui),
16
and Lemmas D.I and D.3 also give
(grad (pl (()) -E--) $ ||grad I1+(t) - Enu+ll
(3h 2 Aut))
< (dm(>(1), (0+) + Tmax)
2
(D.42)
( dm(r(()) xx)++ + Tmax dmllgw (ut))
3
200
200
Lastly, we combine the terms get
(grad((ul(>(()). Emnt)) + (- (-logy(() () Iy grad(e=)(7(t)), x(t)) (()))))))()))))))))))))))))))))) + (grad((el(<((t), ((t) - Emac)
40 (
1 + 15
4 Tmax + 2d au+)) d dail qu+)
(D.43)
1 dm(((((), + 4T 4Tmax (Ml
40
80 dxa()((t). d qu+),
33

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
where we've used assumption that dd la+) 5 and ( m. > dmn(7(0), ddlluu qu-)
mamx 8 maax 2 3200mmxx- Finanly, plugging this result back to Equation D.39
observe
108-(() 2:
dm 9u+) - d2 qu)==
10gyy()) 0all2 ((()) dt
1=
(- 1 (= dm dmlaus qu+)
(D.44)
== (m)()(t),
S 80
dm duu qu+).
This completes the proof
A. Supporting Results
Preliminiaries on the logarithmic map. The following sequence of lemmas provides an upper bound on the number of landmarks [Q), under the assumption that the landmarks are 6-separated. Our argument will assume that the manifold M is connected and geodesically complete. Under these assumptions, the exponential map
exPx: (-) M + M
(A.1)
surjective, i.e., for every q E M, there exists v E M
M such that
exp2, (v) q-
(A.2)
Moreover, by the Hopf-Rinow theorem, there exists a length-minimizing geodesic joining Ty and q, and hence there exists E TarM M of norm ||||| = d (2;, q) satisfying (.2)). In particular, for every E M, there exists v E M of norm at most || I diam(M) satisfying A.2).
The logarithmic map
logan : M M
(A.3)
is defined, in the broadest generality, as the inverse of the exponential map. This mapping can be multi-valued, since for given q there may be multiple tangent vectors v satisfying (A.2). Notice that because exp is surjective, its inverse, log well defined for all q .MM When d (x; q) S Tinj is smaller than the injectivity radius of the exponential map at æ; there is a unique minimum norm element v. of the set logæ; (q). This is typically denoted
log,r (q)
(A.4)
and satisfies || = d. (x; ④) 8 We can extend this notation from q E BM rinj) to all of M, by letting
log,, (g)
(A.5)
denote minimum norm element the set loga, (g), chosen arbitrarily the case that there are multiple minimizers this choice, loga, (q) is well-defined, single-valued over all of M, and defines mapping
With
logær MM- + Br,, M (0. diam(M)
(A.6)
Our analysis will assume that the landmarks Q are d-separated on M, i.e., dm q;) > for all i / j. We will show under this assumption that log.n, (q.) and log.,, (q,) are 8' -esppaaate albeit with a radius of separation 8' which could be significantly smaller than d.
This argument makes heavy of properties of geodesic triangles in particular, Toponogov's 's theorem, which compares side lengths of geodesic triangles in spaces of bounded sectional curvature to side lengths of triangles in spaces of constant sectional curvature. Our argument uses the following properties of the mapping log defined above:
"inj( = (r 0 exp2, is diffeomorphism (0, r) C M)
*This is often taken as the definition of the logarithmic map. Thii selection possible thanks to axiom of choice.
34

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
Inverse Property: for 10ga, (g), exp2; (v) ạ
Minimum Norm Property: || 1og (q)ll - (. q) S diam(MM.
Our analysis does not require analytical properties of the logarithmic map, such as continuity, which do not obtain beyond the injectivity radius of the exponential map.
Lemma A.1. For any R. O, and any 8-separated pair of points q. BM R) (Le., pair of points satisfying dm(g:90 g/ 2 5), we have
v2 4 exp( exp(-xR)o.
[1082; logang d'll 2
(A.7)
Proof. We will prove this claim by applying Toponogov's theorem, fundamental result in Riemannian geometry. Toponogov's theorem is comparison theorem for triangles, which allows to compare side lengths of geodesic triangles in an arbitrary manifold of bounded sectional curvature to the side lengths of geodesic triangles in model space of constant sectional curvature. From Lemma 10 in (Yan* et al. (023). the sectional curvatures of M are bounded from below by the extrinsic curvature K, i.c.,
Kg 2 -
(A.8)
Our plan is as follows: form geodesic triangle (xx q=, q' in the model M_ with constant section curvature -k3, whose side lengths satisfy
(00 q-x2) = dn q):
dM (0, (2, x= -d d2 9'),
(A.9)
and whose angle satisfies
<(q_x2 x2,-x,, x, x'x²)) = <(q, xy. q')
(A.10)
Then by Toponogov's 's theorem, the third sides of these pair of triangles satisfy the inequality
dmlqq, q') S dM (q x², d'm,)):
(A.11)
ie., the third side in the constant curvature model space is larger than that in M.
We construct the triangle A(x, q= x more explicitly as follows: fix arbitrary base point E M_ Let v, o' be two distinct tangent vectors in the tangent space TwMM satisfying
||0||2 = logg; g/12,
||0'1l2 - 10ga, d'112,
(A.12)
and 0- = L(logm, logar d') = -LV, v²). Set q_ = (x) E M_ I' expx(U') E M_
Notice that ||0 - 0'll loga; q logge d'll. We would like lower bound this quantity. From (A.1T) and the fact that dg q') 2 5, we have dmm,, (9-n2, x=xa) 2 5. and the task becomes one of lower bounding ||e o in terms of this quantity. To facilitate this bound, we move M_ hyperbolic space M_1, where can apply standard results from hyperbolic trigonometry, by scaling all side lengths by Namely, form third geodesic triangle in MM by taking an arbitrary - E 1M choosing 0'1,0'_ E Tu M_1 with L(1-1, vL,) = 0 and | 1 ll2 k|[wr], ||wÍ]|2 = =||='|]. As above, set q-1 = expx_, 1U=1), and d'1 expx_, (XP=_,('_,) Then
dm ,
kdM_ (q-x², L
(A.13)
Moreover,
|a -', xi|e r'll.
(A.14)
For compactness of notation, let I/ denote the third sidelength of A-1,
I' = d d (9-1,
d a (q-x2; )
(A.15)
The lengths of the other two side are x * ||Ba|2 < KR, b = x * 1|o'll2 S kR, and angle between these two sides is equal to 8. the corresponding Euclidean triangle on the tangent space, we also have the two sides are length a and b, and the third side has length
I.
1 x 2|
(A.16)
35

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
As M_ is hyperbolic, from hyperbolic law of cosines, have
cosh T' cosh cosh b sinh sinh b coos 0.
(A.17)
From the fact that cosh(a 1 b)) cosh cosh sinh ainh b, could further get
cosh L' cosh(a
sinh sinh b(1 cos 0).
(A.18)
Since sinh t convex over E [0, oo), we have sinh t v f xft And cosh(a b) cosh la b| z cosh L. Then we have
(inh(x:R) for t Σ kR, hence sinh a sinh b I ab
(xR))² sinh (x:R)
cosh L' I cosh L + ab sinh sinh"(x:)(( - cos f). (kR)²
(A.19)
From the law of cosines applying Euclidean triangle with length of two sides a, b and the length of the third side I, know
1,2 a² 132 2ab cos 0
2ab(1 cos 8)
2ab (cosh L' cosh (xR)²
(A.20)
absinh"(kch
2(nRt)² (cosh I' cosh L)
(xnR)
Since dq q') 2 6, then L' = * dm _ (q- d_x)) 2 K* d 4') 2 kō. Then equation (A200) implies
2(xR)² (x
2(xR)² cosh
L
cosh I
(A.21)
(kRR)
By triangle inequality, we know L S a S 2xR. From the mean value form of the Taylor series, we have sinh(xR)
RR cosh((i) for some 0 rı RR and
L
cosh T. < + cosh(r2),
(A.22)
for some r2 S L. Multiply equation (A.21) both side by 2(xR)²
(n and plug in the value above, we get
cosh < sinh (1:R)
L2 + cosh L
(A.23)
2(xxt)²
cosh (ri))(11)) 1?2 + 1 cosh(r2))
122
(A.24)
2
Rearrange the terms, we get
L,2 2 2 coshi((m) cosh(r2)) (cosh((<0) 1)
(A.25)
2 2 (cosh? (NH) + cosh(2xXR) 282
(A.26)
exp( exp((22x11) ~2xR)
(A.27)
(A.28)
where from the first second line we used that cosh(t) 2 1 1 As a result, we have |llog.; q log,, d'll || w'll v2 exp(-kR) z 4 exp(-xRR)
L/R ks 2
36

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
Lemma A.2. Consider 2; E M and let QR {qq: q Ba R) n QQ.. Then the number of landmarks within bull centering Fy Le. 12z, satisfies
QAl - 4v 44to2222m//888 VR 0.
(A.29)
In particular, we have
[ S (1+4V28 diam(M)) )
(A.30)
Proof. For every q E Qn. there is a unique tangent vector log,; E M. Now we define the set Vn = {loga M..M Vq E 2R). Then the number of landmarks within the intrinsic ball BM (Re, Rt is 12 = [|Rl
Let 5R = v22 exp(=xxR) From Lemma A.1 we know that VR forms a òū sepaaratd subset of B(0, R) on M. And for d q) S R. Then it's natural to notice that \Val S P(B(O, R), 5R), where ((B(0, R), 0g) is the largest cardinality of separraed subset of B(0, Rt) E M.
any 1oga; VR. we have [oo,, a
Since ((B(O, R), 6R) is the largest number of closed disjoint balls with centers ((,, R) and radii 8//2, then by volume comparison, we have
P(B(O, R), vol( (B2n22) vol B (2+R))
(A.31)
Then we will have [VRl= s ((,(O, - (1+
which gives the bound we need.
To bound Q, we can simply take diamm(M and notice [ = Qdiam(M))
Lemma A.3. Let M E R be a complete d-dimensional manifold. Suppose the set of landmarks Q = {q} C M forms
d-net for M, and first -order edges Ex satisfies that u + E² if qu qulll S Rubres where Ruivs S TM, and TM is the reach of the manifold. Assume 8 s diam M, and k diam(M) 2 1. Then the number of first-order edges E satisfies
log
E < (rc diam(MM + log(() - log(d) 6) + log(dian(M)) + log(100)) d.
(A.32)
Proof. From construction, we have
| S Q
max Ey quEQ
(A.33)
where E denotes the first-order edges at landmark qu- As we have Rubrs S TM S 1/k, following Lemma A.2 and
Equation A.30 we get
E7 S + 4028-111111 Rubrse" (1+AV28 dia (d) d
)
(A.34)
1 + 4v 20ee (aabo))))))
"(1+4V26 (1+4/20-ciam(M)) diam dlam())) ))))
(A.35)
We recall that a = Rybra/8 2 40. Since ealaarr 2 1, we have 1
To ae 2 1, which means + 4 4 Rae < 4o + ao < (1) + 4V2)a e, since K.Rabre I 1. Similarly, since å < diam M, and x diam(M) 1. < ( + 4V228-11 diam(MMe) diam(M), which gives
1 + 4v28-1 diam(M)e* di)
( + 4v20)a) a ( 4V2)00 "diam(M)e diam(M)) (a d
E1 <
e
(A.36)
40
( + 4020 + 4v2)) diam(M)) diaam(()) d
e
(A.37)
to
s (100)" (ao-1 diam(M)e diamm())))
(A.38)
37

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
Taking the log, get
log E² S (A (tiam(M) + log(()) log(() (6) log(diamm(M)) log((10)) d.
(A.39)
Lemma A.4. There exists a numerical constant C such that with probabilty least -9//2
Tmax= sup { (0,22
dy vig) I 1/KK, E M, 11012 =
(A.40)
satisfies
T maax S C max ovd.
(A.41)
+2
Proof.
Let R. = max 1}. From Theorem 10 of Yan* et al. 2023), we have that with probability at least 1 - 6 20
Tuax 12o
2x + Vlog 12R +
(A.42)
We note that there exists numerical constants C1, C22, such that Vlog 12k - CRR, and Va+I C2vd. Setting x 30 3d then have
12 2T
v log 12k) + S 120R 2n oCik +3vd
(A.43)
112 ovd
yielding the claimed bound.
Lemma A.S. Let
dm xz)) 1 v E TTMMM |10/2 = }
Tmax = sup (0,2) sup
(A.44)
Then with probability at least
we have
Tiaxx 2 o dd/2-22
(A.45)
Proof. Since T max the supremum of 1-Lipschitz function and is therefore 1-Lipschitz in z, it follows that
P [Tmax S [E[Tmax]
t S e 1//20²
(A.46)
By setting = 2y and e = Pray .22 we obtain Tmax 2 Pr.,,MZ
M and thus B[Tiax]] 2 B Bl M m=
Since z is i..dd Gaussian with variance o², the rotational invariance of Gaussian distributions implies that B[] M = B[[[agal]], where ga (0, Ia) is d dimensional standard Gaussian vector. As ||ga|| is 1-Lipschitz, from Lemma A.6 A.6 we have
1 2 Var[lga [B[] 9 B[llgu 2 = d [lllga
(A.47)
and thus E[[ggal] 2 Vd I. Therefore,
B|||P,, MI|l = Biollgall] | 22 //d/2, for d 2 2.
(A.48)
For the case where d compute directly:
Elll Mlll = V2o T(dd + 1)/2) = 22/TO 2 v d/2o.
(A.49)
r(d/2)
Combining the cases for and 1, and substituting into Equation A.46)), we conclude that
Tmax 2 20/d/2- with probability at least 1 - e -2/20
(A.50)
38

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
Lemma A.6 (Bounded Variance of 1-Lipschitz Function). Let g NN,,,)) I) be standard Gaussian, 1-Lipschitz function, then have
Var(f(g)] S
(A.51)
Proof. In the prove, we utilize the Gaussian Poincaré inequality (Boucheron al. 2003 Theorem 3.20] which says that Var[h(g)] < B[]VV(())]I
(A.52)
Ixx
for any C function h. Let Ps be the standard Gaussian mollifier Ps (z) (2ne)ee e and let
fe = f f(x - (z)
then fe is smooth. As
lfc(x) fc(1)) / (fc(x - 2) - fzly z)) Po (=(2)
(A.53)
$ | ([fc -z) ff -2)) (c))
(A.54)
s || - اll / Ps (z(z) = =1| - yll,
(A.55)
fe is also 1-Lipschitz. Following the Gaussian Poincaré inequality we have
Var[Se(g]] < /
(A.56)
To conclude the result, we need to show the interchangeability of the interation and the limit. As fa is 1-Lipschitz, we have
Ifa (m)) < (0) + ||=|||
(A.57)
| f(-2) 2))c + ||=|||
(A.58)
|| [==ll=(())dz ||ر|||
(A.59)
VeB [I] + ||=|||
(A.60)
As the moments of a standard Gaussian are upper bounded, (Je(g) ( can be uniformly upper bounded by some integrable function for all E I 1. And thus
Var[f[gl] -0-0
Varlfe(g)] S 1.
(A.61)
B. Experimental Details
B.1. Gravitational Waves Data Generation
We generate synthetic gravitational waveforms with the PyCBC package (Nitz et al. 2023) with masses drawn from Gaussian distribution with mean 35 and variance 15. We use rejection sampling to limit masses to the range [20, 50], Each waveform is sampled at 2048Hz, padded or truncated to 1 second, and normalized to have unit e2 norm. We simulate noise as i.id. Gaussian with standard deviation a = 0.01 Yan et al. 2023). The training set consists 100, 000 noisy waveforms, the test set contains 20, 000 noisy waveforms.
B.2. Noisy vs. Denoised Gravitational Wave Signal Visualization
The following example (Figure 10 presents a visualization of a noisy gravitational wave signal and its corresponding denoised version, obtained using Denoiser described in Table
39

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
noisy signal
denoised signal and ground truth
sigral
0.10
ground truth
0.05
0.00
0.00
-0.00
-4.10
500
1000
1500
2000
500
1000
1500
2000
Figure 10: Left: Noisy gravitational wave signal. Right: Corresponding denoised output obtained using Denoiser 1 described in and the ground truth signal.
C. Traversal Networks on Synthetic Manifolds
In this section, we present traversal networks created by Algorithm on the following synthetic manifolds: sphere (Figure
12 torus (Figure TT.
Figure 11: Traversal network the torus with noise level 0.01. Left-to- Right, Top-to-Botue Bottom: Clean manifold, landmarks (blue dots), first-order edges (blue lines), zero-order edges (green lines), final traversal network, and final traversal network overlayed with clean manifold.
Figure 12: Traversal network the sphere created based 100,000 noisy points with noise level 0.01. Left-to-Right, Top-to-Bottom: Clean manifold, landmarks (blue dots), first-order edges (blue lines), zero-order edges (green lines), final traversal network, and final traversal network overlayed with clean manifold.
D. Incremental PCA for Efficient Tangent Space Approximation
In this section, we detail the tangent space approximation implementation mentioned in Algorithm 2 and detailed in Algorithm 4 and Algorithm We use Incremental Principal Component Analysis (PCA) to efficiently process streaming high-dimensional data. Below we present the mathematics and algorithmic details of our implementation.
Initializing Local Model Parameters New Landmarks: If newly created landmark qM Algorithm 2 has no other landmarks within Rabrs distance, then its tangent space Tyx is initialized randomly. Otherwise, we identify all existing landmarks within radius Rubes referred to the first-order neighbors and establish connections them. The local parameters Tas and Egg, then initialized based on the information from these first-order neighbors, detailed below.
Let (g: (g denote the set of first-order neighbors of landmark gMs, excluding qu itself. We compute the normalized
40

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
Algorithm 4 IncrPCAoMMatrix(X.
1: Input: centered data matrix [2] qM: Fn qM) E R Rxx containing points within radius R(M) of qM- intrinsic dimension d.
2: U1 < [2] gar/ - qM
3: A - || - qM [
4: for fori=1....,
do
5:
U141,
IncIPCA(2141 QM, U2 As, 1,d)
6: end for
7: Output: U An
difference vectors:
9: qa
h;
(D.I)
[g. q
and assemble them into matrix H = h1 h2 he The tangent space Tax is spanned by the orthonormal
matrix UM obtained through truncated singular value decomposition of H. which ensures Uqu E Pxd, where D and represent ambient and intrinsic dimensions, respectively. Edge embeddings Egg are then created via projecting vectors q: qm onto ggM-
Updating Tangent Space Approximations Efficiently: Once a new landmark qM is created, along with its tangent space Tax and edge embeddings Equ. will update local models at qM using incoming noisy samples that fall within radius R(M). A straightforward way to perform this update is to re-estimate quantities such as the landmark and associated tangent space for each sample as the online learning process progresses. However, repeatedly estimating these quantities from the full dataset is computationally inefficient. To address this, we employ incremental PCA for tangent space updates, following the methods proposed in (Brand 2006; Arora et al., 20122. as detailed below.
Define centered data matrix X,, sample En+1 arrives, is appended form the up- dated matrix X = [X,, In+1 qm). Let U?? denote the rank-l (1 d. where d is the intrinsic dimension of the manifold.) approximation of the X, of the tangent space at qM prior the arrival of new sample In+ and A, E IR(x is a diagonal matrix of corresponding cigenvalues. Our goal is to efficiently update the tangent space at qM upon receiving the new sample 2n+1-
Let vertex .M have local parameters
qM T
(m--00 - qM, 22 ..,..., Fn qm] Dxn, When
X,,X, n where U, E Dxl is an orthonormal matrix that approximates the basis
We note that
X Xn41X n+1
Xn,
Fn-1 qM ][ Xn Øn+1 QM ]
(D.2)
= X + (xn+1 qM) (In+1 gm)
(D.3)
S - U,A,U + (#n+1 qm) (#n+1 qm)² Then S is approximation of X.+1X² n+1 A rank-l approximation of S therefore provides rank-l approximation of the X n+1 The following outlines the procedure for deriving the rank-l approximation of S.
The matrix can written as follows.
s U,A,U (xn+1 qM) (In+1 qM))
(D.4)
Un Int1
gM ]
An
or
0
1
Un Int1 9M 1a
(D.5)
We define the component of Øx+1 - qas that is orthogonal to the subspace spanned Un as (Ix+1 - -xx) = (I U,U!.) (#n=1 - ). Then we have

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
Algorithm 5 I2 qM. U, A 1,
Inputs: +:+11
gMs
U1, A,, 1,d
A
0
2: Aexp 0
0
3: (I++1 -qM)
(I - U,U))" (#i+1 qM)
=
U (x--1 qM)
U (I++1 qM) 1T (xi+1 9 )
4: K Aexp
[ -as)²
5: UKI11 Ki+i t digendecomposition (++1)
6: U++1 Ui
(m:11-9-)+ [<0411-9N)~1 UK.4
7: A4+1 Aii1
8: ifi d then
9: Ui+1 U d]
10: A411 + A4t1l:d; d
11: end if
12: Output: U1+1, A+41
Un En+1 9M
U
U (In+1 qns) + (I UntT) (xnt1 - qns)
(D.6)
Un
U (#n+1 qM) (xn+1 -aa)
(D.7)
I
UT. (#n+1 9m
Un
(0 (an+1 q
(D.8)
0"
(xx+1 92r)
Thus have
7
S = Un
(m--1 1 }ar)
K Un
[m++1-9M1]
(D.9)
(an-1 - {ar)
[ - Q3
where
I
U n (In+1 - 4m)
An
P]
K =
0 [2nt1 qas)" 1
o
i
(Int1 qus Un ||( - 9ax)'11
(D.10)
We can further simplify K as follows.
An
UH (#n+1 - qM)
0 (In+1 qm Un. ||( - |
K
0
[ 9mr)+
(D.11)
An + U²' (In+1 qar) (In41 qM)" Un U (xn+1 - qNr) (00))((nnt11 9m))
(D.12)
(xx+1 -qx))
(In41 qM)) Un
(2 - -Mx) --0)"11
Uhi (In+1 qas) (#n+1 - qM) Un Uh. (Int1 - qM)) ( 9ma)
A
+
(D.13)
or
(x -MM) )
(#n41- qM)" Un
(a - ((
UT (In+1 - I'r)
A o
(# qnr) gMx) TT Un 100011--000 (11)
(D.14)
(#n+1 -qw)*
UT (In+1 9as)
UT (In+1 qm
A,
0
+
(D.15)
(In+1 -(M)=
42

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
We note that K is of size I by the K = -UKAKUP will cost Odd)). From Equation that
D.9
and (.11), we know
s Un
(un+)-9u)+ |0.11-9x)-11
UKARUK]
Un
(m++1 qar)
T
(D.16)
axc)
We define
Unt1 [
Un
(#++1 9xx) UK.
(D.17)
( 11=11-9xx)-1
Aut1 = Ak-
(D.18)
Then
S - n+1
(D.19)
If the sample index i greater than d, we truncate Un+1 and An+1 to retain only the top d eigenvalues and corresponding eigenvectors, thereby obtaining rank < d approximation of X XXT. The computational cost of the update ((D.17) and (D.18) is O(nDd), with storage of ((d)).
E. Additional Explanations on Algorithm 2
Landmark Update Let (zy)}=1 denote the previously observed noisy samples within the neighborhood R(i) of the landmark Q: and let #n++1 be the newly arrived sample with that also lies within this neighborhood. At (n + 1)-th iteration, the landmark is updated by computing the average over all n + noisy samples:
n+1
8k.
(E.1)
However, this update rule requires reprocessing all past samples at each iteration, leading computational inefficiency. To address this, our algorithm employs a streaming (or online) averaging method that incrementally updates the landmark using the previous average:
na
Ent1l 1+1
q.
(E.2)
n
Projection Definition Let U; be the approximated basis for the landmark qi- Then the projection of point æ onto the affine space q: - T; is defined as
P PU+TI== - U,U q:).
(E.3)
Create First-Order Edges for New Landmark When new landmark qi is created, first-order edges are established according to the following rule:
create i j if 11q: 43ll2 S Rubre-
(E.4)
Edge Embedding Definition The edge embedding a, associated with the landmark qi whose approximate tangent space basis is Ug, is defined as
{U (f - -0)+tj))
(E.5)
where E denotes the set of first-order edges.
F. Choosing Denoising Radius
The parameter called denoising radius R(i) in Algorithm 2 controls complexity by determining the number of landmarks
created. Conceptually, as the online algorithm learns, the error in landmarks decreases, which means that R(i) needs to be decreased as the landmark gets learned. This is why we define a general formula for R(i) as follows:
RG1² = (2DD
o²D N + c2o²d).
(F.I)
where N; denotes the number of points assigned to landmark qi The power parameter k helps us control the speed of decay of R(i). making it adaptable to different datasets. Table show the specific constants used to create the R(i) parameter to produce Figure
43

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
Table 1: The choice of hyperparameters yielding each denoiser. N, corresponds to the number of points assigned to a landmark %. For experiments, o 0.01, 2,and D 2048.
DENOISER #
R ROENOISING
R
1
1.2(o2 D
oiD
+ 20o²
2.39o² D
N
2
2.060 1.2( D
2.39o² D
3
N1/2 So²d)
a&D
2.39o² D
4
2.75
3.130² D
5
1.3(0
+ o'D
20 N
2.39o² D
1.15(0
+ D2D
+ 40
2.39a²
N
7
2.39 D
2.750
1.5(o"D
+ 3000 d)
2.39a
9
20 20'D D
2.39 D
10
2.19o²D
2.39o
11
3.130²D
3.53 D
1.94
2.39o²
G. Additional Experiments and Details
G.1. Autoencoders
We include nonlinear autoencoders as an additional baseline for denoising gravitational wave signals, they are generic learning architectures specifically designed to leverage low-dimensional structure in data. To this end, create 15 different networks (see Table 2 with various depths and widths and symmetric encoder/decoders. The widest layers match the input dimensionality, while the narrowest bottleneck layer is set to dimension 2. All autoencoders are trained using the Adam optimizer with a learning rate of 1 x 10-3, As we can see in the Figure 13 high-complexity autoencoders can reach high accuracy. We also observe that while autoencoders we tested can achieve higher accuracy, our method exhibits significantly better efficiency-accuracy trade-offs. In our work, we notice that varying the R((i) parameter in our mixed-order method improves accuracy of manifold traversal method. As a direction for future work, we plan to further investigate how adjusting R(i) can enable our method access higher-accuracy regimes.
Computational Complexity vs. Accuracy
log of #Multiplications per sample)
6.0
Manifold Traversal (R constant)
s.s
Manifold Traversal (R decreasing)
Autoencoder
5.0
0.0
0.1
0.2
0.3
0.4
0.5
0.6
Mean Squared Error
Figure 13: Test-Time Complexity-Accuracy Tradeoff of Manifold Traversal versus Autoencoders.
44

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
Table 2: Autoencoder Architectures. Decoder is mirror image of the encoder.
NUMBER
# OF LAYERS IN ENCODER
DIMENSIONALITY OF LAYERS
2048 +
2048 + 1024
3
2
2048 + 512 +
2
2048 - 1024 + 512
2048 - 128
2048 + 1024 + 512 + 128
6
2048 - 1024 + 5
-
8
6
2048 - 1024 512 -1 256 128 -> +
8
20488 1024
128 -2
--2
10
2048 -004----------
+8
11
10
2048 - 1024 + 512 + 126-+18-+04
32
16 +8 +4-2
12
2
2048 -
13
3
2018 - +2 ->
14
2018 16-48-4
15
2048 - 16 +1-2
G.2. Large-Scale Experiment
We evaluate our method on large-scale real-world image data by performing patch-level denoising. Specifically, we randomly select 300 RGB images from ImageNet, each corrupted with zero-mean Gaussian noise with a standard deviation of a = 0.1. From these, extract 894, 262 noisy patches of size 8
3 with the stride 8. After random shuffling, we use the first 890, 000 patches train traversal network. As shown in Figure [4] the training error steadily decreases, indicating effective learning for denoising. One visual examples of clean, noisy, and denoised patches and images shown in Figure 15 While integrating image processing techniques to address pixelation and color artifacts may further stabilize and enhance denoising performance and visual quality, such exploration is beyond the scope of this paper.
Training Error Curve
2.25
Mcan Squared Error
1.75
1.35
Number of Samples
Figure 14: Training Mean Squared Error (MSE) Curve for Large-Scale Image Denoising.
45

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
patch
Nokey patch patch
Clean palch 1711
Noisy patch #711
Desoised patch #711
Original Image
Noisy Image
Denoised Image
Figure 15: Large-Scale Image Denoising Top and Middle: Two different randomly selected patches from the random select image. Each shows, left-to-right: the clean patch, the noisy patch, and the denoised patch. Bottom: Left-to-right: clean high-resolution image, noisy image, denoised image.
G.3. Single-Image Denoising
test our method extreme scenarios when only single noisy sample available - an interesting and challenging setting in many important applications. To investigate our method's performance in such challenging setting, we conduct an additional experiment to denoise single natural image from the DIV2K dataset (Agustt(A & Timofte 2017] high-resolution dataset of natural RGB images with diverse contents. We corrupt the image with Gaussian noise noise level of 0.1 and apply our method for patch-level denoising, leveraging the common assumption that image patches lie wwwddimensionll manifold. Specifically, we extract patches of size 8 x 8 x 3 with stride 4, yielding 172, 042 patches from a randomly selected image. After shuffling, we use the first 170, 000 patches for training. Figure T6 shows the mean squared emror (MSE) decreasing as the number of training patches increases, indicating that the proposed method effectively learns denoise. We also provide visual comparisons of clean, noisy, and denoised patches and full images in Figure 17
46

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
Training Error Curve
200
1.8
Mcan Squared Enror
1.4
1.2
1.0
100000
125000
150000
175000
Number of Samples
Figure 16: Training Mean Squared Error (MSE) Curve for Single-Image Denoising.
Clean parch #2966
Noisy patch #13964
Denoised patch #132964
Clean patch #8643
Noisy patch #8643
Denoised pasch #8643
Original Image
Noisy Image
Denoised Image
Figure 17: Single Image Denoising In the extreme case where only one image available, our manifold traversal method successfully performs denoising. Top and Middle: Two different randomly selected patches from the high- sighrresolution image. Fach shows, left-to-right: the clean patch, the noisy patch, and the denoised patch. Bottom: Left-to-right: clean high-resolution image, noisy image, denoised image.
G.4. Ablation Study on Mixed-Order Method
This section presents an ablation study of the mixed-order method to justify the combination first-order steps for efficiency and zero-order steps for achieving global optimality. Specifically, we compare with (i) a first-order optimization method exclusively first-order edges generated by the online learning algorithm, and (ii) zero-order optimization method applied to all edges, where the original first-order edges are treated as zero-order. Both methods use the same step rules as their respective components in the proposed mixed-order method. The experiments are conducted on the noisy version of the gravitational wave test set described in Section B.I
As shown in Figure 18 the efficient gradient- based first-order method achieves the lowest computational cost but suffers from the highest error. On the other hand, our mixed-order method achieves a significantly better trade-off between complexity
47

---

Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization
and accuracy in the high-accuracy regime compared the zero-order method. These results confirm the effectiveness of mixed-order method, especially in achieving efficient, high-accuracy denoising.
Ablation Study of Mixed Order Method
Ablation Study of Mixed-Onia Method (700m in)
log of (fMuhiplicatonn per sample)
60
X
Mixed- Order Optimization (R decreasing)
First-Orier Optimization
Optimization (R constam)
log (0Multppication) sample)
6.
Mixed Order Optiiizttonn decreasing)
Misei-Orler Optimication (R consiant)
Onder Opimization
Zetu-Order Order Optiizztiin
30-
X
50-
45
010
0.01
1622
5/13
0.08
0.66
Mean Squared Error
Mean Squared Error
Figure 18: Left: Complexity-accuracy trade-off among the first-order optimization, zero-order optimization, and our proposed mixed-order optimization. Right: A zoomed-in view of the left portion of the left plot.
48


Reviews:
[{"review_id": "aDNJGiPAQx", "reviewer": "Reviewer_6tJ4", "summary": "This paper studies the interesting manifold denoising problem (ref. 1) with the focus “learning-to-optimize” and proposes test-time efficient denoising algorithm. Also mixed-order optimization is proposed to help achieve near optimal results, given first-order gradient only optimization is more efficient. \n\nStrengths: the high-level idea of combing both first order (gradient) and zero order (zero-order neighbors search) is interesting, and the construction of manifold traversal networks is good to see. Also, theoretical analysis (section 7 and appendix) results show the proposed algorithm can achieve certain error accuracy (i.e., linked with geodesic curvature, intrinsic dimension) with upper bounded computational complexity. \n\nExperimental results on synthetic data are presented in section 8 and illustrate the trend of training stage denoiser error converging to theoretical lower bound. Test time efficiency and the comparisons with nearest neighbor search are included to show the proposed algorithm can achieve same level of accuracy with lower computational cost.  \n\nReferences:\n\n1. Hein, M. and Maier, M. Manifold denoising. Advances in neural information processing systems, 19, 2006", "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 sincerely appreciate the reviewer’s valuable feedback to improve our work. We are pleased that the reviewer finds the manifold denoising problem interesting, as well as our idea of rethinking learning-to-denoise as learning-to-optimize, and our accurate and efficient mixed-order method. We are also glad that the reviewer appreciates our theoretical analysis, which demonstrates near-optimal denoising performance and establishes an upper bound on the computational complexity, both of which are tied to the manifold’s geometric properties. Below, we respond to the reviewer’s questions with additional experiments. All updated results are available at [Figures.pdf] (https://anonymous.4open.science/r/Figures_Manifold_Traversal-8D25/Figures.pdf).\n\n**Additional References:** We thank the reviewer for suggesting the inclusion of additional related works. We will incorporate [Hein and Maier, 2006], [Gong et al, 2010], [Hu et al, 2021], [Puchkin and Spokoiny, 2022] in the final manuscript. We discuss the two suggested references below.\n\n[Hein and Maier, 2006] presents a manifold denoising algorithm based on graph-based diffusion process. [Gong et al, 2010] approximates the manifold by linear subspaces, and denoises based on the local linear approximation. Both works and ours denoise based on only noisy data without prior knowledge of the manifold. However, they are inefficient at test time: denoising previously unseen data requires a linear scan to locate its nearest neighbors. At the core, these methods rely on nearest neighbor search, while our approach achieves significantly better accuracy-complexity trade-offs at test-time.\n\n**Real-World Data:** We appreciate the reviewer’s thoughtful suggestion. We would like to emphasize that using synthetic gravitational waves (GWs) is standard practice in GW astrophysics, as it enables systematic evaluation of methods’ performance/limitations in a setting where only a few hundred confirmed detections exist. \n\nFollowing the suggestion, we have also applied our method to real-world images; patches are assumed to lie near a low-dimensional manifold, and denoising is performed at the patch level. We perform experiments on large-scale real-world data from ImageNet with additive Gaussian noise on 1,310,000 patches. **These experiments on large-scale data further demonstrate our method's denoising ability beyond synthetic settings** ([Figure 8] (https://anonymous.4open.science/r/Figures_Manifold_Traversal-8D25/Figures.pdf)).\n\nWe tested our method under extreme scarcity, when only one noisy real-world image is available as training data. The results show clear denoising progress, with steadily decreasing training error curves ([Figures 5, 6, 7] (https://anonymous.4open.science/r/Figures_Manifold_Traversal-8D25/Figures.pdf)). We will include training curves in the main paper and additional visuals in the Appendix of the final manuscript.\n\n**Additional Baseline Comparison:** We thank the reviewer for helpful feedback. We chose nearest-neighbor search as our baseline because it serves as the foundation for state-of-the-art provable denoising methods [Yao et al, 2023], [Sober and Levin, 2020]. Our proposed mixed-order method achieves orders-of-magnitude improvements in computation while maintaining theoretical guarantees.\n\nAs suggested, we have added nonlinear Autoencoders as a baseline, which are generic learning architectures designed to leverage low-dimensionality. The result shows that our mixed-order optimization method — designed to exploit both the optimization structure of the denoising problem and the manifold structure of data — achieves a substantially better accuracy-complexity trade-off compared to the Autoencoder ([Figure 4] (https://anonymous.4open.science/r/Figures_Manifold_Traversal-8D25/Figures.pdf)). We will add this comparison to the final manuscript. For more details, we kindly refer the reviewer to the our response (**[Connection to Diffusion Models]** paragraph) to Reviewer eTvP for more details due to space limitation.\n\n**Additional Landmark Elaboration:** We thank the reviewer for emphasizing the need to clarify the landmark concept. We will include \nthe following illustrations in the final manuscript. [Figure 1] (https://anonymous.4open.science/r/Figures_Manifold_Traversal-8D25/Figures.pdf) provides an illustration of landmarks. Intuitively, they serve as a discrete approximation of the unknown manifold. To enable optimization over the manifold, we need a structured domain, which is formed by the landmarks and connecting edges, facilitating optimization. Importantly, all these components — including the landmarks, edges, and other related quantities — are learned directly from the noisy data, using the proposed online learning algorithm.\n\n**Closing Comments:** We sincerely thank the reviewer for the valuable feedback, which helped us improve the work. We hope our responses address your concerns and are happy to provide further clarification if needed.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I looked Theorem 7.1, and some more from appendix section A, though not very carefully for examination.", "experimental_designs_or_analyses": "Section 8 included both (1) training error converge trend, and (2) test time accuracy vs. complexity tradeoff, and figure 5 for visualization of graph construction results for manifold traversal networks.", "relation_to_broader_scientific_literature": "NA", "essential_references_not_discussed": "This work cited a number of papers from traditional denoising methods to more recent deep neural network leaning based paper, and for manifold denoising then ref. 1 below is included, though there are more directly related works for manifold denoising, e.g., more recent denoising works like ref. 2 or others, should be good to include more closely related work discussions. \n \n\nRef. 1: Hein, M. and Maier, M. Manifold denoising. Advances in neural information processing systems, 19, 2006\n\nRef. 2: D. Gong, F. Sha, and G. Medioni. Locally linear denoising on image manifolds. AISTATS, Proc. Mach. Learn. Res., 9:265–272, 2010", "other_strengths_and_weaknesses": "Limitations:\n\n1. Experimental results, unless I missed, seems only included synthetic data for the test time accuracy evaluation and comparisons with alternative methods. It will be informative to see results from real world data, and some real-world data indeed with lower intrinsic dimension. \n\n2. Section 8 only included \"nearest neighbor search\" as the alternative baseline, it should be helpful to include other (more recent) works, to support the proposed algorithm in this paper.", "other_comments_or_suggestions": "1. Landmark, first mentioned in section 4 (page 4), feel should be helpful to add some illustration here, i.e., high level the concept and usage of landmark in this work, consider it is one important part of the proposed denoising framework.", "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": "WqVqlbIN5c", "reviewer": "Reviewer_9XFD", "summary": "This paper proposes a new framework for efficient denoising of noisy data sampled from an unknown manifold, which treats \"learning to denoise\" as \"learning to optimize.\" The key innovations include: 1) online learning that learns to optimize clean signals using only noisy data and improve the optimizer on the fly; 2) mixed-order methods ensure that the learned optimizers reach global optimality, balancing efficiency and denoising performance. The authors provide theoretical analysis as well as conducting experiments on synthetic and real data.", "questions": "", "limitations": "", "rating": 4, "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 reviewer for the positive feedback and thoughtful questions! We're glad the core idea of learning-to-optimize for denoising, along with our mixed-order method and scalable online learning approach, was well received. We also appreciate the recognition of our experimental and theoretical contributions. Below, we address the reviewer’s questions with additional results. Additionally, we present an ablation study ([Figure 3] (https://anonymous.4open.science/r/Figures_Manifold_Traversal-8D25/Figures.pdf)), which further highlights that mixed-order optimization has significant advantages over both first- and zeroth-order optimization for efficient, high-accuracy denoising. All updated results are available at [Figures.pdf] (https://anonymous.4open.science/r/Figures_Manifold_Traversal-8D25/Figures.pdf).\n\n**Single Noisy Data Denoising:** We thank the reviewer for this excellent question! The scenario where only a single noisy sample is available is indeed both interesting and challenging. To investigate this setting, we conducted an additional experiment focused on denoising a single natural image from the DIV2K dataset [Agustsson and Timofte, 2017]  — a high-resolution dataset of natural RGB images with diverse contents. The result showed that the training error steadily decreased ([Figures 5, 6, 7] (https://anonymous.4open.science/r/Figures_Manifold_Traversal-8D25/Figures.pdf)). Details follow below.\n\nAs suggested, we applied our method to a single training image, performing patch-level denoising under the common assumption that patches lie on a low-dimensional manifold. We choose a patch size as $ 8 \\times 8 \\times 3$, with a stride 8, which results in about 50,000 patches in a single randomly selected image from the DIV2K dataset. [Figures 5, 6, 7] (https://anonymous.4open.science/r/Figures_Manifold_Traversal-8D25/Figures.pdf) also show denoised images and patches.\n\n**Large-Scale Data Denoising:** We appreciate the reviewer’s feedback and suggestions regarding the exploration of large-scale, complex image data. Following the reviewer’s suggestion, we have applied our method to real-world image data and performed  denoising at the patch level. We use images from ImageNet with additive Gaussian noise on 1,310,000 patches. The results demonstrate clear denoising progress, evidenced by steadily decreasing training error curves, as shown in [Figure 8](https://anonymous.4open.science/r/Figures_Manifold_Traversal-8D25/Figures.pdf).\n\nTraditionally, image degradations, such as additive noise, blur, zoom, saturation, and others, are handled via iterative reconstruction methods. These methods alternate between two steps: (1) enforcing consistency with the observed image via a degradation model, and (2) applying a prior on the clean image, typically through a proximal operator. In approaches like Plug-and-Play [Venkatakrishnan et al., 2013], this proximal step is replaced by a learned denoiser, allowing for more flexible and data-driven regularization. Our method can be directly applied as a denoiser for Gaussian noise. However, for more complex degradations  such as motion blur and others — a single-step L2 projection onto the clean-signal manifold is insufficient. Just as our method can be integrated into diffusion models and compressed sensing reconstruction pipelines, it can also be incorporated into iterative algorithms for signal restoration under more complex degradations. When the degradation model is known, frameworks like Plug-and-Play can be used to combine our denoising method with degradation-specific reconstruction steps.\n\nOur method remains applicable to other types of challenging degradations when embedded within an iterative reconstruction framework that explicitly accounts for the degradation process, such as Plug-and-Play.\n\n**Visualizations of Denoised Data:** We thank the reviewer for this helpful suggestion. In response, we have added visualizations that display the noisy inputs, the corresponding denoised outputs, and the ground truth signals. These examples — now presented in [Figure 2](https://anonymous.4open.science/r/Figures_Manifold_Traversal-8D25/Figures.pdf) (noisy gravitational wave (GW), denoised GW, and ground truth GW) and [Figures 5, 6, 7] (https://anonymous.4open.science/r/Figures_Manifold_Traversal-8D25/Figures.pdf) (ground truth image, noisy image, and denoised image) — offer qualitative evidence of the effectiveness of our method and clearly demonstrate its ability to recover clean signals from noisy observations.\n\n**Closing Comment:** We sincerely thank the reviewer for their thoughtful feedback and constructive suggestions. We're glad that the core ideas and contributions of our work resonated with you, and we truly appreciate your comments, which helped us further improve our work.", "claims_and_evidence": "Yes, I list the details in the [Other Strengths And Weaknesses] section.", "methods_and_evaluation_criteria": "Yes, I list the details in the [Other Strengths And Weaknesses] section.", "theoretical_claims": "Yes, I checked part of the theoretical results.", "experimental_designs_or_analyses": "Yes, I checked the experimental designs and results analysis.", "relation_to_broader_scientific_literature": "I list the details in the [Other Strengths And Weaknesses] section.", "essential_references_not_discussed": "The authors have discussed the most important and related works.", "other_strengths_and_weaknesses": "Strengths\n\n1) The paper introduces a novel method that translates the denoising process into an optimization problem over a manifold, leveraging Riemannian optimization techniques. It provides a new perspective on denoising.\n\n2) The proposed method is efficiency. The approach is computationally efficient, particularly in high-dimensional settings, and scales well with the size of the dataset and dimensionality.\n\n3) The introduction of mixed-order traversal which combines first-order and zero-order steps is interesting. It ensures robust convergence towards global minima, enhancing the reliability of the optimization process.\n\n4) The idea of online learning is also novel. Its ability to build necessary structures on-the-fly as data points are encountered is a pioneering aspect, allowing for real-time adaptability and efficiency.\n\n5) In addition, the authors not only provided the theoretical analyses with near-optimal denoising guarantees, but also conducted experiments on both synthetic manifolds as well as scientific and imagery data.\n\n\n\nWeaknesses\n1) I am wondering if due to some privacy policy, one only collected a very few noisy samples (e.g., in a very extreme case, a single noisy data), will this method still work? Since the noisy samples are very small, then the online learning strategy may not work as expected.\n2) The other extreme case, for large-scale, complex image data with different kinds of noise, saying the noise from this benchmark (https://github.com/hendrycks/robustness), how would this method work?", "other_comments_or_suggestions": "It would be very nice to see some visualization results showing the noisy data and the denoised results.", "questions_for_authors": "I list some of my questions in the [Other Strengths And Weaknesses] section.", "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": "4l0RbZJU0j", "reviewer": "Reviewer_PJMj", "summary": "This paper addresses the problem of efficiently denoising new noisy data sampled from an unknown manifold M, relying only on noisy samples. To this end, a framework for test-time efficient manifold denoising was proposed. In the theoretical analyses, the optimality of the proposed methods was elucidated. In the experimental analyses, complexity-performance tradeoffs compared to baseline methods were examined on scientific and imagery data.\n\nUpdate after rebuttal\nI checked all responses and comments from authors and reviewers. Some of my questions were addressed in the rebuttal. Therefore, I keep my score.", "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 reviewer for their appreciation of our writing and theoretical analysis. At the core of our work is a novel, efficient and accurate algorithm for manifold denoising, which reframes learning-to-denoise as learning-to-optimize. Our key technical innovations includes an accurate and efficient mixed-order method, and a scalable online learning algorithm that learns to optimize from only noisy data. This design enables our method to scale effectively to large, high-dimensional datasets, and to practical scenarios where the manifold is unknown and only noisy samples are available.\n\nBelow, we present additional experiments and explanations. We also conducted an ablation study ([Figure 3](https://anonymous.4open.science/r/Figures_Manifold_Traversal-8D25/Figures.pdf)), which shows the superiority of mixed-order over both first- and zeroth-order methods. All new experimental results are available at https://anonymous.4open.science/r/Figures_Manifold_Traversal-8D25/Figures.pdf.\n\n**Connection to Larger Architectures:** Thank you for your insightful comment. Denoising serves as a critical building block for diffusion-based signal generation and signal recovery (compressed sensing (CS)). Our theory demonstrates that mixed-order optimization solves the manifold denoising problem efficiently and accurately — with a number of operations that scales well in the ambient dimension, and a mean-squared error which is close to statistically optimal. These properties have implications for the efficiency and performance of architectures that use denoising as a building block: the overall number of operations is bounded by the number of diffusion/CS outer loop step times the number of operations used by the denoiser. Moreover, in denoising-based CS reconstruction, there is a direct relationship between the MSE of the denoiser and the MSE of CS reconstruction [Metzler et al, 2016]. By reframing the denoising problem (inner loop) as the optimization problem, which is within the outer loop of tasks such as signal reconstruction, we can consolidate these two loops into a single optimization framework, which could yield significant improvements in computation. We leave this direction to future work.\n\n**Additional Experimental Analyses:** We sincerely thank the reviewer for suggestions. We have conducted additional experiments on real-world RGB images to further demonstrate the denoising capability of our method. In the scenario where only a single noisy image is available, the training error curve shows a clear decreasing trend [Figures 5, 6, and 7](https://anonymous.4open.science/r/Figures_Manifold_Traversal-8D25/Figures.pdf). In the case with large-scale data, we see that the method is able to learn meaningful structure of real-world image patches ([Figure 8](https://anonymous.4open.science/r/Figures_Manifold_Traversal-8D25/Figures.pdf)). In our next work, we will integrate the proposed method into larger architectures, such as CS and diffusion models.\n\n**Additional Baseline:** We thank the reviewer for the helpful and constructive feedback. As an additional baseline, we have added nonlinear autoencoders, which are generic learning architectures that capture low-dimensionality. Our mixed-order method — designed to exploit optimization structure of denoising problems and manifold structure of data — achieves a substantially better accuracy-complexity trade-off compared to autoencoders ([Figure 4](https://anonymous.4open.science/r/Figures_Manifold_Traversal-8D25/Figures.pdf)), further highlighting the efficiency of our approach. We will add this comparison to the final manuscript. For more details, we kindly refer the reviewer to our response ( paragraph [Connection to Diffusion Models]) to Reviewer eTvP due to space limitation.\n\n**Large-Scale Data Denoising:** We appreciate the reviewer’s feedback regarding the exploration of larger-scale data. We have applied our method to real-world large-scale image data and performed  denoising at the patch level. We use images from ImageNet with additive Gaussian noise on 1,310,000 patches. **The results on large-scale data further demonstrate our method's denoising ability([Figure 8](https://anonymous.4open.science/r/Figures_Manifold_Traversal-8D25/Figures.pdf)).**\n\n**Improved Documentation of Experimental Setup:** We sincerely thank the reviewer for highlighting the importance of clarifying experimental setup and algorithmic details. Reproducibility is instrumental to progressing science. We will give more details in the supplementary material in the revised manuscript, e.g., computation of incremental PCA for efficient tangent space estimation, definitions of projections, and other details. We will also release all code and data for reproducibility our work.\n\n**Closing Comment:**\nWe sincerely thank the reviewer for their time and thoughtful feedback. We hope our responses effectively addressed and clarified the thoughtful questions posed by the reviewer.", "claims_and_evidence": "The main problems addressed in the paper are identified by “Learned denoisers play a fundamental role in various signal generation (e.g., diffusion models) and reconstruction (e.g., compressed sensing) architectures, whose success derives from their ability to leverage low-dimensional structure in data.” \n\nIn the theoretical analyses, convergence properties of the proposed methods, such as convergence regions and rates, were analyzed. However, these properties were not associated with those of the methods (e.g. diffusion and CS models) considered in the main problem definition.\n\nIn the experimental analyses, the proposed methods were examined on synthetic manifolds and High-Dimensional Scientific Data. However, further analyses on several additional tasks in comparison with the aforementioned models should be given.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria make sense for the problem or application at hand, but limited.", "theoretical_claims": "Theoretical analyses are clear, and I enjoyed the proofs. However, further comparison with the other baselines and related models would improve the novelty and merit of the results.", "experimental_designs_or_analyses": "As mentioned in the previous comments, the proposed methods are evaluated in limited settings. The experimental analyses should be improved by comparing the proposed methods with additional baselines and related work using larger models on larger scale datasets.", "relation_to_broader_scientific_literature": "As mentioned above, the paper is well written in general. However, theoretical and experimental analyses and results are limited, and should be improved in comparison with the other denoising methods.", "essential_references_not_discussed": "Most of the major prior work were considered in the literature review.", "other_strengths_and_weaknesses": "The paper is well written and mathematical results are clear. However, explanation of experimental setups and results should be improved. Moreover, authors should describe how they define and compute projections and solve the optimization problems given in the algorithms in the experimental analyses. Since these details are omitted, implementation of the algorithms is not trivial and reproduction of the results can be challenging.", "other_comments_or_suggestions": "Please see the above comments.", "questions_for_authors": "Please see the above comments.", "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": "AV0b1zChZd", "reviewer": "Reviewer_eTvP", "summary": "The paper considers the problem of constructing efficient denoisers that map noisy samples from a manifold to the manifold. An online learning approach is used to construct a graph for optimization, and a mixed-order method is used to aid optimization in order to achieve good performances. Theoretical analyses are provided, and experiments are performed to demonstrate the effectiveness of the proposed approach.\n\n## update after rebuttal\n\nThe authors provided more evidence that further strengthens the paper. I keep my original score, weak accept, and did not increase it as I am not that familiar with the task in general.", "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 deeply appreciate the reviewer’s positive feedback and insightful suggestions! We are delighted that the reviewer found our proposed method satisfactory and valued both the supporting experimental results (particularly the strong performance compared to the natural baseline of nearest neighbor search) and the accompanying theoretical analysis. \n\nBelow, we address the reviewer’s questions regarding the connection between our method and diffusion models, and we present an ablation study of the mixed-order method, as suggested. Additionally, we conducted further experiments demonstrating that our method also outperforms AutoEncoders, a widely\nused generic learning baseline. All updated experimental results are available at [Figures.pdf](https://anonymous.4open.science/r/Figures_Manifold_Traversal-8D25/Figures.pdf) (https://anonymous.4open.science/r/Figures_Manifold_Traversal-8D25/Figures.pdf).\n\n**Ablation Study:** We thank the reviewer for this excellent idea! We conducted the suggested ablation study on the mixed-order method by selectively removing the first-order or zero-order optimization components one at a time. The results in [Figure 3](https://anonymous.4open.science/r/Figures_Manifold_Traversal-8D25/Figures.pdf)  confirm that mixed-order optimization has significant advantages over both first- and zeroth-order optimization for efficient, high-accuracy denoising. \n\nIn [Figure 3](https://anonymous.4open.science/r/Figures_Manifold_Traversal-8D25/Figures.pdf), we observe that the first-order optimization incurs the lowest computational cost. As expected, it also yields the highest error, due to getting stuck at local minima. In the high-accuracy regime, our mixed-order optimization achieves a more favorable complexity–accuracy tradeoff compared to zero-order optimization. This advantage arises because zero-order methods are less efficient when operating over dense graphs. Conversely, in the low-accuracy regime where the underlying graph is sparse, zero-order optimization slightly outperforms the mixed-order method. This is expected, as in sparse graphs the mixed-order method essentially relies only on its zero-order steps, behaving similarly to pure zero-order optimization.\n\n**Connection to Diffusion Models:** As reviewer pointed out, diffusion models use generic learning architectures. To further validate our approach, we conducted additional experiments comparing our method with AutoEncoders -- a natural generic learning baseline designed to exploit low-dimensional structure in data. As illustrated in [Figure 4](https://anonymous.4open.science/r/Figures_Manifold_Traversal-8D25/Figures.pdf), our mixed-order optimization method -- designed to exploit both the optimization structure of the denoising problem and the manifold structure of the data -- achieves a substantially better accuracy-complexity trade-off compared to the autoencoder. This further highlights the efficiency and effectiveness of our approach. We will add this comparison to the final version of the manuscript. Below we describe the details of this experiment. \n\nTo perform an extensive comparison to Autoencoders as baseline, we create eleven different networks with various depths and widths and symmetric encoder/decoders. The widest autoencoder layer has width equal to the data dimensionality, and the smallest bottleneck equals 2. The shallowest autoencoder (which appears as the point on the low-right corner of [Figure 4](https://anonymous.4open.science/r/Figures_Manifold_Traversal-8D25/Figures.pdf)), has one layer in the encoder, and one in the decoder. The deepest autoencoder has 10 layers in the encoder, and 10 in the decoder. As we can see in [Figure 4](https://anonymous.4open.science/r/Figures_Manifold_Traversal-8D25/Figures.pdf), while autoencoders can achieve slightly higher accuracy, our method exhibits significantly better efficiency-accuracy tradeoffs -- by orders of magnitude. In our work, we notice that varying the $R(i)$ parameter in our mixed-order method improves accuracy of manifold traversal, and we plan to explore further in this direction in future work.\n\nSince the denoiser is a critical building block of diffusion models and most test-time compute is being spent on denoising, improving its test-time efficiency can significantly accelerate the overall process. As part of our immediate next work, we plan to integrate the proposed method into diffusion models to further explore this direction.\n\nWe also appreciate the reviewer’s careful attention to detail, which has helped us improve the clarity and presentation of the paper. We will fix the typos in the final manuscript.\n\n**Closing Comment:** We sincerely thank the reviewer for their valuable feedback and thoughtful suggestions. We hope our rebuttal has effectively addressed the comments and questions. We would be glad to further discuss or clarify any additional questions.", "claims_and_evidence": "The claims are supported by mathematical proofs and empirical experiments.", "methods_and_evaluation_criteria": "The method is shown to outperform the nearest neighbor approach, which is a natural baseline, and I find the proposed method satisfying. My minor complaint is in the abstract the paper is motived using diffusion models, to some degree drawing expectation that a neural approach will be employed, yet the proposed method is largely graph based.", "theoretical_claims": "The claims on Riemannian optimization are generally standard. I did not check the claims in theoretical analysis section.", "experimental_designs_or_analyses": "The presented experiments are generally well-motivated, and I find the experimental settings sound and valid.", "relation_to_broader_scientific_literature": "The paper considers combining graph-based traversal with Riemannian optimization, which are both established methods.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "In terms of strengths, much theoretical analysis is provided to justify the proposed method. It is interesting that the proposed method outperforms the nearest neighbor approach.", "other_comments_or_suggestions": "Page 2, second column, line 97: \"Literature on Reimannian Optimization\": should be \"Literature on Riemannian optimization\"\n\nPage 3, first column, line 147-153 and also later: \"The projection problem (4)\", \"The optimization problem (4)\", but the equation is not given a label\n\nPage 5, caption of Figure 4: \"point q is a local minimizer of q over M\", I think the second q should be replaced by the objective", "questions_for_authors": "The paper proposes using both first order and zeroth order Riemannian optimization. It can be interesting to provide an ablation study on the effect of removing one of them.", "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: The paper proposes a new mixed-order optimization method for manifold denoising (which, in the case of Gaussian noise, is equivalent to minimizing a quadratic function over the manifold). This is a natural problem whose efficient solution could potentially be useful in many settings. However, first-order methods can get stuck due to non-convexity, and to resolve this the authors propose an "edge-growing" scheme that allows local descent to escape bad optima. Statistical analysis is provided in support of this approach, and the authors show that the sample complexity dependence is linear in the ambient dimension and exponential in the manifold dimension, which isn't too bad for very low dimensional surfaces.

All reviewers concurred that the paper makes solid contributions and recommended an accept. My one big concern -- which prevents me from giving a higher score -- is the lack of compelling experiments; Section 8 is disappointingly brief. Given that the algorithm is natural and not too hard to implement, consider including more experimental evidence for more realistic denoising problems.
Decision: Accept (poster)