Data driven estimation of Laplace-Beltrami operator
Approximations of Laplace-Beltrami operators on manifolds through graph Laplacians have become popular tools in data analysis and machine learning. These discretized operators usually depend on bandwidth parameters whose tuning remains a theoretical and practical problem. In this paper, we address this problem for the unnormalized graph Laplacian by establishing an oracle inequality that opens the door to a well-founded data-driven procedure for the bandwidth selection. Our approach relies on recent results by Lacour and Massart [LM15] on the so-called Lepski's method.
This paper provides a method for choosing the bandwidth parameter of a point cloud Laplacian (but introduces other parameters in its place).  Theoretical guarantees and a minimalistic numerical experiment are provided as evidence of usefulness of the technique.
I am unqualified to assess the theoretical significance of this paper but am quite concerned about the practicality.  My key concern about this paper is that it does not seem to improve the state of affairs re: parameters needed for Laplacian approximations.  In particular, the abstract/intro led me to believe the paper was going to alleviate the need to choose a bandwidth parameter for the Laplacian (a very worthy task!).  But in reality, the technique still has parameters a, b, and the paper says "calibration of the constants a and b in practice is beyond the scope" (line 92).  If this is the case, what is the value of the current paper?  The restrictions described at the beginning of sec 5.1 are similarly concerning.  Beyond this, the numerical experiments are far too minimal.  Recovering the Laplacian of a sphere does not represent the noise and geometry typically encountered in machine learning.  Other comments:  - There are quite a few spelling mistakes and other typos that should be fixed; rather than list them here I will encourage the authors to run "spell check"  - You can say "Lepski's method" instead of "the Lepski's method"  - Say early on (e.g. in sec 1) whether the dimension d should be known a priori for this method to be useful.  (Perhaps a relevant citation is "Testing the Manifold Hypothesis" by Fefferman and colleagues)  - l. 32 -- cite papers instead of saying "known results"  - l. 39 -- define "contrast"  - The assumption that H is finite (line 67) seems quite limiting and does not align with e.g. choosing the width of a Gaussian kernel  - I am a little confused about the density function P discussed around eq (2).  In particular, how does P interact with the parameterization chosen in eq (1)?  Is it possible for the isotropic kernel in eq (1) to deal with irregular or unevenly-distributed P's?  - The explanation at the beginning of sec 2.1 of Lepski's method was *very* dense for an inexperienced reader.  Please add equations and/or a concrete example rather than just describing from a high level in words.   - l. 79 "thus seems natural" -- why?  - In eq (3), it seems that h depends on f.  Is this right?  If so, does that make the Laplacian nonlinear?  - In prop 2.1, I am unclear what it means to have a formula for V(h).  It appears above that V(h) is *any* bound satisfying the condition in line 89.  Is this an upper bound for V(h)?  A formula that satisfies the definition?  - The heuristic in lines 170-177 comes out of thin air.  Please provide justification or at least intuition.