On empirical Hodge Laplacians under the manifold hypothesis Jan-Paul Lerch, Martin Wahl, Petr Zamolodtchikov Abstract Given i.i.d. observations uniformly distributed on a closed submanifold of the Euclidean space, we study higher-order generalizations of graph Laplacians, so-called Hodge Laplacians on graphs, as approximations of the Laplace-Beltrami operator on differential forms. Our main result is a high-probability error bound for the associated Dirichlet forms. This bound improves existing Dirichlet form error bounds for graph Laplacians in the context of Laplacian Eigenmaps, and it provides insights into the Betti numbers studied in topological data analysis and the complementing positive part of the spectrum. † † 2020 Mathematics Subject Classification. 62R30, 62R40, 53Z50, 35K08, 05C80 Key words and phrases. Graph Laplacian, Hodge Laplacian on a graph, point cloud, manifold hypothesis, Laplace-Beltrami operator on differential forms, heat semigroup, heat kernel, Hodge theory, perturbation theory, U-statistics. 1 Introduction Methods of dimensionality reduction uncover hidden information from complex data sets and high-dimensional observations. Leading examples are principal component analysis and its nonlinear extensions to kernel principal component analysis or manifold learning. Due to the availability of large amount of data, such methods have become indispensable tools throughout science and engineering. Principal component analysis is a basic linear dimensionality reduction method, in which the data is projected onto the linear space spanned by the leading eigenvectors of the empirical covariance matrix [ 33 ] . This allows to reduce the dimension, while preserving as much variation in the data as possible. Despite being a classical topic, principal component analysis is still intensively studied and exhibits many different phenomena in high dimensions [ 32 , 52 , 34 , 31 ] . In contrast, Laplacian Eigenmaps and Diffusion Maps are instances of nonlinear dimensionality reduction. They are typically used under the so-called manifold hypothesis, where the data is assumed to be sampled from a low-dimensional submanifold in a high-dimensional Euclidean space [ 4 , 14 ] . They are based on different graph Laplacians (unnormalized graph Laplacians, random walk graph Laplacian, etc.) and their spectral characteristics, which carry important information about the geometry of the underlying graph [ 13 ] . The study of the spectral properties of graph Laplacians as approximations of Laplace-Beltrami operators was initiated in [ 5 ] and has since been explored using various approaches [ 6 , 23 , 10 , 22 , 12 ] , including connections to kernel principal component analysis [ 51 ] . Higher-order Laplacians are studied in the context of Hodge theory. Classical Hodge theory on Riemannian manifolds is defined in terms of the de Rham complex of differential forms on smooth manifolds and leads to the Laplace-Beltrami operator on differential forms. Analyzing the spectrum of the Laplace-Beltrami operator on \ell -forms [ 45 ] , particularly its null space, reveals fundamental topological information. For instance, the multiplicity of the zero eigenvalue corresponds to the \ell -th Betti number by Hodge’s theorem. These concepts have been extended in various directions including simplicial complexes [ 18 , 17 ] , metric measure spaces [ 3 , 27 ] and weighted graphs [ 37 ] . A relationship between random walks on simplicial complexes and higher-order (combinatorial) Laplacians has been established in [ 42 , 43 ] . In a complementary but related line of research, topological data analysis aims to provide statistical and algorithmic methods to understand the topological structure of data [ 7 ] . One of its most prominent techniques is persistent homology [ 19 ] and their associated persistent Betti numbers, an extension of classical Betti numbers designed to capture topological structures that persist across scales. Significant statistical work has been conducted on these in a topological context [ 9 ] and in the context of generic chain complexes [ 24 ] . Notably, both persistent homology and Hodge theory can be formulated algebraically as spectral problems [ 49 ] . In this paper, we deal with the statistical analysis of data supported on a submanifold in a high-dimensional Euclidean space and consider the problem of approximating the Laplace-Beltrami operator on differential forms by appropriate empirical Hodge Laplacians. Inspired and guided by results in [ 30 , 3 , 37 , 27 ] , we construct an empirical exterior calculus, empirical \ell -forms, and an empirical Hodge Laplacian. Building on this, we turn to the statistical analysis of such empirical Hodge-Laplacians under the manifold hypothesis, and establish a non-asymptotic error bound for the associated empirical Dirichlet form. This upper bound provides a first step towards more sophisticated spectral convergence and approximation results, including the analysis of the Betti numbers studied in topological data analysis and the complementing positive part of the spectrum. Moreover, specialized to the empirical graph Laplacian, we improve existing Dirichlet form convergence rates in the context of Laplacian Eigenmaps and Diffusion Maps [ 22 , 11 ] . In the proof, we combine tools from exterior calculus, matrix analysis, geometric analysis on Riemannian manifolds [ 25 ] , and the theory of U-statistics [ 41 ] . The paper is organized as follows. In Section 2 we provide a brief introduction to weighted Hodge Laplacians on a graph, followed by a discussion of empirical \ell -forms in Section 3 . The Laplace–Beltrami operator in the context of Riemannian manifolds is discussed in Section 4 laying the fundament for the formulation of the main result in Theorem 1 stated in Section 5 . Sections 6 and 7 are dedicated to the proof of Theorem 1 , and Section 8 implements numerical experiments. Basic notation For a natural number n\geq 1 the symmetric group on n elements is denoted by S_{n} . I_{n} denotes the n\times n identity matrix. For a subset J\subseteq\{1,\dots,n\} , we denote by J^{\complement} the complement of J in \{1,\dots,n\} . For q\geq 1 and a real-valued random variable X on a probability space (\Omega,\mathcal{F},\mathbb{P}) we write \|X\|_{L^{q}}=\mathbb{E}^{1/q}|X|^{q} for the L^{q} norm. Similarly, for q=\infty we write \|X\|_{L^{\infty}} for the (essential) supremum norm. Throughout the paper, C>0 denotes a constant that may change from line to line (by a numerical value). 2 Hodge Laplacians on graphs Hodge Laplacians on graphs are higher-order generalizations of graph Laplacians. They can be interpreted as discrete analogous of Hodge theory on Riemannian manifolds, and they have been first introduced in the context of simplicial complexes. In this section, we summarize some basic elements and formulas of this theory in a form suitable for our study. Similar treatments can be found in [ 3 , 37 ] . Let V=\{X_{1},\dots,X_{n}\} be a finite set of data points (in a Euclidean space). We call a function \boldsymbol{\omega}:V^{\ell+1}\rightarrow\mathbb{R} an \ell -form if it is alternating, that is \displaystyle\boldsymbol{\omega}(X_{i_{\sigma(0)}},\dots,X_{i_{\sigma(\ell)}})=\operatorname{sgn}(\sigma)\boldsymbol{\omega}(X_{i_{0}},\dots,X_{i_{\ell}}) for all i_{0},\dots,i_{\ell}\in\{1,\dots,n\} and all \sigma\in S_{\ell+1} . Given positive and symmetric weights (k_{i_{0}\cdots i_{\ell}}) , we denote by L^{2}_{\wedge}(V^{\ell+1}) the Hilbert space of all \ell -forms endowed with the inner product \displaystyle\langle\boldsymbol{\omega},\boldsymbol{\eta}\rangle_{n}=\tfrac{1}{(\ell+1)!}\sum_{i_{0},\dots,i_{\ell}=1}^{n}k_{i_{0}\cdots i_{\ell}}\boldsymbol{\omega}(X_{i_{0}},\dots,X_{i_{\ell}})\boldsymbol{\eta}(X_{i_{0}},\dots,X_{i_{\ell}}). (1) Using the alternating property and the symmetry of the weights, we can also write \displaystyle\langle\boldsymbol{\omega},\boldsymbol{\eta}\rangle_{n}=\sum_{1\leq i_{0}<\dots0 , and all f\in C^{\infty}(\mathcal{M}) , where dy denotes the volume measure induced by the Riemannian metric on \mathcal{M} . The heat kernel k_{t} is symmetric, positive, and satisfies \int_{\mathcal{M}}k_{t}(x,y)\,dy=1 for all x\in\mathcal{M} . For more background see [ 45 , 25 , 54 ] . For \ell\geq 0 , let \Omega^{\ell}(\mathcal{M}) be the set of all smooth differential \ell -forms, let d be the exterior differentiation operator, and let \wedge be the wedge product. The Riemannian metric defines an inner product \langle\cdot,\cdot\rangle_{x} on the cotangent space at point x , leading to a global inner product \int_{\mathcal{M}}\langle\cdot,\cdot\rangle_{x}\,dx on \Omega^{1}(\mathcal{M}) . Similarly, the inner product induces an inner product on \Omega^{\ell}(\mathcal{M}) , which we denote by \langle\cdot,\cdot\rangle . In what follows it is important that if f_{1},\dots,f_{\ell}\in C^{\infty}(\mathcal{M}) , then \displaystyle\langle df_{1}\wedge\dots\wedge df_{\ell},df_{1}\wedge\dots\wedge df_{\ell}\rangle=\int_{\mathcal{M}}\det\begin{pmatrix}\langle df_{1},df_{1}\rangle_{x}&\ldots&\langle df_{1},df_{\ell}\rangle_{x}\\ \vdots&\ddots&\vdots\\ \langle df_{\ell},df_{1}\rangle_{x}&\ldots&\langle df_{\ell},df_{\ell}\rangle_{x}\end{pmatrix}\,dx and the individual inner products \langle df_{a},df_{b}\rangle_{x} coincide with the carré du champ operator of f_{a} and f_{b} . Again, the above information can be summarized into the de Rham cochain complex \textstyle{0\ignorespaces\ignorespaces\ignorespaces\ignorespaces} \textstyle{\Omega^{0}(\mathcal{M})\ignorespaces\ignorespaces\ignorespaces\ignorespaces} \scriptstyle{d_{0}} \textstyle{\Omega^{1}(\mathcal{M})\ignorespaces\ignorespaces\ignorespaces\ignorespaces} \scriptstyle{d_{1}} \textstyle{\cdots\ignorespaces\ignorespaces\ignorespaces\ignorespaces} \scriptstyle{d_{\ell-1}} \textstyle{\Omega^{\ell}(\mathcal{M})\ignorespaces\ignorespaces\ignorespaces\ignorespaces} \scriptstyle{d_{\ell}} \textstyle{\cdots,} which is the differential counterpart to ( 2 ). Finally, for each \ell\geq 0 , let d_{\ell}^{*} be the adjoint of d_{\ell} with respect to \langle\cdot,\cdot\rangle . Then the up and down Laplace-Beltrami operators on \ell -forms are \displaystyle\Delta_{\ell}^{\up}=d_{\ell}^{*}d_{\ell},\qquad\Delta_{\ell}^{\down}=d_{\ell-1}d_{\ell-1}^{*}. and the Laplace-Beltrami operator on \ell -forms are \Delta_{0}=\Delta_{0}^{\up} and \displaystyle\Delta_{\ell}=\Delta_{\ell}^{\up}+\Delta_{\ell}^{\down}=d_{\ell}^{*}d_{\ell}+d_{\ell-1}d_{\ell-1}^{*} for \ell\geq 1 . Similarly as in the graph theoretic setting, an Hodge decomposition holds stating that \Omega^{\ell}(\mathcal{M})=\operatorname{im}(d_{\ell-1})\oplus\ker(\Delta_{\ell})\oplus\operatorname{im}(d_{\ell}^{*}) . Moreover, topological information is contained in \ker(\Delta_{\ell}) , which is isomorphic to the \ell th de Rham cohomology group. For more details, see [ 45 ] . 5 Main result: Dirichlet form error bound 5.1 Assumptions and main result The main goal of this paper is to relate \mathscr{L}_{\ell-1}^{\up} to \Delta_{\ell-1}^{\up} in the case that V=\{X_{1},\dots,X_{n}\} is a sample of independent and identical distributed points in a submanifold of the Euclidean space. Assumption 1 (Manifold hypothesis) . Let X_{1},\dots,X_{n} be independent and identical distributed random variables uniformly distributed in a closed and connected submanifold \mathcal{M}\subseteq\mathbb{R}^{p} with \dim(\mathcal{M})=d and \operatorname{vol}(\mathcal{M})=1 . The manifold hypothesis is crucial in modern theory of machine learning [ 38 ] . Under Assumption 1 , the empirical Hodge Laplacian can be analyzed as an approximation of the Laplace-Beltrami operator. In this paper, we make a first step in this direction and study the quadratic form \langle\boldsymbol{\omega},\mathscr{L}_{\ell-1}^{\up}\boldsymbol{\omega}\rangle_{n} as approximations of the Dirichlet form or energy \langle\omega,\Delta_{\ell-1}^{\up}\omega\rangle for certain (empirical) \ell -forms \omega and \boldsymbol{\omega} . More precisely, for a fixed set f_{1},\dots,f_{\ell}\in C^{\infty}(\mathcal{M}) and its restrictions \mathbf{f}_{1},\dots,\mathbf{f}_{\ell}\in L^{2}_{\wedge}(V) to the data points, we consider \displaystyle\omega=f_{1}(df_{2}\wedge\dots\wedge df_{\ell}),\qquad\boldsymbol{\omega}=\mathbf{f_{1}}(\delta\mathbf{f}_{2}\wedge\dots\wedge\delta\mathbf{f_{\ell}})\in L^{2}_{\wedge}(V^{\ell}) (12) As weights, we consider \displaystyle k_{i_{0}\dots i_{\ell}}=\frac{1}{\binom{n}{\ell+1}}\frac{\ell!}{(2t)^{\ell}}\Big(\frac{1}{\ell+1}\sum_{a=0}^{\ell}\prod_{\begin{subarray}{c}b=0\\ b\neq a\end{subarray}}^{\ell}k_{t}(X_{i_{a}},X_{i_{b}})\Big) (13) for all i_{0},\dots,i_{\ell}\in\{1,\dots,n\} and all \ell\geq 0 , and with time parameter t>0 . See also equation (42) in [ 27 ] and equation (3) in [ 3 ] . Here, k_{t} denoted the heat kernel on \mathcal{M} , as introduced in Section 4 . With the choice ( 13 ), we call \mathscr{L}_{\ell-1}^{\up} the empirical up Hodge Laplacian and we call \langle\boldsymbol{\omega},\mathscr{L}_{\ell-1}^{\up}\boldsymbol{\omega}\rangle_{n} the empirical Dirchlet form. Our analysis will be based on the following quantitative boundedness and smoothness conditions on the heat kernel k_{t} and the functions f_{1},\dots,f_{\ell} . Assumption 2 (Global heat kernel bound) . There are constants c_{1},C_{1}>0 such that \displaystyle k_{t}(x,y)\leq\frac{C_{1}}{t^{d/2}}\exp\Big(-c_{1}\frac{d_{\mathcal{M}}(x,y)^{2}}{t}\Big). for all x,y\in\mathcal{M} and all t\in(0,1] . Here d_{\mathcal{M}} denotes the intrinsic distance on \mathcal{M} . Assumption 3 (Smoothness properties) . There is a constant C_{2}>0 such that \displaystyle\|f_{a}\|_{L^{\infty}},\|\Delta(f_{a}f_{b})\|_{L^{\infty}},\Big\|\Big(\frac{e^{-t\Delta}-I+t\Delta}{t^{2}}\Big)(f_{a}f_{b})\Big\|_{L^{\infty}}\leq C_{2}, for all 0\leq a,b\leq\ell , where f_{0}\equiv 1 . Note that both assumptions are satisfied for \mathcal{M} closed (see [ 26 ] ) and smooth functions f_{1},\dots,f_{\ell} . Their particular purpose is to introduce the constants c_{1},C_{1},C_{2} that are important for our analysis. We now state our main result. Theorem 1 . Let t\in(0,1] and A>0 be real numbers and let \ell\geq 0 and n\geq 2+2\ell be natural numbers. Moreover, suppose \mathscr{L}_{\ell-1}^{\up} is the empirical up Hodge Laplacian based on the sample X_{1},\dots,X_{n} satisfying Assumption 1 and having the weights (k_{i_{0}\cdots i_{\ell}}) introduced in ( 13 ). Furthermore, let f_{1},\dots,f_{\ell}\in C^{\infty}(\mathcal{M}) and let \omega=f_{1}(df_{2}\wedge\dots\wedge df_{\ell}) and \boldsymbol{\omega}=\mathbf{f_{1}}(\delta\mathbf{f}_{2}\wedge\dots\wedge\delta\mathbf{f_{\ell}}) as introduced in ( 12 ). Finally, let \Delta^{\up}_{\ell-1} be the up Laplace-Beltrami operator on \mathcal{M} and suppose that Assumptions 2 and 3 are satisfied. Then, with probability at least 1-n^{-A} , we have \displaystyle\Big|\langle\boldsymbol{\omega},\mathscr{L}_{\ell-1}^{\up}\boldsymbol{\omega}\rangle_{n}-\langle\omega,\Delta_{\ell-1}^{\up}\omega\rangle\Big|\leq C\Big(t+\sum_{j=1}^{\ell+1}\Big(\frac{(\log n)^{j/2}}{t^{d(j-1)/4}n^{j/2}}+\frac{(\log n)^{(j+1)/2}}{t^{d(j-1)/2}n^{(j+1)/2}}\Big)\Big), where C>0 is a constant depending only on \ell,A,c_{1},C_{1},C_{2} . The proof of Theorem 1 is given in Sections 6 – 7 . More precisely, in Section 6 , we study the approximation error \langle\omega,\Delta_{\ell-1}^{\up}\omega\rangle-\mathbb{E}\langle\boldsymbol{\omega},\mathscr{L}_{\ell-1}^{\up}\boldsymbol{\omega}\rangle_{n} , which relates Hodge theory on Riemannian manifolds to continuous Hodge theory on metric spaces. In Section 7 , we study the stochastic error \langle\boldsymbol{\omega},\mathscr{L}_{\ell-1}^{\up}\boldsymbol{\omega}\rangle_{n}-\mathbb{E}\langle\boldsymbol{\omega},\mathscr{L}_{\ell-1}^{\up}\boldsymbol{\omega}\rangle_{n} using the machinery of U-statistics. 5.2 Discussion Comparison to the literature Let us compare our results with the literature, which has so far focused on the case \ell=0 . For \ell=0 , that is in the case of the (un-)normalized graph Laplacians, such and similar bounds have been studied previously in the context of Laplacian Eigenmaps and Diffusion Maps [ 6 , 23 , 22 , 11 , 12 ] . Dirichlet error bounds provide a first important step towards the more sophisticated study of the spectral convergence of graph Laplacians towards the Laplace-Beltrami operator. A state-of-the-art bound in [ 12 ] provides the Dirichlet error rate \max(t,1/(nt^{d/2})) up to log-terms. In contrast, our theorem yield with high probability \displaystyle\big|\langle f,\Delta f\rangle_{n}-\langle\mathbf{f},\mathscr{L}_{0}\mathbf{f}\rangle_{n}\big|\leq C\Big(t+\frac{\log^{1/2}n}{n^{1/2}}+\frac{\log n}{nt^{d/4}}+\frac{\log^{3/2}n}{n^{3/2}t^{d/2}}\Big). In particular, our result shows that the dimension dependence, that is the curse of dimensionality, only appears in lower order terms. An important question is to apply bias reduction techniques to reduce the Ct bias term. Directions for future research The present analysis provides a basis for further investigations of the problem of approximating the Laplace-Beltrami operator on \ell -forms by empirical Hodge Laplacians. First, Theorem 1 provides an concentration bound for the empirical Dirichlet form. This can be seen as a first step towards the study of eigenvalues and eigenforms. In the case of eigenvalues, this can be approached via the min-max characterizations. However, further steps must be implemented first. So far, Theorem 1 is restricted to empirical \ell -forms in contrast to the set of all alternating functions and it depends on the strong smoothness properties in Assumption 3 . Second, our results are stated in terms of the heat kernel, which is unknown to the statistician. It is possible to replace the heat kernel with a Gaussian kernel by combining the analysis in Section 3 of [ 51 ] with Lemma 4 , in order to obtain practical results. Since this requires several further assumptions on the local approximation of the intrinsic distance by the extrinsic distance and of the heat kernel by the geodesic kernel, we have not included this in the current paper and refer to subsequent work. 6 The bias term: continuous Hodge theory 6.1 Main approximation bound In this section we relate \langle\omega,\Delta_{\ell-1}^{\up}\omega\rangle to \displaystyle\mathbb{E}\langle\boldsymbol{\omega},\mathscr{L}_{\ell-1}^{\up}\boldsymbol{\omega}\rangle_{n} \displaystyle=\mathbb{E}\frac{1}{\binom{n}{\ell+1}}\sum_{1\leq i_{0}<\dots0 is a constant depending only on \ell and C_{2} . To prove Proposition 1 , it is necessary to relate differential Hodge theory to continuous Hodge theory [ 3 , 46 , 27 , 28 ] . See e.g. Theorem 1 in [ 3 ] for the matching of cohomology and Corollary 5.2 in [ 28 ] for a related pointwise non-local-to-local convergence result of cotangential structures. 6.2 Technical lemmas The following lemma is a quantitative variant of the approximation of the carré du champ operator through the semigroup ( see Chapter 3 in [ 2 ] ). Lemma 5 . Under the assumptions of Proposition 1 , we have \displaystyle\Big|\langle df_{a},df_{b}\rangle_{x}-\frac{1}{2t}\int_{\mathcal{M}}k_{t}(x,y)(f_{a}(x)-f_{a}(y))(f_{b}(x)-f_{b}(y))\,dy\Big|\leq Ct, for all 1\leq a,b\leq\ell and all x\in\mathcal{M} , where C>0 depends only on C_{2} . Proof. By the product rule, we have \displaystyle\langle df_{a},df_{b}\rangle_{x} \displaystyle=\langle\nabla f_{a},\nabla f_{b}\rangle_{x}=\frac{1}{2}\big(f_{a}\Delta f_{b}+f_{b}\Delta f_{a}-\Delta(f_{a}f_{b})\big)(x)=(*)+(**), (14) where \displaystyle(*)= \displaystyle\frac{1}{2}\Big(-f_{a}\Big(\frac{e^{-t\Delta}-I}{t}\Big)f_{b}-f_{b}\Big(\frac{e^{-t\Delta}-I}{t}\Big)f_{a}+\Big(\frac{e^{-t\Delta}-I}{t}\Big)(f_{a}f_{b})\Big)(x), \displaystyle(**)= \displaystyle\frac{1}{2}\Big(f_{a}\Big(\frac{e^{-t\Delta}-I+t\Delta}{t}\Big)f_{b}+f_{b}\Big(\frac{e^{-t\Delta}-I+t\Delta}{t}\Big)f_{a}\Big)(x)-\frac{1}{2}\Big(\Big(\frac{e^{-t\Delta}-I+t\Delta}{t}\Big)(f_{a}f_{b})\Big)(x), and where \langle\cdot,\cdot\rangle_{x} also denotes the inner product on the tangent space at point x (by some abuse of notation). Now, using ( 11 ) and the fact that k_{t}(x,\cdot) integrates to 1 , we have \displaystyle(*)= \displaystyle-\frac{1}{2t}\int_{\mathcal{M}}k_{t}(x,y)f_{a}(x)f_{b}(y)\,dy-\frac{1}{2t}\int_{\mathcal{M}}k_{t}(x,y)f_{a}(y)f_{b}(x)\,dy \displaystyle+\frac{1}{2t}\int_{\mathcal{M}}k_{t}(x,y)f_{a}(y)f_{b}(y)\,dy+\frac{1}{2t}\int_{\mathcal{M}}k_{t}(x,y)f_{a}(x)f_{b}(x)\,dy \displaystyle= \displaystyle\frac{1}{2t}\int_{\mathcal{M}}k_{t}(x,y)(f_{a}(x)-f_{a}(y))(f_{b}(x)-f_{b}(y))\,dy. On the other hand, by Assumptions 3 , we have that (**) is upper-bounded by (C_{2}^{2}+C_{2}/2)t in absolute value. ∎ The following lemma is the key in order to connect the empirical Dirichlet form in Lemma 4 to an integral approximation of \langle\cdot,\cdot\rangle . Lemma 6 (Andréief’s identity) . Let \nu be a measure on a measurable space \mathcal{X} , and let \phi_{1},\dots,\phi_{\ell}:\mathcal{X}\rightarrow\mathbb{R} be square-integrable. Then we have \displaystyle\det_{\ell\times\ell}\Big(\int_{\mathcal{X}}\phi_{a}(y)\phi_{b}(y)\,\nu(dy)\Big)=\frac{1}{\ell!}\int_{\mathcal{X}^{\ell}}\det_{\ell\times\ell}\left(\phi_{a}(y_{b})\right)^{2}\,\nu(dy_{1})\cdots\nu(dy_{\ell}). Andréief’s identity is a continuous analog of the Cauchy-Binet formula. It is a standard technique in random matrix theory [ 15 ] . Lemma 7 . Let A,B\in\mathbb{R}^{\ell\times\ell} be matrices such that |A_{ij}|\leq a and |A_{ij}-B_{ij}|\leq Ct for all 1\leq i,j\leq\ell and real numbers a>0 , C\geq 1 , and t\in(0,1] . Then we have \displaystyle\big|\det(B)-\det(A)\big|\leq(C(a+1))^{\ell}\ell!t. Lemma 7 follows from an elementary computation using the Leibniz formula for determinants and the binomial formula, and is omitted. We now turn to the proof of Proposition 1 . Proof of Proposition 1 . By the definition of \Delta_{\ell-1}^{\up} and the properties of the inner product \langle\cdot,\cdot\rangle on \Omega^{\ell-1}(\mathcal{M}) defined in Section 4 , we have \displaystyle\langle\omega,\Delta_{\ell-1}^{\up}\omega\rangle \displaystyle=\langle d_{\ell-1}\omega,d_{\ell-1}\omega\rangle=\langle df_{1}\wedge\dots\wedge df_{\ell},df_{1}\wedge\dots\wedge df_{\ell}\rangle=\int_{\mathcal{M}}\det_{\ell\times\ell}\big(\langle df_{a},df_{b}\rangle_{x}\big)dx By Lemma 5 , ( 14 ), and Assumption 3 , we have \displaystyle\Big|\langle df_{a},df_{b}\rangle_{x}-\frac{1}{2t}\int_{\mathcal{M}}k_{t}(x,y)\delta f_{a}(x,y)\delta f_{b}(x,y)\,dy\Big|\leq Ct,\ \text{ and }\ \big|\langle df_{a},df_{b}\rangle_{x}\big|\leq C, for all 1\leq a,b\leq\ell and some constant C>0 depending only on C_{2} . Hence, Lemma 7 yields \displaystyle\Big|\det_{\ell\times\ell}\big(\langle df_{a},df_{b}\rangle_{x}\big)-\det_{\ell\times\ell}\Big(\frac{1}{2t}\int_{\mathcal{M}}\delta f_{a}(x,y)\delta f_{b}(x,y)k_{t}(x,y)dy\Big)\Big|\leq Ct, (15) where C>0 depends only on C_{2} . By Andréief’s identity \displaystyle\det_{\ell\times\ell}\Big(\frac{1}{2t}\int_{\mathcal{M}}\delta f_{a}(x,y)\delta f_{b}(x,y)k_{t}(x,y)dy\Big)=\frac{1}{\ell!}\frac{1}{(2t)^{\ell}}\int_{\mathcal{M}^{\ell}}\det_{\ell\times\ell}\big(\delta_{0}f_{a}(x,x_{b})\big)^{2}\Big(\prod_{b=1}^{\ell}k_{t}(x,x_{b})dx_{b}\Big). (16) Inserting ( 16 ) into ( 15 ), the claim follows from integrating with respect to x and the triangle inequality. ∎ 7 The variance term: concentration of U-statistics 7.1 Main concentration bound In this section we study the stochastic error \langle\boldsymbol{\omega},\mathscr{L}_{\ell-1}^{\up}\boldsymbol{\omega}\rangle_{n}-\mathbb{E}\langle\boldsymbol{\omega},\mathscr{L}_{\ell-1}^{\up}\boldsymbol{\omega}\rangle_{n} using the theory of U-statistics [ 35 , 16 ] . More precisely, we analyze the expression \displaystyle U_{n}(\ell,t)=\frac{1}{\binom{n}{\ell+1}}\sum_{1\leq i_{0}<\dots1 , and f_{1},\dots,f_{\ell}\in C^{\infty}(\mathcal{M}) . Suppose that n\geq 2+2\ell and that Assumptions 1 – 3 are satisfied. Then, with probability at least 1-n^{-A} , we have \displaystyle\Big|U_{n}(\ell,t) \displaystyle-\frac{1}{t^{\ell}}\int_{\mathcal{M}^{\ell+1}}(D(f_{1},\dots,f_{\ell},x_{0},\dots,x_{\ell}))^{2}\Big(\prod_{b=1}^{\ell}k_{t}(x_{0},x_{b})dx_{b}\Big)dx_{0}\Big| \displaystyle\leq C\sum_{j=1}^{\ell+1}\Big(\frac{(\log n)^{j/2}}{t^{d(j-1)/4}n^{j/2}}+\frac{(\log n)^{(j+1)/2}}{t^{d(j-1)/2}n^{(j+1)/2}}\Big), where C is a constant depending only on \ell,A,c_{1},C_{1} and C_{2} . 7.2 The Hoeffding decomposition First, note that h_{t} is symmetric, so that expression ( 17 ) is an U-statistic of order \ell+1 . Since h_{t} is not degenerate, we have to apply the Hoeffding decomposition before we can proceed with the proof of Proposition 2 . We start with some notation. For a function f on \mathcal{M} we write Pf=\mathbb{E}f(X)=\int_{\mathcal{M}}f(x)\,dx . For a symmetric function h:\mathcal{M}^{\ell+1}\rightarrow\mathbb{R} and 0\leq j\leq\ell , we write \displaystyle P^{\ell-j}h(x_{0},\dots,x_{j}) \displaystyle=\mathbb{E}f(x_{0},\dots,x_{j},X_{j+1},\dots,X_{\ell})=\int_{\mathcal{M}^{\ell-j}}f(x_{0},\dots,x_{\ell})\,dx_{j+1}\dots dx_{\ell}. We set \displaystyle h_{t}^{(j)}=(\delta_{x_{0}}-P)\times\dots\times(\delta_{x_{j}}-P)\times P^{\ell-j}h_{t},\qquad x_{0},\dots,x_{j}\in\mathcal{M}. Then h_{t}^{(j)} is a symmetric and degenerate kernel, that is \displaystyle\mathbb{E}h_{t}^{(j)}(x_{0},\dots,x_{j-1},X_{j})=\int_{\mathcal{M}}h_{t}^{(j)}(x_{0},\dots,x_{j-1},x_{j})\,dx_{j}=0 for all x_{0},\dots,x_{j-1}\in\mathcal{M} and the Hoeffding decomposition, see [ 16 , Section 3.5] or [ 35 ] , implies that \displaystyle\frac{1}{\binom{n}{\ell+1}}\sum_{1\leq i_{0}<\dots0 is a constant depending only on c_{1},C_{1},C_{2} and \ell . Here, dx_{J^{\complement}} means \prod_{b\in J^{\complement}}dx_{b} and dx_{J} means \prod_{b\in J}dx_{b} . Proof. Using the Leibniz formula applied to the transpose, we have \displaystyle\begin{split}D^{2}(f_{1},\dots,f_{\ell},x_{0},\dots,x_{\ell})&=\sum_{\sigma,\tau\in S_{\ell}}\prod_{b=1}^{\ell}(f_{\sigma(b)}(x_{b})-f_{\sigma(b)}(x_{0}))(f_{\tau(b)}(x_{b})-f_{\tau(b)}(x_{0}))\\ &\leq\ell!\sum_{\sigma\in S_{\ell}}\prod_{b=1}^{\ell}(f_{\sigma(b)}(x_{b})-f_{\sigma(b)}(x_{0}))^{2},\end{split} (22) where we used the inequality xy\leq(x^{2}+y^{2})/2 and the symmetry in \sigma,\tau\in S_{\ell} . We now consider separately the two cases 0\in J and 0\notin J . First, let 0\in J . Inserting ( 22 ) into ( 20 ) and using the Fubini theorem, we get \displaystyle\int_{\mathcal{M}^{|J^{\complement}|}}\Big(\frac{1}{t^{\ell}}\prod_{b=1}^{\ell}k_{t}(x_{0},x_{b})\Big)\cdot D^{2}(f_{1},\dots,f_{\ell},x_{0},\dots,x_{\ell})\,dx_{J^{\complement}} (23) \displaystyle\leq\ell!\sum_{\sigma\in S_{\ell}}\int_{\mathcal{M}^{|J^{\complement}|}}\prod_{b=1}^{\ell}\frac{1}{t}k_{t}(x_{0},x_{b})(f_{\sigma(b)}(x_{b})-f_{\sigma(b)}(x_{0}))^{2}dx_{J^{\complement}} \displaystyle=\ell!\sum_{\sigma\in S_{\ell}}\prod_{\begin{subarray}{c}b\in J\\ b\neq 0\end{subarray}}\frac{1}{t}k_{t}(x_{0},x_{b})(f_{\sigma(b)}(x_{b})-f_{\sigma(b)}(x_{0}))^{2}\cdot\prod_{b\in J^{\complement}}\int_{\mathcal{M}}\frac{1}{t}k_{t}(x_{0},x_{b})(f_{\sigma(b)}(x_{b})-f_{\sigma(b)}(x_{0}))^{2}dx_{b}\Big). Inserting Lemma 8 the first claim follows in this case. Similarly, \displaystyle\int_{\mathcal{M}^{|J|}}\Big(\int_{\mathcal{M}^{|J^{\complement}|}}\Big(\frac{1}{t^{\ell}}\prod_{b=1}^{\ell}k_{t}(x_{0},x_{b})\Big)\cdot D^{2}(f_{1},\dots,f_{\ell},x_{0},\dots,x_{\ell})\,dx_{J^{\complement}}\Big)^{2}dx_{J} \displaystyle\leq(\ell!)^{3}\sum_{\sigma\in S_{\ell}}\int_{\mathcal{M}^{|J|}}\Big(\int_{\mathcal{M}^{|J^{\complement}|}}\prod_{b=1}^{\ell}\frac{1}{t}k_{t}(x_{0},x_{b})(f_{\sigma(b)}(x_{b})-f_{\sigma(b)}(x_{0}))^{2}\,dx_{J^{\complement}}\Big)^{2}dx_{J}. Proceeding as in ( 23 ), applying Lemma 8 and using the fact that we can also integrate with respect to x_{J} , the second claim follows. Second, let 0\in J^{\complement} . Moreover, let a\in J be arbitrary but fixed. Then \displaystyle\int_{\mathcal{M}^{|J^{\complement}|}}\Big(\frac{1}{t^{\ell}}\prod_{b=1}^{\ell}k_{t}(x_{0},x_{b})\Big) \displaystyle\cdot D^{2}(f_{1},\dots,f_{\ell},x_{0},\dots,x_{\ell})\,dx_{J^{\complement}} \displaystyle\leq\ell!\sum_{\sigma\in S_{\ell}}\int_{\mathcal{M}}\Big[ \displaystyle\prod_{\begin{subarray}{c}b\in J\setminus\{a\}\end{subarray}}\frac{1}{t}k_{t}(x_{0},x_{b})(f_{\sigma(b)}(x_{b})-f_{\sigma(b)}(x_{0}))^{2} \displaystyle\cdot \displaystyle\prod_{b\in J^{c}\setminus\{0\}}\int_{\mathcal{M}}\frac{1}{t}k_{t}(x_{0},x_{b})(f_{\sigma(b)}(x_{b})-f_{\sigma(b)}(x_{0}))^{2}dx_{b} \displaystyle\cdot \displaystyle\frac{1}{t}k_{t}(x_{0},x_{a})(f_{\sigma(a)}(x_{a})-f_{\sigma(a)}(x_{0}))^{2}\Big]\,dx_{0} Inserting Lemma 8 , the first claim follows in this case, ensuring that we integrate with respect to the x_{0} in the last step. Similarly, \displaystyle\int_{\mathcal{M}^{|J|}}\Big[\int_{\mathcal{M}^{|J^{\complement}|}}\Big(\frac{1}{t^{\ell}}\prod_{b=1}^{\ell}k_{t}(x_{0},x_{b})\Big)\cdot D^{2}(f_{1},\dots,f_{\ell},x_{0},\dots,x_{\ell})\,dx_{J^{\complement}}\Big]^{2}dx_{J} \displaystyle\leq(\ell!)^{3}\sum_{\sigma\in S_{\ell}}\int_{\mathcal{M}^{|J|}}\Big[\int_{\mathcal{M}^{|J^{\complement}|}}\Big(\prod_{b=1}^{\ell}\frac{1}{t}k_{t}(x_{0},x_{b})(f_{\sigma(b)}(x_{b})-f_{\sigma(b)}(x_{0}))^{2}\Big)\,dx_{J^{\complement}}\Big]^{2}dx_{J} \displaystyle\leq C(\ell!)^{3}\sum_{\sigma\in S_{\ell}}\int_{\mathcal{M}^{|J|+1}}\Big[\int_{\mathcal{M}^{|J^{\complement}|-1}}\prod_{\begin{subarray}{c}b=1\\ b\neq a\end{subarray}}^{\ell}\frac{1}{t}k_{t}(x_{0},x_{b})(f_{\sigma(b)}(x_{b})-f_{\sigma(b)}(x_{0}))^{2}\,dx_{J^{\complement}\setminus\{0\}}\Big]^{2} \displaystyle\qquad\qquad\qquad\qquad\quad\cdot\frac{1}{t}k_{t}(x_{0},x_{a})(f_{\sigma(a)}(x_{a})-f_{\sigma(a)}(x_{0}))^{2}dx_{0}dx_{J}, where we applied the Cauchy-Schwarz inequality and Lemma 8 in the last inequality. Now, we can proceed as in the first case. ∎ Corollary 1 . Suppose that the assumptions of Proposition 2 are satisfied. Then, for each j=0,\dots,\ell , \displaystyle\|h_{t}^{(j)}\|_{L^{\infty}} \displaystyle\leq C\frac{1}{t^{dj/2}}, \displaystyle\|h_{t}^{(j)}\|_{L^{2}} \displaystyle\leq C\frac{1}{t^{dj/4}}. Proof. By construction, we have \displaystyle h_{t}^{(j)} \displaystyle=(\delta_{x_{0}}-P)\times\dots\times(\delta_{x_{j}}-P)\times P^{\ell-j}h_{t}=\sum_{J\subseteq\{0,\dots,j\}}(-1)^{j+1-|J|}\prod_{b\in J}\delta_{x_{b}}\times P^{\ell+1-|J|}h_{t} \displaystyle=\sum_{J\subseteq\{0,\dots,j\}}\frac{(-1)^{j+1-|J|}}{\ell+1}\sum_{a=0}^{\ell}\int_{\mathcal{M}^{|J^{\complement}|}}\Big(\frac{1}{t^{\ell}}\prod_{\begin{subarray}{c}b=0\\ b\neq a\end{subarray}}^{\ell}k_{t}(x_{a},x_{b})\Big)D^{2}(f_{1},\dots,f_{\ell},x_{0},\dots,x_{\ell})dx_{J^{\complement}}. The first claim follows from Lemma 9 , taking into account that J=\{0,\dots,j\} provides the bound Ct^{-dj/2} with the highest exponent and thus the dominating part because t\in(0,1] , and each summand with a>0 can be reduced to a=0 by relabeling the variables and using the alternating property of D . The second claim follows similarly from Minkowski’s inequality and the second claim in Lemma 9 . ∎ Proof of Proposition 2 . Using ( 18 ) and Corollary 1 , the concentration behavior of ( 17 ) can be analyzed using the standard machinery for U-statistics. We follow the strategy of [ 41 ] . Let \epsilon_{1},\dots,\epsilon_{n} be independent Rademacher random variables independent of X_{1},\dots,X_{n} . Then, by symmetrization (see [ 47 ] or [ 16 , Theorem 3.1] for a result with slightly worse constants) and the Bonami inequality ( [ 16 , Theorem 3.22] ), we have for j=0,\dots,\ell , \displaystyle\mathbb{E}^{1/p}\Big|\frac{1}{\binom{n}{j+1}^{1/2}}\sum_{1\leq i_{0}<\dotsu\Big) \displaystyle\leq\frac{1}{u^{p}}\mathbb{E}\Big|U_{n}(\ell,t)-\int_{\mathcal{M}^{\ell+1}}\Big(\det_{\ell\times\ell}(f_{a}(x_{b})-f_{a}(x_{0}))\Big)^{2}\Big(\frac{1}{t^{\ell}}\prod_{b=1}^{\ell}k_{t}(x_{0},x_{b})dx_{b}\Big)dx_{0}\Big|^{p} the claim follows from the choices p=\log n and \displaystyle u=e^{A}C\sum_{j=0}^{\ell}\Big(\frac{p^{\frac{j+1}{2}}}{t^{\frac{dj}{4}}n^{j+1}}+\frac{p^{\frac{j+2}{2}}}{t^{\frac{dj}{2}}n^{\frac{j+2}{2}}}\Big). ∎ End of the proof of Theorem 1 . Decomposing \langle\omega,\Delta_{\ell-1}^{\up}\omega\rangle-\langle\boldsymbol{\omega},\mathscr{L}_{\ell-1}^{\up}\boldsymbol{\omega}\rangle_{n} into the bias term \langle\omega,\Delta_{\ell-1}^{\up}\omega\rangle-\mathbb{E}\langle\boldsymbol{\omega},\mathscr{L}_{\ell-1}^{\up}\boldsymbol{\omega}\rangle_{n} and the variance term \mathbb{E}\langle\boldsymbol{\omega},\mathscr{L}_{\ell-1}^{\up}\boldsymbol{\omega}\rangle_{n}-\langle\boldsymbol{\omega},\mathscr{L}_{\ell-1}^{\up}\boldsymbol{\omega}\rangle_{n} , Theorem 1 follows from inserting Propositions 1 and 2 and the triangle inequality. ∎ 8 Experiments We compare the spectra of the empirical operators \mathscr{L}_{1}^{\up} and \mathscr{L}_{1}^{\down} with the corresponding population eigenvalues of \Delta_{1}^{\up} and \Delta_{1}^{\down} on the unit volume sphere r\cdot S^{2} with radius r=(4\pi)^{-1/2}. Population spectrum and heat kernel. The spectrum of \Delta_{1} for the unit sphere S^{2} is obtained in [ 21 , Theorems A-C] (see additionally [ 48 , Chapter 4] for the multiplicities). For each fixed r>0, the nonzero spectra of both \Delta_{1}^{\up} and \Delta_{1}^{\down} of r\cdot S^{2} are the same. In each case, for j\geq 1, the j -th positive eigenvalue is j(j+1)/r^{2} and has multiplicity 2j+1 and the spectrum of \Delta_{1} is the multiset union of the non-zero spectra of \Delta_{1}^{\up} and \Delta_{1}^{\down}. Table 1 below lists the corresponding first 4 eigenvalues of \Delta_{1}. We will denote by \lambda_{j}^{\up} and \lambda_{j}^{\down} the ascending positive eigenvalues, counted with multiplicities, of \Delta_{1}^{\up} and \Delta_{1}^{\down}, respectively. The heat kernel of r\cdot S^{2} admits a Mercer expansion in terms of spherical harmonics [ 55 , 1 ] . Rescaling and applying the addition theorem for spherical harmonics [ 39 ] , leads to \displaystyle k_{t}(x,y)=\sum_{j=0}^{\infty}\frac{2j+1}{4\pi r^{2}}e^{-\tfrac{j(j+1)t}{r^{2}}}P_{j}\Big(\frac{\langle x,y\rangle}{r^{2}}\Big),\qquad x,y\in r\cdot S^{2}, (24) where P_{j} is the j -th Legendre polynomial. Multiplicities Index Eigenvalue \Delta_{1}^{\down} \Delta_{1}^{\up} \Delta_{1} 1 2/r^{2} 3 3 6 2 6/r^{2} 5 5 10 3 12/r^{2} 7 7 14 4 20/r^{2} 9 9 18 Table 1 : First eigenvalues of \Delta_{1} on r\cdot S^{2}, broken down by contributions from \Delta_{1}^{\up} and \Delta_{1}^{\down}. Figure 1 : Weighted graph of V . Edge thickness is proportional to k_{ij}^{(\alpha)} . Eigenvalue problem. We sample X_{1},\dots,X_{n} as i.i.d. random variables uniformly distributed on r\cdot S^{2}. The spaces L^{2}_{\wedge}(V^{\ell+1}) are identified with \mathbb{R}^{d_{\ell}} of dimension d_{\ell}:={n\choose\ell+1} with the canonical basis indexed by ordered (\ell+1) -tuples of distinct elements of \{1,\dots,n\}. Let B_{1}\in\mathbb{R}^{d_{\ell+1}\times d_{\ell}} denote the matrix representation of \delta_{1} in these bases, where the (t,e) -entry of B_{1} is zero if the edge corresponding to e is not included in the triangle corresponding to \tau and equals to the sign induced by ( 4 ) otherwise (see also [ 37 , 44 , 53 ] for more details). The weighted inner products on L^{2}_{\wedge}(V^{2}) and L^{2}_{\wedge}(V^{3}) are represented by diagonal matrices W_{1} and W_{2}, respectively. Since the operator \delta_{1}^{*} is the adjoint of \delta_{1}, it has the matrix representation W_{1}^{-1}B_{1}^{\top}W_{2} . Consequently, \mathscr{L}_{1}^{\up}=\delta_{1}^{*}\delta_{1} has the matrix representation W_{1}^{-1}B_{1}^{\top}W_{2}B_{1} . Taking the weighted inner product into account, we aim at obtaining the eigenvalues of W_{1}^{-1/2}B_{1}^{\top}W_{2}B_{1}W_{1}^{-1/2}, which can be obtained by solving the generalized eigenvalue problem \displaystyle B_{1}^{T}W_{2}B_{1}w=\lambda W_{1}w,\qquad(\lambda,w)\in\mathbb{R}\times\mathbb{R}^{d_{\ell}}. (25) To construct W_{1} and W_{2} , we approximate the true heat kernel by the 50 leading terms of ( 24 ), and the weights (k_{i_{0}\dots i_{\ell}}),\ \ell\geq 1 are obtained by plugging the result in ( 13 ). The order-zero weights (k_{i}) are set to 1. In the approximation of the spectrum of \mathscr{L}_{1}^{\up}, we additionally perform a dimensionality reduction step by using the thresholded weights \displaystyle k_{ij}^{(\alpha)}:=k_{ij}\mathds{1}(k_{ij}\geq t^{\alpha-1}/(4\pi)),\ \text{ and }k_{ijk}^{\alpha}:=k_{ijk}\mathds{1}(k_{ij}^{(\alpha)}k_{ik}^{(\alpha)}k_{jk}^{(\alpha)}>0), (26) with \alpha>2 . The resulting weighted graph is visualized in Figure 1 . Since now W_{1} and W_{2} have zero entries, we restrict \mathbb{R}^{d_{1}} and \mathbb{R}^{d_{2}} and the matrices W_{1},W_{2},B_{1} to their respective ranges. Finally, the positive spectrum of \mathscr{L}_{1}^{\down} is obtained from that of the weighted unnormalized graph Laplacian of Example 1 with non-thresholded weights. Numerical procedure and results. The experiments are implemented in Python. We use the function eigsh from scipy and obtain numerical approximations to the eigenvalues above. The up-Helmholtzian has a large kernel of dimension \dim\ker(B_{1}). We remove the numerical eigenvalues that correspond to this kernel by discarding the numerical approximations smaller than 10^{-1}. The remaining numerical eigenvalues, sorted in ascending order, are denoted by \hat{\lambda}_{j}^{\up}(t),\ j\geq 1. The same procedure applied to the numerical eigenvalues of the graph Laplacian results in \hat{\lambda}_{j}^{\down}(t). We perform grid searches on the respective time parameters t_{u} and t_{d} of \hat{\lambda}_{j}^{\up} and \hat{\lambda}_{j}^{\down} and find approximate minimizers of \displaystyle\mathcal{E}^{\down}(t_{d})=\frac{1}{J}\sum_{j=1}^{J}\frac{|\lambda_{j}^{\down}-\hat{\lambda}_{j}^{\down}(t_{d})|}{\lambda_{j}^{\down}},\qquad\mathcal{E}^{\up}(t_{u})=\frac{1}{J}\sum_{j=1}^{J}\frac{|\lambda^{\up}_{j}-\hat{\lambda}_{j}^{\up}(t_{u})|}{\lambda^{\up}_{j}}, with J=8. Denote by \hat{t}_{d} and \hat{t}_{u} the resulting approximate minimizers. We set n=700, and \alpha=2.1. We set scipy ’s eigsh to compute k = 450 numerical eigenvalues, with which = 'SA' and tol = 1e-1 . t^{\up} varies along 20 regularly spaced values in [0.4n^{-2/3},1.2n^{-2/3}] and t^{\down} along 20 regularly spaced values in [0.1n^{-2/3},0.4n^{-2/3}]. The experiment is repeated with 10 different realizations of X_{1},\dots,X_{n}. The results are comparable to those of [ 12 ] , where numerical simulations were run for the random-walk Laplacian on data from r\cdot S^{2} . For n=700, they obtain a minimal value of \mathcal{E}^{\down} close to 10^{-0.92}\approx 0.120. We find 0.121\pm 0.010, showing close agreement between the two sets of results. Figure 2 : Empirical and true eigenvalues of r\cdot S^{2}. Index i is associated with the violin plot of \hat{\lambda}_{i}. The top, middle, and bottom horizontal bars are, respectively, the maximum, mean, and minimum over the 10 realizations. Left: 15 smallest eigenvalues \hat{\lambda}_{j}^{\down}. Center: 15 smallest eigenvalues \hat{\lambda}_{j}^{\up}. Right: Bottom of the spectrum of \mathscr{L}_{1}, obtained as the multiset union of the spectra shown in the left and center panels. Figure 2 depicts the empirical distributions of each of the resulting eigenvalues. The empirical eigenvalues are clearly separated into clusters in all of the three plots. The gap between the first two clusters of empirical eigenvalues exceeds half of the corresponding population gap. We minimize \mathcal{E} on the first two clusters of eigenvalues. The green bands in Figure 2 show the ranges of the first eigenvalue levels of the approximation (1-e^{-\hat{t}_{d}\lambda_{k}})/\hat{t}_{d}.