# A kernel-based analysis of Laplacian Eigenmaps

Martin Wahl Universität Bielefeld, Germany. E-mail<EMAIL_ADDRESS>bielefeld.de
2010 Mathematics Subject Classification. 62H25, 60B20, 15A42, 47A55, 47D07,
35K08
Key words and phrases. empirical graph Laplacian, Laplace-Beltrami operator,
heat semigroup, heat kernel, principal components analysis, empirical
covariance operator, reproducing kernel Hilbert space, perturbation theory,
concentration inequalities.

###### Abstract

Given i.i.d. observations uniformly distributed on a closed manifold
$\operatorname{{\mathcal{M}}}\subseteq\operatorname{{\mathbb{R}}}^{p}$, we
study the spectral properties of the associated empirical graph Laplacian
based on a Gaussian kernel. Our main results are non-asymptotic error bounds,
showing that the eigenvalues and eigenspaces of the empirical graph Laplacian
are close to the eigenvalues and eigenspaces of the Laplace-Beltrami operator
of $\operatorname{{\mathcal{M}}}$. In our analysis, we connect the empirical
graph Laplacian to kernel principal component analysis, and consider the heat
kernel of $\operatorname{{\mathcal{M}}}$ as reproducing kernel feature map.
This leads to novel points of view and allows to leverage results for
empirical covariance operators in infinite dimensions.

###### Contents

  1. 1 Introduction
    1. 1.1 Motivation
    2. 1.2 Laplacian Eigenmaps and Diffusion Maps
    3. 1.3 Laplace-Beltrami operator, heat semigroup and heat kernel
    4. 1.4 Two main consequences
    5. 1.5 Previous and new proof map
  2. 2 Heat kernel principal component analysis
    1. 2.1 The heat kernel as reproducing kernel
    2. 2.2 Heat kernel PCA
    3. 2.3 Perturbation bounds for heat kernel PCA
  3. 3 The approximation error
    1. 3.1 Different graph Laplacians
    2. 3.2 Analysis of the approximation error
  4. 4 Additional proofs
    1. 4.1 Proof of Corollary 1
    2. 4.2 Proof of Corollary 2
  5. A Appendix
    1. A.1 Perturbation bounds
    2. A.2 Concentration inequalities
    3. A.3 Eigenvalue estimates

##  1 Introduction

###  1.1 Motivation

Laplacian Eigenmaps [3] and Diffusion Maps [15] are nonlinear dimensionality
reduction methods that use the eigenvalues and eigenvectors of (un)normalized
graph Laplacians. Both methods are applied when the data is sampled from a
low-dimensional manifold, embedded in a high-dimensional Euclidean space. From
a mathematical point of view, the fundamental problem is to understand these
so-called empirical graph Laplacians as spectral approximations of the
underlying Laplace-Beltrami operator.

Spectral convergence properties of graph Laplacians have been studied first by
[4], based on pointwise convergence results [5, 19] and perturbation theory
for linear operators on Banach spaces [45, 11]. Since then, different
approaches have been proposed in order to study the spectral properties of
graph Laplacians (see e.g. [9, 40, 18, 10, 13] and the references therein).
Besides pointwise convergence results, an important role is played by
Dirichlet form convergence of the empirical graph Laplacian towards the
Laplace-Beltrami operator.

A different line of research studies principal component analysis (PCA) in
high dimensions [48, 29] or in infinite dimensions [23, 39], where the latter
also includes functional and kernel PCA. Principal component analysis is a
standard dimensionality reduction method that uses the eigenvalues and
eigenspaces of the empirical covariance matrix or operator to find the so-
called principal components, capturing most of the variance of the (empirical)
distribution. Recently, there has been a lot of interest and activity in the
(spectral) analysis of empirical covariance operators in infinite dimensions
(see, e.g., [42, 33, 32, 35, 28, 1] and the references therein). A related
problem studies approximations of integral operators [31, 37].

In this paper, we study empirical graph Laplacians through the lens of kernel
PCA. In particular, we connect the eigenvalue and eigenvector problem for the
empirical graph Laplacian to a kernel PCA problem, providing a novel
functional analytic framework. To achieve this, the semigroup framework plays
an important role. First, we interpret the Laplace-Beltrami operator of
$\operatorname{{\mathcal{M}}}$ as the generator of the heat semigroup of
$\operatorname{{\mathcal{M}}}$ [16, 21]. Second, the heat semigroup is an
integral operator on the space of all square-integrable functions on
$\operatorname{{\mathcal{M}}}$, with integral kernel being the heat kernel of
$\operatorname{{\mathcal{M}}}$. Restricting its domain to the reproducing
kernel Hilbert space (RKHS) induced by the heat kernel, the heat semigroup can
be interpreted as the covariance operator of the random variable obtained by
embedding the original observation on the manifold using the heat kernel as
reproducing kernel feature map. This leads to novel points of view and allows
us to use results for empirical covariance operators in infinite dimensions.
In particular, this paves the way to apply Hilbert space perturbation theory
in the analysis of empirical graph Laplacians.

###  1.2 Laplacian Eigenmaps and Diffusion Maps

In this section, we introduce the Laplacian Eigenmaps and the Diffusion Maps
algorithm. Let $X_{1},\dots,X_{n}$ be data points in
$\operatorname{{\mathbb{R}}}^{p}$. Let $\langle\cdot,\cdot\rangle$ be the
standard inner product in $\operatorname{{\mathbb{R}}}^{p}$ and let
$\|\cdot\|_{2}$ be the corresponding Euclidean norm in
$\operatorname{{\mathbb{R}}}^{p}$. Finally, let

$\displaystyle w_{t}(x,y)=\frac{1}{(4\pi
t)^{d/2}}\exp\Big{(}-\frac{\|x-y\|_{2}^{2}}{4t}\Big{)},\qquad
x,y\in\operatorname{{\mathbb{R}}}^{p},$ (1.1)

be the Gaussian kernel with hyperparameters $d\in\operatorname{{\mathbb{N}}}$
and $t>0$. Then the (unnormalized) empirical graph Laplacian or point cloud
Laplacian with repsect to $w_{t}$ is given by (see, e.g., [44])

$\displaystyle\mathscr{L}_{w_{t}}=\frac{1}{t}(D_{w_{t}}-W_{t})\in\operatorname{{\mathbb{R}}}^{n\times
n}$

with adjacency matrix $W_{t}\in\operatorname{{\mathbb{R}}}^{n\times n}$
defined by

$\displaystyle(W_{t})_{ij}=\frac{1}{n}w_{t}(X_{i},X_{j})$

and degree matrix $D_{w_{t}}\in\operatorname{{\mathbb{R}}}^{n\times n}$ being
a diagonal matrix with

$\displaystyle(D_{w_{t}})_{ii}=\frac{1}{n}\sum_{j=1}^{n}w_{t}(X_{i},X_{j}).$

Graph Laplacians have been intensively studied in spectral graph theory (see,
e.g., [14] or [44] and the references therein). A first key identity of the
unnormalized graph Laplacian is

$\displaystyle\langle
u,\mathscr{L}_{w_{t}}u\rangle=\frac{1}{2n}\sum_{i=1}^{n}\sum_{j=1}^{n}w_{t}(X_{i},X_{j})(u_{i}-u_{j})^{2},\qquad
u\in\operatorname{{\mathbb{R}}}^{n},$ (1.2)

which can be seen as an empirical Dirichlet form (see, e.g., Proposition 1 in
[44]). In particular, $\mathscr{L}_{w_{t}}$ is symmetric and positive semi-
definite. Let

$\displaystyle
0\leq\lambda_{1}(\mathscr{L}_{w_{t}})\leq\dots\leq\lambda_{n}(\mathscr{L}_{w_{t}})$

be the eigenvalues of $\mathscr{L}_{w_{t}}$ (in non-decreasing order), and let

$\displaystyle
u_{1}(\mathscr{L}_{w_{t}}),\dots,u_{n}(\mathscr{L}_{w_{t}})\in\operatorname{{\mathbb{R}}}^{n}$

be an orthonormal basis of corresponding eigenvectors. Since $w_{t}(x,y)>0$
for all $x,y\in\operatorname{{\mathbb{R}}}^{n}$, it follows from Proposition 2
in [44] that
$0=\lambda_{1}(\mathscr{L}_{w_{t}})<\lambda_{2}(\mathscr{L}_{w_{t}})$ and that
$u_{1}(\mathscr{L}_{w_{t}})=n^{-1/2}(1,\dots,1)^{\top}$. The spectral
characteristics of $\mathscr{L}_{w_{t}}$ are often used in spectral
clustering. Indeed, given a natural number $1\leq j\leq n$, a reduced
coordinate system is given by

$\displaystyle\varphi^{(j)}(X_{i})=\begin{pmatrix}u_{1i}(\mathscr{L}_{w_{t}})\\\
\vdots\\\
u_{ji}(\mathscr{L}_{w_{t}})\end{pmatrix}\in\operatorname{{\mathbb{R}}}^{j},\qquad
1\leq i\leq n,$ (1.3)

where $u_{ki}(\mathscr{L}_{w_{t}})$ is the $i$th coordinate of the $k$th
eigenvector. Often, one also introduces a weighting by multiplying the entries
$u_{ki}(\mathscr{L}_{w_{t}})$ by $\lambda_{k}(\mathscr{L}_{w_{t}})^{m}$ with
$m>0$. Moreover, often $\mathscr{L}_{w_{t}}$ is replaced by the random walk
graph Laplacian $I_{n}-D_{w_{t}}^{-1}\mathscr{L}_{w_{t}}$, where
$I_{n}\in\operatorname{{\mathbb{R}}}^{n\times n}$ is the identity matrix, in
which case (1.3) is also called (truncated) diffusion map and
$\|\varphi^{(j)}(X_{i_{1}})-\varphi^{(j)}(X_{i_{2}})\|_{2}$ is also called
diffusion distance between data points $X_{i_{1}}$ and $X_{i_{2}}$ (see, e.g.,
[15] and [2]).

###  1.3 Laplace-Beltrami operator, heat semigroup and heat kernel

Let $\mathcal{M}$ be a submanifold of $\operatorname{{\mathbb{R}}}^{p}$ of
dimension $d$, equipped with the Riemannian metric induced by the ambient
space. We assume that $\mathcal{M}$ is closed (that is, compact and without
boundary) and that the volume of $\mathcal{M}$ is $1$. Let

$\displaystyle H=-\Delta|_{W^{2}(\mathcal{M})}$ (1.4)

be the Laplace-Beltrami operator of $\mathcal{M}$ (see Section 3.7 in [21],
Chapter 5 in [16], or [38]), which we consider with domain being the Sobolev
spaces $W^{2}(\mathcal{M})$. The sign convention implies that $H$ is a
positive self-adjoint operator. Let

$\displaystyle(e^{-tH})_{t>0}$ (1.5)

be the heat semigroup on $L^{2}(\mathcal{M})$ associated with $H$ (see, e.g.,
Theorem 4.9 in [21] or Chapter 5 in [16]). For each $t>0$, $e^{-tH}$ is a a
positive self-adjoint bounded operator on $L^{2}(\mathcal{M})$. Moreover,
since $\mathcal{M}$ is closed, $e^{-tH}$ is ultracontractive (see, e.g.,
Theorem 7.6 in [21]), implying the existence of an integral kernel $k_{t}$
satisfying

$\displaystyle e^{-tH}f(x)=\int_{\mathcal{M}}k_{t}(x,y)f(y)dy$

for all $x\in\mathcal{M}$, all $t>0$ and all $f\in L^{2}(\mathcal{M})$, where
$dy$ denotes the volume measure on $\mathcal{M}$ (see, e.g., Theorem 5.2.1 in
[16] or Theorem 7.13 in [21]). The kernel $k_{t}$ is called heat kernel of
$\operatorname{{\mathcal{M}}}$. It is symmetric, bounded, non-negative (in
fact, we have $k_{t}(x,y)>0$ whenever $x$ and $y$ belong to the same connected
component of $\mathcal{M}$ and $k_{t}(x,y)=0$ otherwise), and satisfies
$\int_{\operatorname{{\mathcal{M}}}}k_{t}(x,y)\,dy=1$ for all
$x\in\operatorname{{\mathcal{M}}}$. In particular, $e^{-tH}$ is additionally
trace-class for every $t>0$, implying that there exists an orthonormal basis
$\phi_{1},\phi_{2},\dots$ of $L^{2}(\mathcal{M})$ and an non-decreasing
sequence $0=\mu_{1}\leq\mu_{2}\leq\dots\rightarrow\infty$ of non-negative real
numbers such that (see, e.g., Lemma 7.2.1 in [16] or Theorem 10.13 in [21])

$\displaystyle
e^{-tH}\phi_{j}=\phi_{j},\qquad\sum_{j=1}^{\infty}e^{-\mu_{j}t}<\infty.$ (1.6)

For each $j\in\operatorname{{\mathbb{N}}}$, $\phi_{j}$ is in the domain of
$H$, implying that

$\displaystyle H\phi_{j}=\lim_{t\rightarrow
0}\frac{I-e^{-tH}}{t}\phi_{j}=\mu_{j}\phi_{j},$

where $I$ denotes the identity map. Moreover, the heat kernel admits the
expansion

$\displaystyle
k_{t}(x,y)=\sum_{j=1}^{\infty}e^{-\mu_{j}t}\phi_{j}(x)\phi_{j}(y)$ (1.7)

for all $t>0$ and all $x,y\in\mathcal{M}$, which converges in
$L^{2}(\mathcal{M}\times\mathcal{M})$ as well as absolutely and uniformly in
$[a,b]\times\mathcal{M}\times\mathcal{M}$ for all real numbers $b>a>0$. The
multiplicity of the eigenvalue $0$ is denoted by $m$, meaning that

$\displaystyle 0=\mu_{1}=\dots=\mu_{m}<\mu_{m+1}.$

The number $m$ corresponds to the number of connected components of
$\mathcal{M}$. Moreover, if $\mathcal{M}_{1},\dots,\mathcal{M}_{m}$ are the
connected components of $\mathcal{M}$, then we can choose
$\phi_{j}=\operatorname{vol}(\mathcal{M}_{j})^{-1/2}\mathbf{1}_{\mathcal{M}_{j}}$
as the first $m$ eigenfunctions of $H$ (see, e.g., Section 2.2 in [22]).

###  1.4 Two main consequences

The main goal of this paper is to study the behavior of the eigenvalues and
eigenvectors of $\mathscr{L}_{w_{t}}$ under the following manifold assumption.

######  Assumption 1.

Let $X,X_{1},\dots,X_{n}$ be i.i.d. random variables that are uniformly
distributed on $\mathcal{M}$, where $\mathcal{M}$ is a closed submanifold of
$\operatorname{{\mathbb{R}}}^{p}$ with $\dim\operatorname{{\mathcal{M}}}=d$
and $\operatorname{vol}(M)=1$ such that conditions (C1), (C3), (C4) and (C5)
from below hold.

In this section, we formulate two main consequences of the analysis presented
in Sections 2 and 3. We say that an event holds with high probability, if it
holds with probability at least $1-Cn^{-c}$, where $c,C>0$ are constants
depending only on the manifold constants from (C1), (C3), (C4) and (C5). The
following result deals with eigenvalues.

######  Corollary 1.

Grant Assumption 1. Then there are constants $c,C>0$ depending only on the
constants in (C1), (C3), (C4) and (C5) such that the following holds. Let
$n\geq 2$ and let $t\in(0,1]$ be such that $\frac{\log n}{nt^{d/2}}\leq c$.
Then

$\displaystyle\forall 1\leq j\leq
n,\quad|\lambda_{j}(\mathscr{L}_{w_{t}})-\mu_{j}|\leq C\Big{(}\sqrt{\frac{\log
n}{nt^{d/2+2}}}+\mu_{j}t\log^{2}(\tfrac{e}{t})+(\mu_{j}^{2}\vee 1)t\Big{)}.$

with high probability.

For all $j\in\operatorname{{\mathbb{N}}}$ let

$S_{n}\phi_{j}=\frac{1}{\sqrt{n}}(\phi_{j}(X_{1}),\dots,\phi_{j}(X_{n}))^{\top}\in\operatorname{{\mathbb{R}}}^{n}$

and let $O(j)$ be the set of all orthogonal $j\times j$ matrices. The next
result deals with eigenspaces and provides an error bound for the reduced
coordinate system in (1.3).

######  Corollary 2.

Grant Assumption 1. Then there are constants $c,C>0$ depending only on the
constants in (C1), (C3), (C4) and (C5) such that the following holds. Let
$n\geq 2$, $1\leq j\leq n$ and $t\in(0,1]$ be such that $\mu_{j+1}>\mu_{j}$,
$\mu_{j+1}t\leq 1$ and $\frac{\log n}{nt^{d/2}}\leq c$. Then

$\displaystyle\inf_{O\in O(j)}$
$\displaystyle\|(S_{n}\phi_{1},\dots,S_{n}\phi_{j})-(u_{1}(\mathscr{L}_{w_{t}}),\dots,u_{j}(\mathscr{L}_{w_{t}}))O\|_{2}$
$\displaystyle\leq C\sqrt{j}\Big{(}\frac{1}{\mu_{j+1}-\mu_{j}}\sqrt{\frac{\log
n}{nt^{d/2+2}}}+\frac{\mu_{j+1}}{\mu_{j+1}-\mu_{j}}t\log^{2}(\tfrac{e}{t})+\mu_{j}t\Big{)}.$

with high probability. Here, $\|\cdot\|_{2}$ denotes the Hilbert-Schmidt norm.

The proofs of Corollaries 1 and 2 are based on classical (zero order)
perturbation bounds (i.e. the Weyl bound and the Davis-Kahan bound). On the
one hand, this leads to non-asymptotic perturbation bounds that are valid
under minimal assumptions and exhibit simple dependencies on the involved
quantities ($d$, $j$, $\mu_{j}$, spectral gap, etc). For instance, Corollary 1
holds without any spectral gap assumption. On the other hand, this leads to a
stochastic error (i.e. the term involving $n^{-1/2}t^{-d/4-1}$ up to a
logarithmic term) that is suboptimal with respect to $t$.

Compared to recent results in the literature, our dependence on $t$ is better
than e.g. in the bounds obtained in [18], but it is worse than in the bounds
obtained in [13]. The latter provides a first order perturbation analysis, and
establishes the stochastic errors (up to logarithmic terms) of the asymptotic
order $n^{-1/2}t^{-d/4}$ and $n^{-1/2}t^{-d/4-1/2}$ for the eigenvalues and
eigenfunctions, respectively. However, this requires stronger assumptions, and
in [13] only a fixed number of leading eigenvalues (and eigenfunctions) are
considered under the (spectral gap) assumption that they all have multiplicity
$1$.

In a companion paper we will combine our approach (outlined in Section 1.5)
with higher order perturbation expansions obtained in [35, 28, 27]. We
conjecture that this will lead to an improved stochastic error term of the
order $n^{-1/2}t^{-d/4}$ for both eigenvalues and eigenspaces (with an even
better rate in the case of eigenvalues), but also leads to more restrictive
assumptions on $d$, $j$, $\mu_{j}$, spectral gap, etc. In this paper, we
formulate such an improvement only for heat kernel PCA and for the leading
eigenvalue and the associated eigenspace (related to spectral clustering, see
Theorem 3 below). This already requires more advanced techniques in the form
of concentration inequalities (Lemmas 5 and 16), perturbation bounds (Lemmas 9
and 10), and eigenvalues computations (Lemma 17). Note that all these
techniques are not used in the proofs of Corollaries 1 and 2.

###  1.5 Previous and new proof map

A standard route in the analysis of the point cloud Laplacian under the
manifold assumption (see, e.g., [4, 19, 41, 18, 13]) is described by the
following error decomposition

Here, (1) corresponds to an approximation error and (2) corresponds to a
stochastic error. In the approximation error, the heat kernel $k_{t}$ is
replaced by a Gaussian kernel $w_{t}$, leading to the operator

$\displaystyle\mathbb{E}\mathscr{L}_{w_{t}}f(x)=\frac{1}{t}\int_{\mathcal{M}}(f(x)-f(y))w_{t}(x,y)dy,\qquad
f\in L^{2}(\mathcal{M}),x\in\mathcal{M}.$

The approximation error tends to decrease when $t$ decreases. It cannot be
controlled uniformly over $L^{2}(\mathcal{M})$, but only over proper classes
of smooth functions (see, e.g., Theorem 3.1 in [19], Theorem 5.1 in [13] and
[41] for pointwise error bounds and Theorem 3.2 in [13] and Section 3 in [18]
for Dirichlet form error bounds). In the stochastic error, the uniform
distribution on $\operatorname{{\mathcal{M}}}$ is replaced by by the empirical
distribution, leading to

$\displaystyle\mathscr{L}_{w_{t}}f(x)=\frac{1}{t}\frac{1}{n}\sum_{i=1}^{n}(f(x)-f(X_{i}))w_{t}(x,X_{i}),\qquad
f\in\mathcal{C}(\mathcal{M}),x\in\mathcal{M},$

where $\mathcal{C}(\mathcal{M})$ denotes the space of all continuous functions
on $\mathcal{M}$. The stochastic error tends to increase when $n$ increases.
Again, for certain proper classes of functions, it can be controlled using
concentration inequalities and empirical process theory (see, e.g., [19] and
[4]).

The approach of this paper reverses the order of approximation error and
stochastic error and is described by the following error decomposition

Here, (1) corresponds to a stochastic error, (2) corresponds to the kernel
trick, (3) is another stochastic error and (4) is an approximation error. The
first main step will be to realize $e^{-tH}$ as the covariance operator
$\Sigma_{t}$ of the embedded data point $k_{t}(X,\cdot)$ taking values in the
reproducing kernel Hilbert space (RKHS) $\mathcal{H}_{t}$ induced by $k_{t}$
(Section 2.2). The new stochastic error consists now in estimating
$\Sigma_{t}$ using the empirical covariance operator $\hat{\Sigma}_{t}$ on
$\operatorname{{\mathcal{H}}}$ based on the embedded data points
$k_{t}(X_{i},\cdot)\in\operatorname{{\mathcal{H}}}_{t}$, $1\leq i\leq n$. This
error can be controlled in operator norm (which makes it easy to apply
perturbation bounds for eigenvalues and eigenspaces) using concentration
inequalities for random self-adjoint operators (Section 2.3). Together with
the kernel trick in (2), this allows to relate the spectral characteristics of
$\frac{I-e^{-tH}}{t}$ to those of $\frac{I_{n}-K_{t}}{t}$, where
$K_{t}\in\operatorname{{\mathbb{R}}}^{n\times n}$ is the kernel matrix defined
by $(K_{t})_{ij}=n^{-1}k_{t}(X_{i},X_{j})$. Finally, the stochastic error in
(3) and the approximation error in (4) can again be controlled in operator
norm, using concentration inequalities and asymptotic expansions of the heat
kernel (Section 3.2).

##### Further basic notation.

Given a bounded (resp. Hilbert-Schmidt) operator $A$ on a Hilbert space
$\mathcal{H}$, we denote the operator norm (resp. the Hilbert-Schmidt norm) of
$A$ by $\|A\|_{\infty}$ (resp. $\|A\|_{2}$). Given a trace class operator $A$
on $\mathcal{H}$, we denote the trace of $A$ by $\operatorname{tr}(A)$. For
$g,h\in\mathcal{H}$, we denote by $g\otimes h$ the rank-one operator on
$\mathcal{H}$ defined by $(g\otimes h)x=\langle h,x\rangle g$,
$x\in\mathcal{H}$. Throughout the paper, $c\in(0,1)$ and $C>1$ denote
constants that may change from line to line (by a numerical value). If no
further dependencies are mentioned, then these constants are absolute.

##  2 Heat kernel principal component analysis

Throughout Section 2, we suppose that Assumption 1 is satisfied.

###  2.1 The heat kernel as reproducing kernel

The representation in (1.7) implies that $k_{t}$ is a symmetric and positive
semi-definite kernel function in the sense of Definition 12.6 in [48]. Hence,
$k_{t}$ induces the reproducing kernel Hilbert space (RKHS) (see, e.g.,
Corollary 12.26 in [48])

$\displaystyle\operatorname{{\mathcal{H}}}_{t}=\Big{\\{}f=\sum_{j=1}^{\infty}\alpha_{j}\phi_{j}\
:\ \sum_{j=1}^{\infty}\alpha_{j}^{2}<\infty\text{ and
}\sum_{j=1}^{\infty}e^{\mu_{j}t}\alpha_{j}^{2}<\infty\Big{\\}}$

with the inner product

$\displaystyle\langle
f,g\rangle_{\operatorname{{\mathcal{H}}}_{t}}=\sum_{j=1}^{\infty}e^{\mu_{j}t}\alpha_{j}\beta_{j},\qquad
f=\sum_{j=1}^{\infty}\alpha_{j}\phi_{j},g=\sum_{j=1}^{\infty}\beta_{j}\phi_{j}\in\operatorname{{\mathcal{H}}}_{t}.$

In particular, an orthonormal basis of $\operatorname{{\mathcal{H}}}_{t}$ is
given by

$u_{t,j}=e^{-\mu_{j}t/2}\phi_{j},\qquad j\in\operatorname{{\mathbb{N}}}.$

Alternatively, we have

$\displaystyle\operatorname{{\mathcal{H}}}_{t}=e^{-(t/2)H}L^{2}(\operatorname{{\mathcal{M}}})$

with

$\displaystyle\langle f,g\rangle_{\operatorname{{\mathcal{H}}}_{t}}=\langle
e^{(t/2)H}f,e^{(t/2)H}g\rangle_{L^{2}(\operatorname{{\mathcal{M}}})}$

for $f,g\in\operatorname{{\mathcal{H}}}_{t}$. In particular, for all $t>0$ and
all $x\in\operatorname{{\mathcal{M}}}$, we have

$\displaystyle k_{t}(x,\cdot)\in\operatorname{{\mathcal{H}}}_{t}$

and the reproducing property

$\displaystyle f(x)=\langle
f,k_{t}(x,\cdot)\rangle_{\operatorname{{\mathcal{H}}}_{t}}$

holds. Setting $f=k_{t}(y,\cdot)$, we get

$\displaystyle k_{t}(x,y)=\langle
k_{t}(y,\cdot),k_{t}(x,\cdot)\rangle_{\operatorname{{\mathcal{H}}}_{t}}$ (2.1)

for all $t>0$ and all $x,y\in\operatorname{{\mathcal{H}}}_{t}$. Hence,
geometric computations for the functions $k_{t}(x,\cdot)$,
$x\in\operatorname{{\mathcal{M}}}$ in the infinite-dimensional Hilbert space
$\operatorname{{\mathcal{H}}}_{t}$ can be carried out using only evaluations
of the kernel function.

###  2.2 Heat kernel PCA

Since $k_{t}$ is a positive semi-definite kernel function with RKHS
$\operatorname{{\mathcal{H}}}_{t}$, we can consider the reproducing kernel
feature map (see, e.g., [39, 42])

$\displaystyle\Phi_{t}:\operatorname{{\mathcal{M}}}\rightarrow\operatorname{{\mathcal{H}}}_{t},\
x\mapsto k_{t}(x,\cdot).$

This map is similar to the (population) diffusion map (see, e.g., [15]) with
the difference that the range is $\operatorname{{\mathcal{H}}}_{t}$ instead of
the larger space $L^{2}(\operatorname{{\mathcal{M}}})$. This feature map
yields the embedded random variables

$\displaystyle k_{t}(X,\cdot),k_{t}(X_{1},\cdot),\dots,k_{t}(X_{n},\cdot),$

taking values in the Hilbert space $\operatorname{{\mathcal{H}}}_{t}$. The
random variable $k_{t}(X,\cdot)$ has expectation
$\mathbf{1}_{\operatorname{{\mathcal{M}}}}:\operatorname{{\mathcal{M}}}\rightarrow\operatorname{{\mathbb{R}}},\
x\mapsto 1$. Moreover, by (1.7), it has the Karhunen-Loève (KL) representation

$\displaystyle
k_{t}(X,\cdot)=\sum_{j=1}^{\infty}e^{-\mu_{j}t/2}\phi_{j}(X)u_{t,j}$ (2.2)

with KL coefficients $\phi_{j}(X)$ satisfying
$\operatorname{{\mathbb{E}}}\phi_{j}(X)\phi_{k}(X)=0$ for all $j\neq k$ and
$\operatorname{{\mathbb{E}}}\phi_{j}^{2}(X)=1$ for all
$j\in\operatorname{{\mathbb{N}}}$. By (2.2), we have

$\displaystyle\operatorname{{\mathbb{E}}}\|k_{t}(X,\cdot)\|_{\operatorname{{\mathcal{H}}}_{t}}^{2}=\sum_{j=1}^{\infty}e^{-\mu_{j}t}<\infty,$

meaning that $k_{t}(X,\cdot)$ is strongly square-integrable. Hence we can
define the (unnormalized) covariance operator

$\displaystyle\Sigma_{t}=\operatorname{{\mathbb{E}}}k_{t}(X,\cdot)\otimes
k_{t}(X,\cdot),$

which is a positive self-adjoint trace class operator on
$\operatorname{{\mathcal{H}}}_{t}$ (see, e.g., Theorem 7.2.5 in [23] or [27]).
The following lemma collects some basic properties of $k_{t}(X,\cdot)$.

######  Lemma 1.

The random variable $k_{t}(X,\cdot)$ is strongly square-integrable with
ovariance operator
$\Sigma_{t}=\operatorname{{\mathbb{E}}}k_{t}(X,\cdot)\otimes k_{t}(X,\cdot)$
satisfying

$\displaystyle\Sigma_{t}=\sum_{j=1}^{\infty}e^{-\mu_{j}t}u_{t,j}\otimes
u_{t,j}=e^{-tH}|_{\operatorname{{\mathcal{H}}}_{t}}.$

In particular, $\Sigma_{t}$ is a trace-class operator with

$\displaystyle\operatorname{tr}(\Sigma_{t})=\sum_{j=1}^{\infty}e^{-\mu_{j}t}.$

###### Proof.

The spectral respresentation of $\Sigma_{t}$ is a consequence of (2.2). For
the second equality it suffices to note that
$\Sigma_{t}u_{t,j}=e^{-\mu_{j}t}u_{t,j}=e^{-tH}u_{t,j}$ for all
$j\in\operatorname{{\mathbb{N}}}$. ∎

Lemma 1 shows that the spectral characteristics of the heat semigroup can be
inferred from the covariance operator of $k_{t}(X,\cdot)$. In particular, the
eigenvalues of $\Sigma_{t}$ are given by $e^{-\mu_{1}t}\geq
e^{-\mu_{2}t}\geq\dots>0$ (we also often write $\lambda_{t,j}=e^{-\mu_{j}t}$)
and corresponding eigenvectors are given by $u_{t,1},u_{t,2},\dots$. For
$j\in\operatorname{{\mathbb{N}}}$, let

$\displaystyle P_{t,\leq j}=\sum_{k=1}^{j}P_{t,k},\qquad
P_{t,k}=u_{t,k}\otimes u_{t,k}$

be the orthogonal projection onto the eigenspace spanned by
$u_{t,1},\dots,u_{t,j}$.

Let

$\displaystyle\hat{\Sigma}_{t}=\frac{1}{n}\sum_{i=1}^{n}k_{t}(X_{i},\cdot)\otimes
k_{t}(X_{i},\cdot)$

be the empirical covariance operator, which is a positive self-adjoint finite-
rank operator on $\operatorname{{\mathcal{H}}}_{t}$. In particular, there
exists a sequence $\hat{\lambda}_{t,1}\geq\hat{\lambda}_{t,2}\geq\cdots\geq 0$
of non-negative eigenvalues together with an orthonormal basis of eigenvectors
$\hat{u}_{t,1},\hat{u}_{t,2},\dots$ in $\operatorname{{\mathcal{H}}}_{t}$ such
that

$\displaystyle\hat{\Sigma}_{t}=\sum_{k=1}^{\infty}\hat{\lambda}_{t,k}\hat{u}_{t,k}\otimes\hat{u}_{t,k}.$

For $j\in\operatorname{{\mathbb{N}}}$, let

$\displaystyle\hat{P}_{t,\leq
j}=\sum_{k=1}^{j}\hat{P}_{t,k},\qquad\hat{P}_{t,k}=\hat{u}_{t,k}\otimes\hat{u}_{t,k}$

be the orthogonal projection onto the eigenspace spanned by
$\hat{u}_{t,1},\dots,\hat{u}_{t,j}$.

A related matrix is the kernel matrix
$K_{t}\in\operatorname{{\mathbb{R}}}^{n\times n}$ defined by

$\displaystyle(K_{t})_{ij}=\frac{1}{n}\langle
k_{t}(X_{i},\cdot),k_{t}(X_{j},\cdot)\rangle_{\operatorname{{\mathcal{H}}}_{t}}=\frac{1}{n}k_{t}(X_{i},X_{j}).$

The so-called kernel trick states that $\hat{\Sigma}_{t}$ and $K_{t}$ have the
same non-zero eigenvalues and that the so called principal components (see,
e.g., [30]) can be computed from $K_{t}$. To formulate this, let

$\displaystyle
S_{n}:\operatorname{{\mathcal{H}}}_{t}\rightarrow\operatorname{{\mathbb{R}}}^{n},\
f\mapsto\frac{1}{\sqrt{n}}(f(X_{1}),\dots,f(X_{n}))^{\top}$

be the (normalized) sampling operator. Then there exists an orthonormal basis
$\hat{v}_{t,1},\dots,\hat{v}_{t,n}$ of $\operatorname{{\mathbb{R}}}^{n}$ such
that (see, e.g., [13])

$\displaystyle
K_{n}=\sum_{j=1}^{n}\hat{\lambda}_{t,j}\hat{v}_{t,j}\hat{v}_{t,j}^{\top}$

with principal components satisfying

$\displaystyle\hat{\lambda}_{t,j}^{1/2}\hat{v}_{t,j}=S_{n}\hat{u}_{t,j}\in\operatorname{{\mathbb{R}}}^{n}.$
(2.3)

The qualitative properties in Lemma 1 alone are not sufficient for a
statistical analysis of heat kernel PCA. For this we need some additional
quantitative properties of $k_{t}$. For better reference, we will formulate
these properties as conditions with explicit constants.

(C1)

There exists a constant $C_{1}>0$ such that

$\displaystyle k_{t}(x,x)\leq C_{1}t^{-d/2}$

for all $t\in(0,1]$ and all $x\in\operatorname{{\mathcal{M}}}$.

Condition (C1) is satisfied under Assumption 1, as follows from Theorem 7.9 in
[21]. It has many consequences. For instance, (1.7) and (C1) yield (after
integrating over $\operatorname{{\mathcal{M}}}$)

$\displaystyle je^{-\mu_{j}t}\leq\sum_{k=1}^{\infty}e^{-\mu_{k}t}\leq
C_{1}t^{-d/2}$

and setting $t=\mu_{j}^{-1}$ with $j>m$ leads to

$\displaystyle\mu_{j}\geq c_{1}j^{2/d}$ (2.4)

for all $j>m$, with a constant $c_{1}>0$ depending only on $C_{1}$ (see also
Example 10.16 in [21] and Remark 3 in [12]).

(C2)

There exists a constant $C_{2}>0$ such that

$\displaystyle\sum_{k=1}^{j}\phi_{k}^{2}(x)\leq C_{2}j$

for all $x\in\operatorname{{\mathcal{M}}}$ and all
$j\in\operatorname{{\mathbb{N}}}$.

Condition (C2) says that the orthonormal basis $\phi_{1},\phi_{2},\dots$ of
$L^{2}(\operatorname{{\mathcal{M}}})$ is bounded on average. It holds under
Assumption 1, as shown in [34]. It is again closely related to (C1) and an
upper bound for the eigenvalues. Indeed, by Weyl’s formula there exists a
constant $C>0$ such that $\mu_{j}\leq Cj^{2/d}$ for all
$j\in\operatorname{{\mathbb{N}}}$. Thus, (1.7) and (C1) yield for $t=j^{-2/d}$
that

$\displaystyle
e^{-C}\sum_{k=1}^{j}\phi_{k}^{2}(x)\leq\sum_{k=1}^{\infty}e^{-\mu_{k}t}\phi_{k}^{2}(x)\leq
C_{1}t^{-d/2}=C_{1}j.$

Finally, we state two simple consequences of (C1) and (C2).

######  Lemma 2.

If (C1) holds, then

$\displaystyle\|k_{t}(X,\cdot)\|_{\operatorname{{\mathcal{H}}}_{t}}^{2}\leq
C_{1}t^{-d/2}\qquad\text{a.s.},$

where $C_{1}$ is the constant in (C1).

###### Proof.

By (2.1) we have

$\displaystyle\|k_{t}(X,\cdot)\|_{\operatorname{{\mathcal{H}}}_{t}}^{2}=\langle
k_{t}(X,\cdot),k_{t}(X,\cdot)\rangle_{\operatorname{{\mathcal{H}}}_{t}}=k_{t}(X,X),$

Hence, the claim follows from inserting (C1). ∎

Hence under (C1), $k_{t}(X,\cdot)$ is a bounded random variable, which is
already sufficient to start the analysis of heat kernel PCA (see, e.g., [37,
7]). The next lemma shows that $k_{t}(X,\cdot)$ has a more subtle
probabilistic structure if additionally (C2) is fulfilled. This will allow us
to apply more refined concentration techniques.

######  Lemma 3.

If (C1) and (C2) hold, then $k_{t}(X,\cdot)$ has the KL representation

$\displaystyle
k_{t}(X,\cdot)=\sum_{j=1}^{\infty}e^{-\mu_{j}t/2}\phi_{j}(X)u_{t,j}$

such that for all $j>m$ it holds that

$\displaystyle\mu_{j}\geq
cj^{2/d}\qquad\text{and}\qquad\sum_{k=1}^{j}\phi_{k}^{2}(X)\leq Cj\quad\text{
almost surely.}$

###### Proof.

Follows from (2.2), (2.4) and (C2). ∎

###  2.3 Perturbation bounds for heat kernel PCA

In this section, we derive perturbation bounds for the eigenvalues
$\hat{\lambda}_{t,j}$ and the spectral projectors $\hat{P}_{t,\leq j}$ of the
empirical covariance operator $\hat{\Sigma}_{t}$, considered as spectral
approximations of the eigenvalues $\lambda_{t,j}=e^{-\mu_{j}t}$ and the
spectral projectors $P_{t,\leq j}$ of the covariance operator $\Sigma_{t}$. We
apply classical absolute perturbation bounds, based on the perturbation bounds
by Weyl and Davis-Kahan, and we will also show how to obtain more refined
bounds, by using relative perturbation bound from [35, 28, 27]. In the latter
case we restrict ourselves to the nullspace.

######  Lemma 4.

Suppose that (C1) is satisfied. Then, with probability at least
$1-Ct^{-d/2}e^{-y}$, $y>0$, we have

$\displaystyle\|\hat{\Sigma}_{t}-\Sigma_{t}\|_{\infty}\leq
C\Big{(}\sqrt{\frac{y}{nt^{d/2}}}+\frac{y}{nt^{d/2}}\Big{)}$

with constant $C>0$ depending only on $C_{1}$.

###### Proof.

Let $\xi=k_{t}(X,\cdot)\otimes k_{t}(X,\cdot)-\Sigma_{t}$ and
$\xi_{i}=k_{t}(X_{i},\cdot)\otimes k_{t}(X_{i},\cdot)-\Sigma_{t}$ for $1\leq
i\leq n$. Then we have

$\displaystyle\hat{\Sigma}_{t}-\Sigma_{t}=\frac{1}{n}\sum_{i=1}^{n}\xi_{i},$

and our goal is to apply the operator Bernstein inequality stated in Appendix
A.2. First,

$\displaystyle\|\xi\|_{\infty}$ $\displaystyle\leq\|k_{t}(X,\cdot)\otimes
k_{t}(X,\cdot)\|_{\infty}+\operatorname{{\mathbb{E}}}\|k_{t}(X,\cdot)\otimes
k_{t}(X,\cdot)\|_{\infty}$
$\displaystyle=\|k_{t}(X,\cdot)\|_{\operatorname{{\mathcal{H}}}_{t}}^{2}+\operatorname{{\mathbb{E}}}\|k_{t}(X,\cdot)\|_{\operatorname{{\mathcal{H}}}_{t}}^{2}$
$\displaystyle=k_{t}(X,X)+\operatorname{{\mathbb{E}}}k_{t}(X,X)$
$\displaystyle\leq 2C_{1}t^{-d/2}$

almost surely, where we successively applied the triangle inequality, Jensen’s
inequality, the reproducing property in (2.1), and (C1). Similarly, we have

$\displaystyle\|\operatorname{{\mathbb{E}}}\xi^{2}\|_{\infty}$
$\displaystyle\leq\|\operatorname{{\mathbb{E}}}(k_{t}(X,\cdot)\otimes
k_{t}(X,\cdot))^{2}\|_{\infty}$
$\displaystyle=\|\operatorname{{\mathbb{E}}}k_{t}(X,X)(k_{t}(X,\cdot)\otimes
k_{t}(X,\cdot))\|_{\infty}$ $\displaystyle\leq
C_{1}t^{-d/2}\|\Sigma_{t}\|_{\infty}\leq C_{1}t^{-d/2}$

and

$\displaystyle\operatorname{tr}(\operatorname{{\mathbb{E}}}\xi^{2})$
$\displaystyle=\operatorname{tr}(\operatorname{{\mathbb{E}}}k_{t}(X,X)(k_{t}(X,\cdot)\otimes
k_{t}(X,\cdot)))$ $\displaystyle\leq
C_{1}t^{-d/2}\operatorname{{\mathbb{E}}}\operatorname{tr}(k_{t}(X,\cdot)\otimes
k_{t}(X,\cdot))$
$\displaystyle=C_{1}^{-d/2}\operatorname{{\mathbb{E}}}k_{t}(X,X)\leq
C_{1}^{2}t^{-d}.$

An application of Lemma 15 yields

$\displaystyle\operatorname{{\mathbb{P}}}\Big{(}\Big{\|}\frac{1}{n}\sum_{i=1}^{n}\xi_{i}\Big{\|}_{\infty}\geq
u\Big{)}$ $\displaystyle\leq
Ct^{-d/2}\exp\Big{(}-c\frac{nu^{2}}{t^{-d/2}+t^{-d/2}u}\Big{)}$
$\displaystyle\leq Ct^{-d/2}\exp(-cnt^{d/2}\min(u,u^{2}))$

for all $u>0$. Setting

$u=\max\Big{(}\sqrt{\frac{y}{nt^{d/2}}},\frac{y}{nt^{d/2}}\Big{)},$

the claim follows. ∎

######  Theorem 1.

Suppose that (C1) is satisfied. Then there are constants $c,C>0$ depending
only on $C_{1}$ such that the following holds. Suppose that $\frac{\log
n}{nt^{d/2}}\leq c$. Then, with probability at least $1-Cn^{-c}$, we have

$\displaystyle\forall
j\in\operatorname{{\mathbb{N}}},\qquad\Big{|}\frac{1-\hat{\lambda}_{t,j}}{t}-\frac{1-e^{-\mu_{j}t}}{t}\Big{|}\leq
C\sqrt{\frac{\log n}{nt^{d/2+2}}}$

and

$\displaystyle\forall
j\in\operatorname{{\mathbb{N}}},\qquad\Big{|}\frac{1-\hat{\lambda}_{t,j}}{t}-\mu_{j}\Big{|}\leq
C\sqrt{\frac{\log n}{nt^{d/2+2}}}+\mu_{j}^{2}t$

###### Proof.

The first claim follows from Lemma 4 and Lemma 8. The second claim follows
from the inequalities $-x^{2}/2\leq 1-e^{-x}-x\leq 0$, $x\geq 0$. ∎

######  Theorem 2.

Suppose that (C1) is satisfied. Then there are constants $c,C>0$ depending
only on $C_{1}$ such that the following holds. Let
$j\in\operatorname{{\mathbb{N}}}$ and $t\in(0,1]$ be such that
$\mu_{j+1}>\mu_{j}$, $\mu_{j+1}t\leq 1$ and $\frac{\log n}{nt^{d/2}}\leq c$.
Then, with probability at least $1-Cn^{-c}$, we have

$\displaystyle\|\hat{P}_{t,\leq j}-P_{t,\leq j}\|_{2}\leq
C\frac{\sqrt{j}}{\mu_{j+1}-\mu_{j}}\sqrt{\frac{\log n}{nt^{d/2+2}}}.$

###### Proof.

Combining Lemma 4 with the Davis-Kahan bound in Lemma 8, we get

$\displaystyle\|\hat{P}_{t,\leq j}-P_{t,\leq j}\|_{2}\leq
C\frac{\sqrt{j}}{e^{-\mu_{j}t}-e^{-\mu_{j+1}t}}\sqrt{\frac{\log n}{nt^{d/2}}}$

with probability at least $1-Cn^{-c}$. Inserting

$\displaystyle\frac{1}{e^{-\mu_{j}t}-e^{-\mu_{j+1}t}}=\frac{e^{\mu_{j+1}t}}{e^{(\mu_{j+1}-\mu_{j})t}-1}\leq\frac{e}{(\mu_{j+1}-\mu_{j})t},$

where we also used that $\mu_{j+1}t\leq 1$ and $\mu_{j+1}>\mu_{j}$, the claim
follows. ∎

To obtain more refined perturbation bounds for the nullspace, we introduce the
relative complexity measure (see, e.g., Appendix A.1.1)

$\displaystyle\delta_{\leq m}(\hat{\Sigma}_{t}-\Sigma_{t})$
$\displaystyle=\Big{\|}\Big{(}\frac{P_{t,\leq
m}}{1-e^{-\mu_{m+1}t}}+R_{t,>m}\Big{)}^{\frac{1}{2}}(\hat{\Sigma}_{t}-\Sigma_{t})\Big{(}\frac{P_{t,\leq
m}}{1-e^{-\mu_{m+1}t}}+R_{t,>m}\Big{)}^{\frac{1}{2}}\Big{\|}_{\infty}$

with reduced outer resolvent

$\displaystyle R_{t,>m}=\sum_{k>m}\frac{P_{t,k}}{1-e^{-\mu_{k}t}}.$

The following result extends Lemma 4.

######  Lemma 5.

Suppose that (C1) and (C2) are satisfied. Let $d\geq 3$ and $t\in(0,1]$ be
such that $\mu_{m+1}t\leq 1$. Then, with probability at least
$1-Ct^{-d/2+1}e^{-y}$, $y>0$, we have

$\displaystyle\|\delta_{\leq m}(\hat{\Sigma}_{t}-\Sigma_{t})\|_{\infty}\leq
C\Big{(}\sqrt{\frac{y}{nt^{d/2+1}}}+\frac{y}{nt^{d/2}}\Big{)}$

with constant $C>0$ depending only on $C_{1}$, $C_{2}$ and $m$.

###### Proof.

For $1\leq i\leq n$, set

$\displaystyle Z$ $\displaystyle=\Big{(}\frac{P_{t,\leq
m}}{1-e^{-\mu_{m+1}t}}+R_{t,>m}\Big{)}^{\frac{1}{2}}X,\qquad Z_{i}$
$\displaystyle=\Big{(}\frac{P_{t,\leq
m}}{1-e^{-\mu_{m+1}t}}+R_{t,>m}\Big{)}^{\frac{1}{2}}X_{i}$

and

$\displaystyle\xi=Z\otimes Z-\operatorname{{\mathbb{E}}}(Z\otimes
Z),\qquad\xi_{i}=Z_{i}\otimes Z_{i}-\operatorname{{\mathbb{E}}}(Z_{i}\otimes
Z_{i}).$

Then we have

$\displaystyle\|\delta_{\leq
m}(\hat{\Sigma}_{t}-\Sigma_{t})\|_{\infty}=\Big{\|}\frac{1}{n}\sum_{i=1}^{n}\xi_{i}\Big{\|}_{\infty}$

and our goal is to again apply the operator Bernstein inequality stated in
Appendix A.2. We start with bounding $\|Z\|_{\mathcal{H}_{t}}$. By the KL
representation in (2.2), we have

$\displaystyle\|Z\|_{\mathcal{H}_{t}}^{2}=\frac{1}{1-e^{-\mu_{m+1}t}}\sum_{k=1}^{m}\phi_{k}^{2}(X)+\sum_{k>m}\frac{e^{-\mu_{k}t}}{1-e^{-\mu_{k}t}}\phi_{k}^{2}(X).$
(2.5)

On the one hand, we have

$\displaystyle\frac{1}{1-e^{-\mu_{m+1}t}}\sum_{k=1}^{m}\phi_{k}^{2}(X)$
$\displaystyle\leq\frac{e^{\mu_{m+1}t}}{e^{\mu_{m+1}t}-1}\sum_{k=1}^{m}\phi_{k}^{2}(X)$
$\displaystyle\leq\frac{eC_{2}m}{\mu_{m+1}}t^{-1}\leq Ct^{-d/2}$ (2.6)

with a constant $C>0$ depending only on $C_{1}$, $C_{2}$ and $m$, and where we
applied $\mu_{m+1}t\leq 1$, (C2), (2.4) and $d\geq 3$. To bound the second
term on the right-hand side of (2.5), introduce

$\displaystyle a_{k}=\frac{e^{-\mu_{k}t}}{1-e^{-\mu_{k}t}}\quad\text{and}\quad
B_{k}=\sum_{l=1}^{k}\phi_{l}^{2}(X)$

for $k>m$. Then $a_{m+1},a_{m+2},\dots$ is a non-increasing sequence with

$\displaystyle\sum_{k>m}a_{k}\leq Ct^{-d/2}$

by Lemma 17, and the $B_{k}$ satisfy $B_{k}\leq C_{2}k$ for all $k>m$ by (C2).
Hence, by partial summation, we get

$\displaystyle\sum_{k=m+1}^{M}a_{k}(B_{k}-B_{k-1})$
$\displaystyle=a_{M}B_{M}-a_{m+1}B_{m}+\sum_{k=m+1}^{M-1}(a_{k}-a_{k+1})B_{k}$
$\displaystyle\leq Ca_{M}M+C\sum_{k=m+1}^{M-1}(a_{k}-a_{k+1})k\leq
C\sum_{k=m+1}^{M}a_{k}$

for all $M>m$. Letting $M$ go to infinity, we get

$\displaystyle\sum_{k>m}\frac{e^{-\mu_{k}t}}{1-e^{-\mu_{k}t}}\phi_{k}^{2}(X)=\sum_{k>m}a_{k}(B_{k}-B_{k-1})\leq
C\sum_{k>m}a_{k}\leq Ct^{-d/2}.$ (2.7)

Inserting (2.3) and (2.7) into (2.5), we arrive at

$\displaystyle\|Z\|_{\mathcal{H}_{t}}^{2}\leq Ct^{-d/2},$

with a constant $C>0$ depending only on $C_{1}$, $C_{2}$ and $m$. Next, let us
bound $\|\operatorname{{\mathbb{E}}}(Z\otimes Z)\|_{\infty}$. By construction,
we have

$\displaystyle\operatorname{{\mathbb{E}}}(Z\otimes Z)=\Big{(}\frac{P_{t,\leq
m}}{1-e^{-\mu_{m+1}t}}+R_{t,>m}\Big{)}^{1/2}\Sigma_{t}\Big{(}\frac{P_{t,\leq
m}}{1-e^{-\mu_{m+1}t}}+R_{t,>m}\Big{)}^{1/2},$

so that

$\displaystyle\|\operatorname{{\mathbb{E}}}(Z\otimes
Z)\|_{\infty}=\frac{1}{1-e^{-\mu_{m+1}t}}=\frac{e^{\mu_{m+1}t}}{e^{\mu_{m+1}t}-1}\leq\frac{e}{\mu_{m+1}t}\leq\frac{C}{t},$

where we applied the spectral decomposition in Lemma 1, the condition
$\mu_{m+1}t\leq 1$ and (2.4).

Equipped with the bounds for $\|Z\|_{\mathcal{H}_{t}}$ and
$\|\operatorname{{\mathbb{E}}}(Z\otimes Z)\|_{\infty}$, we can now proceed as
in Lemma 2. In particular, we have

$\displaystyle\|\xi\|_{\infty}\leq\|Z\|_{\operatorname{{\mathcal{H}}}_{t}}^{2}+\operatorname{{\mathbb{E}}}\|Z\|_{\operatorname{{\mathcal{H}}}_{t}}^{2}\leq
Ct^{-d/2},$ $\displaystyle\|\operatorname{{\mathbb{E}}}\xi^{2}\|_{\infty}$
$\displaystyle\leq\|\operatorname{{\mathbb{E}}}\|Z\|_{\operatorname{{\mathcal{H}}}_{t}}(Z\otimes
Z)\|_{\infty}\leq Ct^{-d/2-1},$ (2.8)

and

$\displaystyle\operatorname{tr}(\operatorname{{\mathbb{E}}}\xi^{2})$
$\displaystyle=\operatorname{tr}(\|Z\|_{\operatorname{{\mathcal{H}}}_{t}}(Z\otimes
Z))\leq
Ct^{-d/2}\operatorname{{\mathbb{E}}}\|Z\|_{\operatorname{{\mathcal{H}}}_{t}}^{2}\leq
C^{2}t^{-d}.$

An application of Lemma 15 yields

$\displaystyle\operatorname{{\mathbb{P}}}\Big{(}\Big{\|}\frac{1}{n}\sum_{i=1}^{n}\xi_{i}\Big{\|}_{\infty}\geq
u\Big{)}$ $\displaystyle\leq
Ct^{-d/2+1}\exp\Big{(}-c\frac{nu^{2}}{t^{-d/2-1}+t^{-d/2}u}\Big{)}$
$\displaystyle\leq Ct^{-d/2+1}\exp(-cn\min(t^{d/2}u,u^{2}t^{d/2+1}))$

for all $u>0$. Setting

$u=\max\Big{(}\sqrt{\frac{y}{nt^{d/2+1}}},\frac{y}{nt^{d/2}}\Big{)},$

the claim follows. ∎

######  Theorem 3.

Suppose that (C1) and (C2) are satisfied. Let $n\geq 2$, $d\geq 5$ and
$t\in(0,1]$ be such that $\mu_{m+1}t\leq 1$ and $\frac{\log n}{nt^{d/2+1}}\leq
c$. Then, with probability at least $1-Cn^{-c}$, we have

$\displaystyle\Big{|}\frac{1-\hat{\lambda}_{t,j}}{t}\Big{|}\leq
C\sqrt{\frac{\log n}{nt^{2}}}+C\frac{\log n}{nt^{d/2+1}}$

for all $1\leq j\leq m$ and

$\displaystyle\|\hat{P}_{t,\leq m}-P_{t,\leq m}\|_{2}\leq C\sqrt{\frac{\log
n}{nt^{d/2}}}+C\frac{\log n}{nt^{d/2+1}},$

with constants $c,C>0$ depending only on $C_{1}$, $C_{2}$ and $m$. In
particular, if additionally $\frac{\log n}{nt^{d/2+2}}\leq c$ holds, then,
with probability at least $1-Cn^{-c}$, we have

$\displaystyle\Big{|}\frac{1-\hat{\lambda}_{t,j}}{t}\Big{|}\leq
C\sqrt{\frac{\log n}{nt^{d/2}}},$

for all $1\leq j\leq m$ and

$\displaystyle\|\hat{P}_{t,\leq m}-P_{t,\leq m}\|_{2}\leq C\sqrt{\frac{\log
n}{nt^{d/2}}}.$

Extensions to other eigenspaces can be obtained analogously, but require
extensions of the perturbation bounds from [47] to the case of eigenvalues
with multiplicities.

###### Proof.

By Lemma 5 we have

$\displaystyle\delta_{\leq m}(\hat{\Sigma}_{t}-\Sigma_{t})$ $\displaystyle\leq
C\Big{(}\sqrt{\frac{\log n}{nt^{d/2+1}}}+\frac{\log n}{nt^{d/2}}\Big{)}\leq
1/4$ (2.9)

with probability at least $1-Cn^{-c}$, provided that the constant $c$ in the
assumptions of Theorem 3 is chosen suffficiently small. On this event, Lemma
10 yields

$\displaystyle\Big{|}\frac{1-\hat{\lambda}_{t,j}}{t}\Big{|}$
$\displaystyle\leq\frac{1}{t}\|P_{t,\leq
m}(\hat{\Sigma}_{t}-\Sigma_{t})P_{t,\leq m}\|_{2}+\mu_{m+1}\cdot\delta_{\leq
m}(\hat{\Sigma}_{t}-\Sigma_{t})^{2}$

for all $1\leq j\leq m$ and

$\displaystyle\|\hat{P}_{t,\leq m}-P_{t,\leq m}\|_{2}\leq\sqrt{2}\|P_{t,\leq
m}(\hat{\Sigma}_{t}-\Sigma_{t})R_{t,>m}\|_{2}+C\cdot\delta_{\leq
m}(\hat{\Sigma}_{t}-\Sigma_{t})^{2},$

where we also used that $\mu_{1}=0$ and that
$t^{-1}(1-e^{-\mu_{m+1}t})\leq\mu_{m+1}$ in the first inequality. We have

$\displaystyle\|P_{t,\leq m}(\hat{\Sigma}_{t}-\Sigma_{t})P_{t,\leq
m}\|_{2}^{2}=\sum_{j=1}^{m}\sum_{k=1}^{m}\Big{(}\frac{1}{n}\sum_{i=1}^{n}\phi_{j}(X_{i})\phi_{k}(X_{i})-\delta_{jk}\Big{)}^{2}$

and

$\displaystyle\|P_{t,\leq
m}(\hat{\Sigma}_{t}-\Sigma_{t})R_{t,>m}\|_{2}^{2}=\sum_{j=1}^{m}\sum_{k=m+1}^{\infty}\frac{e^{-\mu_{k}t}}{(1-e^{-\mu_{k}t})^{2}}\Big{(}\frac{1}{n}\sum_{i=1}^{n}\phi_{j}(X_{i})\phi_{k}(X_{i})\Big{)}^{2},$

as can be seen from inserting the KL representation in (2.2). The sequence
$e^{-\mu_{k}t}/(1-e^{-\mu_{k}t})^{2}$ is non-increasing and satisfies

$\displaystyle\sum_{k>m}\frac{e^{-\mu_{k}t}}{(1-e^{-\mu_{k}t})^{2}}\leq
Ct^{-d/2}\quad\text{and}\quad\sum_{k>m}\frac{ke^{-\mu_{k}t}}{(1-e^{-\mu_{k}t})^{2}}\leq
Ct^{-d},$

as follows from Lemma 17, (C1), (2.4), and the fact that $d\geq 5$. Moreover,
by (C2), we have

$\displaystyle\forall
N\in\operatorname{{\mathbb{N}}},\qquad\Big{|}\sum_{j=1}^{m}\sum_{k=1}^{N}\phi_{j}^{2}(X)\phi_{k}^{2}(X)\Big{|}\leq
C_{2}^{2}mN$

Hence, by Lemma 16, we obtain with probability at least $1-Cn^{-c}$,

$\displaystyle\sum_{j=1}^{m}\sum_{k=1}^{m}\Big{(}\frac{1}{n}\sum_{i=1}^{n}\phi_{j}(X_{i})\phi_{k}(X_{i})-\delta_{jk}\Big{)}^{2}\leq
C\frac{\log n}{n}$

and

$\displaystyle\sum_{j=1}^{m}\sum_{k=m+1}^{\infty}\frac{e^{-\mu_{k}t}}{(1-e^{-\mu_{k}t})^{2}}\Big{(}\frac{1}{n}\sum_{i=1}^{n}\phi_{j}(X_{i})\phi_{k}(X_{i})\Big{)}^{2}$
$\displaystyle\leq C\Big{(}\frac{\log
n}{nt^{d/2}}+\frac{\log^{2}n}{n^{2}t^{d}}\Big{)}$ $\displaystyle\leq
C\frac{\log n}{nt^{d/2}}.$

We conclude that, with probability at least $1-Cn^{-c}$,

$\displaystyle\Big{|}\frac{1-\hat{\lambda}_{t,j}}{t}\Big{|}$
$\displaystyle\leq C\sqrt{\frac{\log n}{nt^{2}}}+C\frac{\log
n}{nt^{d/2+1}}+C\frac{\log^{2}n}{n^{2}t^{d}}$ $\displaystyle\leq
C\sqrt{\frac{\log n}{nt^{2}}}+C\frac{\log n}{nt^{d/2+1}},$

for all $1\leq j\leq m$ and

$\displaystyle\|\hat{P}_{t,\leq m}-P_{t,\leq m}\|_{2}\leq C\sqrt{\frac{\log
n}{nt^{d/2}}}+C\frac{\log n}{nt^{d/2+1}}.$

This completes the proof. ∎

##  3 The approximation error

###  3.1 Different graph Laplacians

Recall that $\operatorname{{\mathcal{M}}}$ is a closed submanifold of
$\operatorname{{\mathbb{R}}}^{p}$ with $\dim\operatorname{{\mathcal{M}}}=d$
and $\operatorname{vol}(M)=1$, equipped with the Riemannian metric induced by
the ambient space. Let $d_{\operatorname{{\mathcal{M}}}}$ be the intrinsic
distance on $\operatorname{{\mathcal{M}}}$ (see, e.g., Definition 4.21 in
[36]), where we additionally set
$d_{\operatorname{{\mathcal{M}}}}(x,y)=+\infty$ whenever $x$ and $y$ belong to
different components of $\operatorname{{\mathcal{M}}}$. Moreover, let
$\|x-y\|_{2}$ be the Euclidean (extrinsic) distance between
$x,y\in\operatorname{{\mathcal{M}}}$. We consider the heat kernel $k_{t}$, the
geodesic kernel $g_{t}$ and the Gaussian kernel $w_{t}$, where the latter two
are defined by

$\displaystyle g_{t}(x,y)$ $\displaystyle=\frac{1}{(4\pi
t)^{d/2}}\exp\Big{(}-\frac{d_{\operatorname{{\mathcal{M}}}}(x,y)^{2}}{4t}\Big{)},$
$\displaystyle w_{t}(x,y)$ $\displaystyle=\frac{1}{(4\pi
t)^{d/2}}\exp\Big{(}-\frac{\|x-y\|_{2}^{2}}{4t}\Big{)},$

for $x,y\in\operatorname{{\mathcal{M}}}$. Based on these kernels, we introduce
the following un-normalized graph Laplacians

$\displaystyle\mathscr{L}_{k_{t}}$
$\displaystyle=\frac{D_{k_{t}}-K_{t}}{t}\in\operatorname{{\mathbb{R}}}^{n\times
n},$ $\displaystyle\mathscr{L}_{g_{t}}$
$\displaystyle=\frac{D_{g_{t}}-G_{t}}{t}\in\operatorname{{\mathbb{R}}}^{n\times
n},$ $\displaystyle\mathscr{L}_{w_{t}}$
$\displaystyle=\frac{D_{w_{t}}-W_{t}}{t}\in\operatorname{{\mathbb{R}}}^{n\times
n},$

where

$\displaystyle(K_{t})_{ij}$ $\displaystyle=\frac{1}{n}k_{t}(X_{i},X_{j}),$
$\displaystyle(G_{t})_{ij}$ $\displaystyle=\frac{1}{n}g_{t}(X_{i},X_{j}),$
$\displaystyle(W_{t})_{ij}$ $\displaystyle=\frac{1}{n}w_{t}(X_{i},X_{j}),$

and the degree matrices $D_{k_{t}}$, $D_{g_{t}}$ and $D_{w_{t}}$ are diagonal
matrices with

$\displaystyle(D_{k_{t}})_{ii}$
$\displaystyle=\frac{1}{n}\sum_{j=1}^{n}k_{t}(X_{i},X_{j}),$
$\displaystyle(D_{g_{t}})_{ii}$
$\displaystyle=\frac{1}{n}\sum_{j=1}^{n}g_{t}(X_{i},X_{j}),$
$\displaystyle(D_{w_{t}})_{ii}$
$\displaystyle=\frac{1}{n}\sum_{j=1}^{n}w_{t}(X_{i},X_{j}).$

###  3.2 Analysis of the approximation error

In order to relate the different graph Laplacians, we need relationships
between the extrinsic and the intrinsic distance and between the geodesic
kernel and the heat kernel. Again, for better reference, we formulate these
relationships as conditions with explicit constants and refer to the
literature where these properties are proven.

(C3)

(Extrinsic and intrinsic distance). Suppose that there are constants
$c_{3}\in(0,1)$ and $C_{3}>1$ such that

$\displaystyle 0\leq
d_{\operatorname{{\mathcal{M}}}}^{2}(x,y)-\|x-y\|_{2}^{2}\leq
C_{3}d_{\operatorname{{\mathcal{M}}}}^{4}(x,y)$

for all $x,y\in\operatorname{{\mathcal{M}}}$,
$d_{\operatorname{{\mathcal{M}}}}(x,y)<c_{3}$ and

$\displaystyle\inf_{x,y\in\operatorname{{\mathcal{M}}},d_{\operatorname{{\mathcal{M}}}}(x,y)>s}\|x-y\|_{2}^{2}\geq
c_{3}d_{\operatorname{{\mathcal{M}}}}^{2}(x,y)$

for all $0<s<c_{3}$.

The first condition is standard in the manifold learning literature (see,
e.g., [19, 4, 13]), and proven by the exponential map and Taylor expansions.
The second condition measures the bottleneckness of
$\operatorname{{\mathcal{M}}}$ and the distance between the different
connected components of $\operatorname{{\mathcal{M}}}$.

######  Lemma 6.

Suppose that (C3) is satisfied. Let $K\in\operatorname{{\mathbb{N}}}$. Then
there exist constants $C>0$ and $c\in(0,1)$ depending only on $c_{3},C_{3}$,
$d$ and $K$ such that

$\displaystyle|w_{t}(x,y)-g_{t}(x,y)|\leq
Cg_{t}(x,y)t\log^{2}(\tfrac{e}{t})+Ct^{K}$

for all $x,y\in\operatorname{{\mathcal{M}}}$ and all $t\in(0,c)$.

###### Proof.

Let $t\in(0,1]$ be such that

$\displaystyle\delta(t):=\sqrt{\frac{4(K+d/2)}{c_{3}}t\log(\tfrac{e}{t})}<c_{3}.$

Let $x,y\in\operatorname{{\mathcal{M}}}$ be arbitrary. If
$d_{\operatorname{{\mathcal{M}}}}(x,y)>\delta(t)$, then (C3) yields
$\|x-y\|_{2}^{2}>c_{3}\delta(t)^{2}$ and thus

$\displaystyle 0\leq w_{t}(x,y)-g_{t}(x,y)$ $\displaystyle\leq
w_{t}(x,y)\leq\frac{1}{(4\pi
t)^{d/2}}\exp\Big{(}-c_{3}\frac{\delta(t)^{2}}{4t}\Big{)}$ $\displaystyle\leq
Ct^{-d/2}t^{K+d/2}=Ct^{K}.$ (3.1)

On the other hand, if $d_{\operatorname{{\mathcal{M}}}}(x,y)\leq\delta(t)$,
then (C3) yields

$\displaystyle 0\leq w_{t}(x,y)-g_{t}(x,y)$ $\displaystyle\leq
g_{t}(x,y)\exp\Big{(}C_{3}\frac{d_{\operatorname{{\mathcal{M}}}}^{4}(x,y)}{4t}\Big{)}-g_{t}(x,y)$
$\displaystyle\leq g_{t}(x,y)(\exp(Ct\log^{2}(\tfrac{e}{t}))-1)$
$\displaystyle\leq Cg_{t}(x,y)t\log^{2}(\tfrac{e}{t}).$ (3.2)

The claim follows from combining (3.1) and (3.2). ∎

(C4)

(First order asymptotic expansion of the heat kernel). There are smooth
functions $u$ and $r_{t}$ on
$\operatorname{{\mathcal{M}}}\times\operatorname{{\mathcal{M}}}$ and constants
$c_{4}\in(0,1)$ and $C_{4}>0$ such that

$\displaystyle k_{t}(x,y)=g_{t}(x,y)(1+u(x,y)+r_{t}(x,y))$

with

$\displaystyle|u(x,y)|\leq
C_{4}d_{\operatorname{{\mathcal{M}}}}^{2}(x,y)\quad\text{and}\quad|r_{t}(x,y)|\leq
C_{4}t$

for all $x,y\in\operatorname{{\mathcal{M}}}$ with
$d_{\operatorname{{\mathcal{M}}}}(x,y)<c_{4}$ and all $t\in(0,1]$.

If $x$ and $y$ belong to different components, then $k_{t}(x,y)=g_{t}(x,y)=0$
and the above condition is trivially satisfied with $u(x,y)=r_{t}(x,y)=0$. If
$x$ and $y$ belong to the same connected component, then (C4) is a consequence
of the parametrix construction. See, e.g., Equation (45) in [12] (which is an
improvement over Exercise 5 in [38]) and also [19] for an upper bound on $u$.

(C5)

(Refined global heat kernel). There are constants $c_{5}\in(0,1/4]$ and
$C_{5}>0$ such that

$\displaystyle
k_{t}(x,y)\leq\frac{C_{5}}{t^{d/2}}\exp\Big{(}-c_{5}\frac{d^{2}_{\operatorname{{\mathcal{M}}}}(x,y)}{t}\Big{)}$

for all $x,y\in\operatorname{{\mathcal{M}}}$ and all $t\in(0,1]$.

######  Lemma 7.

Suppose that (C4) and (C5) are satisfied. Let
$K\in\operatorname{{\mathbb{N}}}$. Then there exist constants $C>0$ and
$c\in(0,1)$ depending only on $c_{4},c_{5},C_{4},C_{5}$, $d$ and $K$ such that

$\displaystyle|k_{t}(x,y)-g_{t}(x,y)|\leq
Ck_{t}(x,y)t\log(\tfrac{e}{t})+Ct^{K}$

for all $x,y\in\operatorname{{\mathcal{M}}}$ and all $t\in(0,c)$.

###### Proof.

Let $t\in(0,1]$ be such that

$\displaystyle\delta(t):=\sqrt{\frac{(K+d/2)}{c_{5}}t\log(\tfrac{e}{t})}<c_{4}.$

Let $x,y\in\operatorname{{\mathcal{M}}}$ be arbitrary. If
$d_{\operatorname{{\mathcal{M}}}}(x,y)>\delta(t)$, then (C5) yields

$\displaystyle k_{t}(x,y)\leq C_{5}t^{-d/2}e^{-c_{5}\delta^{2}(t)/t}\leq
Ct^{-d/2}t^{K+d/2}=Ct^{K}$ (3.3)

and, since $c_{5}<1/4$,

$\displaystyle g_{t}(x,y)\leq(4\pi t)^{-d/2}e^{-\delta^{2}(t)/(4t)}\leq
Ct^{-d/2}t^{K+d/2}=Ct^{K}.$ (3.4)

On the other hand, if $d_{\operatorname{{\mathcal{M}}}}(x,y)\leq\delta(t)$,
then (C4) yields

$\displaystyle k_{t}(x,y)$ $\displaystyle=(1+u(x,y)+r_{t}(x,y))$
$\displaystyle\leq g_{t}(x,y)(1+C_{4}\delta^{2}(t)+C_{4}t)$ $\displaystyle\leq
g_{t}(x,y)(1+Ct\log(\tfrac{e}{t}))$

and similarly

$\displaystyle k_{t}(x,y)$ $\displaystyle\geq
g_{t}(x,y)(1-Ct\log(\tfrac{e}{t})).$

Hence, if additionally $Ct\log(\tfrac{e}{t})\leq 1/2$ holds, then

$\displaystyle\frac{1}{1+Ct\log(\tfrac{e}{t})}k_{t}(x,y)\leq
g_{t}(x,y)\leq\frac{1}{1-Ct\log(\tfrac{e}{t})}k_{t}(x,y)$

and, by elementary inequalities,

$\displaystyle(1-Ct\log(\tfrac{e}{t}))k_{t}(x,y)\leq
g_{t}(x,y)\leq(1+2Ct\log(\tfrac{e}{t}))k_{t}(x,y).$ (3.5)

The claim follows from (3.3), (3.4) and (3.5). ∎

######  Corollary 3.

Suppose that (C3), (C4) and (C5) are satisfied. Let
$K\in\operatorname{{\mathbb{N}}}$. Then there exist constants $C>0$ and
$c\in(0,1)$ depending only on $c_{3},c_{4},c_{5},C_{3},C_{4},C_{5}$, $d$ and
$K$ such that

$\displaystyle|k_{t}(x,y)-w_{t}(x,y)|\leq
Ck_{t}(x,y)t\log^{2}(\tfrac{e}{t})+Ct^{K}$

for all $x,y\in\operatorname{{\mathcal{M}}}$ and all $t\in(0,c)$.

###### Proof.

Follows from Lemmas 6 and 7. ∎

We now state the main result of this section.

######  Theorem 4.

Suppose that (C3), (C4) and (C5) are satisfied. Let
$K\in\operatorname{{\mathbb{N}}}$. Then there exist constants $C>0$ and
$c\in(0,1)$ depending only on $c_{3},c_{4},c_{5},C_{3},C_{4},C_{5}$, $d$ and
$K$ such that

$\displaystyle|\langle u,\mathscr{L}_{k_{t}}u\rangle-\langle
u,\mathscr{L}_{w_{t}}u\rangle|\leq Ct\log^{2}(\tfrac{e}{t})(\langle
u,\mathscr{L}_{k_{t}}u\rangle+t^{K}\|u\|_{2}^{2})$

for all $u\in\operatorname{{\mathbb{R}}}^{n}$ and all $t\in(0,c)$.

###### Proof.

Let $c,C>0$ be constants such that the conclusion of Corollary 3 holds with
$K+2$. Let $t\in(0,c)$ and let $u\in\operatorname{{\mathbb{R}}}^{n}$. Then

$\displaystyle|\langle u,(D_{k_{t}}-K_{t})u\rangle-\langle
u,(D_{w_{t}}-W_{t})u\rangle|$
$\displaystyle=\Big{|}\frac{1}{2n}\sum_{i=1}^{n}\sum_{j=1}^{n}k_{t}(X_{i},X_{j})(u_{i}-u_{j})^{2}-\frac{1}{2n}\sum_{i=1}^{n}\sum_{j=1}^{n}w_{t}(X_{i},X_{j})(u_{i}-u_{j})^{2}\Big{|}$
$\displaystyle\leq\frac{1}{2n}\sum_{i=1}^{n}\sum_{j=1}^{n}|k_{t}(X_{i},X_{j})-w_{t}(X_{i},X_{j})|(u_{i}-u_{j})^{2}$
$\displaystyle\leq\frac{1}{2n}\sum_{i=1}^{n}\sum_{j=1}^{n}Ck_{t}(X_{i},X_{j})t\log^{2}(\tfrac{e}{t})(u_{i}-u_{j})^{2}+\frac{1}{2n}\sum_{i=1}^{n}\sum_{j=1}^{n}Ct^{K+2}(u_{i}-u_{j})^{2},$

where we applied (1.2) (to both kernels $w_{t}$ and $k_{t}$) and Corollary 3.
Hence, we arrive at

$\displaystyle|\langle u,(D_{k_{t}}-K_{t})u\rangle-\langle
u,(D_{w_{t}}-W_{t})u\rangle|$ $\displaystyle\leq
Ct\log^{2}(\tfrac{e}{t})\langle
u,(D_{k_{t}}-K_{t})u\rangle+C\frac{t^{K+2}}{n}\sum_{i=1}^{n}\sum_{j=1}^{n}(u_{i}^{2}+u_{j}^{2})$
$\displaystyle=Ct\log^{2}(\tfrac{e}{t})\langle
u,(D_{k_{t}}-K_{t})u\rangle+2Ct^{K+2}\|u\|_{2}^{2}.$

Dividing through $t$, the claim follows. ∎

######  Corollary 4.

Under the assumptions of Theorem 4, we have

$\displaystyle\|(\mathscr{L}_{k_{t}}+t^{K}I_{n})^{-1/2}(\mathscr{L}_{w_{t}}-\mathscr{L}_{k_{t}})(\mathscr{L}_{k_{t}}+t^{K}I_{n})^{-1/2}\|_{\infty}\leq
Ct\log^{2}(\tfrac{e}{t})$

for all $t\in(0,c)$.

##  4 Additional proofs

###  4.1 Proof of Corollary 1

We proceed as in the proof map given in Section 1.5. The claim follows from
the following three steps and the triangle inequality. Recall that we say that
an event holds with high probability, if it holds with probability at least
$1-Cn^{-c}$, where $c,C>0$ are constants depending only on the constants from
(C1), (C3), (C4) and (C5). In the following, we often make use of the fact
that if two events hold with high probability, their union also holds with
high probability.

##### Reduction to heat kernel PCA.

We have

$\displaystyle\forall 1\leq j\leq
n,\qquad\Big{|}\lambda_{j}\Big{(}\frac{I-K_{n}}{t}\Big{)}-\mu_{j}\Big{|}\leq
C\Big{(}\sqrt{\frac{\log n}{nt^{d/2+2}}}+\mu_{j}^{2}t\Big{)}$

with high probability.

###### Proof.

By Theorem 1, we have

$\displaystyle\forall
j\in\operatorname{{\mathbb{N}}},\qquad\Big{|}\frac{1-\hat{\lambda}_{t,j}}{t}-\mu_{j}\Big{|}\leq
C\sqrt{\frac{\log n}{nt^{d/2+2}}}+\frac{\mu_{j}^{2}t}{2}$

with high probability. Hence, the claim follow from the fact that the first
$n$ eigenvalues of $\hat{\Sigma}_{t}$ coincide with those of $K_{t}$. ∎

##### Reduction to the heat graph Laplacian.

We have

$\displaystyle\forall 1\leq j\leq
n,\qquad\Big{|}\lambda_{j}\Big{(}\frac{I_{n}-K_{t}}{t}\Big{)}-\lambda_{j}(\mathscr{L}_{k_{t}})\Big{|}\leq
C\sqrt{\frac{\log n}{nt^{d/2+2}}}$ (4.1)

with high probability.

###### Proof.

By Weyl’s bound, we have

$\displaystyle\Big{|}\lambda_{j}\Big{(}\frac{I_{n}-K_{t}}{t}\Big{)}-\lambda_{j}(\mathscr{L}_{k_{t}})\Big{|}\leq\frac{1}{t}\|I_{n}-D_{k_{t}}\|_{\infty},$
(4.2)

with diagonal matrix $I_{n}-D_{k_{t}}$ such that

$\displaystyle\|I_{n}-D_{k_{t}}\|_{\infty}=\max_{1\leq i\leq
n}\Big{|}\frac{1}{n}\sum_{j=1}^{n}k_{t}(X_{i},X_{j})-1\Big{|}.$

Fix $1\leq i\leq n$. Then

$\displaystyle\Big{|}\frac{1}{n}\sum_{j=1}^{n}(k_{t}(X_{i},X_{j})-1)\Big{|}\leq\frac{|k_{t}(X_{i},X_{i})-1|}{n}+\Big{|}\frac{1}{n}\sum_{j=1,j\neq
i}^{n}(k_{t}(X_{i},X_{j})-1)\Big{|}.$

From (C1) it follows that

$\displaystyle k_{t}(X_{i},X_{i})\leq C_{1}t^{-d/2}$

almost surely and thus

$\displaystyle\frac{|k_{t}(X_{i},X_{i})-1|}{n}\leq\frac{C_{1}t^{-d/2}+1}{n}\leq
C\frac{1}{nt^{d/2}}.$

Moreover for all $j\neq i$, we have

$\displaystyle k_{t}(X_{i},X_{j})\leq\sqrt{k_{t}(X_{i},X_{i})\cdot
k_{t}(X_{j},X_{j})}\leq C_{1}t^{-d/2}$

almost surely and

$\displaystyle\operatorname{{\mathbb{E}}}_{X_{j}}(k_{t}(X_{i},X_{j})-1)^{2}\leq\operatorname{{\mathbb{E}}}_{X_{j}}k_{t}(X_{i},X_{j})^{2}\leq
C_{1}t^{-d/2}\operatorname{{\mathbb{E}}}_{X_{j}}k_{t}(X_{i},X_{j})=C_{1}t^{-d/2},$

where $\operatorname{{\mathbb{E}}}_{X_{j}}$ denotes expectation with respect
to $X_{j}$ only. Hence, an application of Bernstein’s inequality (conditional
on $X_{i}$) yields

$\displaystyle\operatorname{{\mathbb{P}}}\Big{(}\Big{|}\frac{1}{n}\sum_{j=1,j\neq
i}^{n}(k_{t}(X_{i},X_{j})-1)\Big{|}\geq u\Big{)}\leq
2\exp(cnt^{d/2}\min(u,u^{2}))$

for all $u>0$. Setting

$u=C\cdot\max\Big{(}\sqrt{\frac{\log n}{nt^{d/2}}},\frac{\log
n}{nt^{d/2}}\Big{)}\leq C\sqrt{\frac{\log n}{nt^{d/2}}},$

with $C$ sufficiently large, we obtain

$\displaystyle\|I_{n}-D_{k_{t}}\|_{\infty}\leq C\sqrt{\frac{\log
n}{nt^{d/2}}}$ (4.3)

with high probability, where we also applied the union bound. Inserting this
into (4.2), the claim follows. ∎

##### Reduction to the Gaussian graph Laplacian.

We have

$\displaystyle\forall 1\leq j\leq
n,\qquad|\lambda_{j}(\mathscr{L}_{k_{t}})-\lambda_{j}(\mathscr{L}_{w_{t}})|\leq
C\Big{(}\sqrt{\frac{\log n}{nt^{d/2+2}}}+(\mu_{j}^{2}\vee
1)t\log^{2}(\tfrac{e}{t})\Big{)}.$

with high probability.

###### Proof.

For $K\in\operatorname{{\mathbb{N}}}$ let

$\displaystyle\tilde{\mathscr{L}}_{k_{t}}=\mathscr{L}_{k_{t}}+t^{K}I_{n},\qquad\tilde{\mathscr{L}}_{w_{t}}=\mathscr{L}_{w_{t}}+t^{K}I_{n}.$

Then $\tilde{\mathscr{L}}_{k_{t}}$ and $\tilde{\mathscr{L}}_{w_{t}}$ are
strictly positive and Corollary 4 yields

$\displaystyle\|\tilde{\mathscr{L}}_{k_{t}}^{-1/2}(\tilde{\mathscr{L}}_{w_{t}}-\tilde{\mathscr{L}}_{k_{t}})\tilde{\mathscr{L}}_{k_{t}}^{-1/2}\|_{\infty}\leq
Ct\log^{2}(\tfrac{e}{t})$

for all $t\in(0,c)$. An application of Lemma 14 yields

$\displaystyle|\lambda_{j}(\mathscr{L}_{k_{t}})-\lambda_{j}(\mathscr{L}_{w_{t}})|$
$\displaystyle=|\lambda_{j}(\tilde{\mathscr{L}}_{k_{t}})-\lambda_{j}(\tilde{\mathscr{L}}_{w_{t}})|\leq
C\lambda_{j}(\tilde{\mathscr{L}}_{k_{t}})t\log^{2}(\tfrac{e}{t})$

for all $t\in(0,c)$ and all $1\leq j\leq n$. By the previous two steps this
implies that

$\displaystyle|\lambda_{j}(\mathscr{L}_{k_{t}})-\lambda_{j}(\mathscr{L}_{w_{t}})|$
$\displaystyle\leq C\Big{(}\mu_{j}+\mu_{j}^{2}t+t^{K}+\sqrt{\frac{\log
n}{nt^{d/2+2}}}\Big{)}t\log^{2}(\tfrac{e}{t})$ $\displaystyle\leq
C\Big{(}\mu_{j}t\log^{2}(\tfrac{e}{t})+(\mu_{j}^{2}\vee 1)t+\sqrt{\frac{\log
n}{nt^{d/2+2}}}\Big{)}$

for all $t\in(0,c)$ and all $1\leq j\leq n$. ∎

###  4.2 Proof of Corollary 2

We proceed as in the proof map given in Section 1.5. In particular, the claim
follows from the following steps and the triangle inequality.

##### Preliminaries.

Recall that we write $\lambda_{t,k}=e^{-\mu_{k}t}$ for all
$k\in\operatorname{{\mathbb{N}}}$. For all $k\in\operatorname{{\mathbb{N}}}$,
we have

$\displaystyle\|S_{n}\phi_{k}\|_{2}^{2}=\langle\phi_{k},\hat{\Sigma}_{t}\phi_{k}\rangle_{\operatorname{{\mathcal{H}}}_{t}}$
$\displaystyle\leq\hat{\lambda}_{t,k}\cdot\|\phi_{k}\|_{\operatorname{{\mathcal{H}}}_{t}}^{2}$
$\displaystyle\leq(1+\|\hat{\Sigma}_{t}-\Sigma_{t}\|_{\infty})\cdot
e^{\mu_{k}t},$

where we used Weyl’s bound and the fact that $\lambda_{t,k}\leq 1$ for all
$k\in\operatorname{{\mathbb{N}}}$ in the last inequality. Hence, by Lemma 4
and the assumptions in Corollary 2, we have for all $1\leq k\leq j$,

$\displaystyle\|S_{n}\phi_{k}\|_{2}^{2}\leq\Big{(}1+C\sqrt{\frac{\log
n}{nt^{d/2}}}\Big{)}e^{\mu_{k}t}\leq Ce^{\mu_{k}t}\leq Ce$

with high probability. Consequently, we may assume in the following that

$\displaystyle\sqrt{\frac{\log
n}{nt^{d/2+2}}}+\mu_{j+1}t\log^{2}(\tfrac{e}{t})\leq c(\mu_{j+1}-\mu_{j}),$
(4.4)

for some sufficiently small constant $c>0$ (to be determined in the following
steps), since otherwise the claim follows from the fact that the inequality

$\displaystyle\inf_{O\in O(j)}$
$\displaystyle\|(S_{n}\phi_{1},\dots,S_{n}\phi_{j})-(u_{1}(\mathscr{L}_{w_{t}}),\dots,u_{j}(\mathscr{L}_{w_{t}}))O\|_{2}$
$\displaystyle\leq\|(S_{n}\phi_{1},\dots,S_{n}\phi_{j})\|_{2}+\|(u_{1}(\mathscr{L}_{w_{t}}),\dots,u_{j}(\mathscr{L}_{w_{t}}))\|_{2}$
$\displaystyle=\Big{(}\sum_{k=1}^{j}\|S_{n}\phi_{k}\|_{2}^{2}\Big{)}^{1/2}+\sqrt{j}\leq
C\sqrt{j}$

holds with high probability. Let us also collect some perliminary eigenvalue
bounds. First, with high probability, we have

$\displaystyle\hat{\lambda}_{t,j}\geq\lambda_{t,j}-\|\hat{\Sigma}_{t}-\Sigma_{t}\|_{\infty}$
$\displaystyle\geq e^{-\mu_{j}t}-C\sqrt{\frac{\log n}{nt^{d/2}}}$
$\displaystyle\geq e^{-1}-C\sqrt{\frac{\log n}{nt^{d/2}}}\geq\frac{1}{2e},$
(4.5)

provided that $c>0$ from the assumptions is chosen small enough (such that
$c\leq 1/(2Ce)$), meaning that
$\hat{\lambda}_{t,1}\geq\cdots\geq\hat{\lambda}_{t,j}>0$ with high
probability. Moreover, with high probability, we have

$\displaystyle|1-\hat{\lambda}_{t,k}|\leq
1-e^{-\mu_{k}t}+\|\hat{\Sigma}_{t}-\Sigma_{t}\|_{\infty}\leq
1-e^{-\mu_{k}t}+C\sqrt{\frac{\log n}{nt^{d/2}}}\leq c<1$

for all $1\leq k\leq j$. Hence, with high probability, we have

$\displaystyle|\lambda_{t,k}^{-1/2}-1|$ $\displaystyle\leq
C|1-\lambda_{t,k}|\leq Ct\mu_{k}$
$\displaystyle|\hat{\lambda}_{t,k}^{-1/2}-1|$ $\displaystyle\leq
C|1-\hat{\lambda}_{t,k}|\leq C\Big{(}t\mu_{k}+\sqrt{\frac{\log
n}{nt^{d/2}}}\Big{)}$ (4.6)

for all $1\leq k\leq j$, where we also used that $|(1-x)^{-1/2}-1|\leq C|x|$
for all $|x|\leq c<1$.

##### Reduction to heat kernel PCA.

We have

$\displaystyle\inf_{O\in O(j)}$
$\displaystyle\|(S_{n}\phi_{1},\dots,S_{n}\phi_{j})-(\hat{v}_{t,1},\dots,\hat{v}_{t,j})O\|_{2}$
$\displaystyle\leq C\Big{(}\frac{\sqrt{j}}{\mu_{j+1}-\mu_{j}}\sqrt{\frac{\log
n}{nt^{d/2+2}}}+\sqrt{j}\mu_{j}t\Big{)}$

with high probability.

###### Proof.

If $h_{1},\dots,h_{j}$ are elements in $\operatorname{{\mathcal{H}}}_{t}$,
then we consider $(h_{k})_{k=1}^{j}=(h_{1},\dots,h_{j})$ as a linear map from
$\operatorname{{\mathbb{R}}}^{j}$ to $\operatorname{{\mathcal{H}}}_{t}$,
mapping $\alpha\in\operatorname{{\mathbb{R}}}^{j}$ to
$\sum_{k=1}^{j}\alpha_{k}h_{k}$. Now, on the one hand, we have
$\phi_{k}=\lambda_{t,k}^{-1/2}u_{t,k}$ for all
$k\in\operatorname{{\mathbb{N}}}$. On the other hand, (4.5) holds with high
probability, implying that
$\hat{v}_{t,k}=\hat{\lambda}_{t,k}^{-1/2}S_{n}\hat{u}_{t,k}$ for all $1\leq
k\leq j$ by (2.3). We estimate with high probability

$\displaystyle\inf_{O\in O(j)}$
$\displaystyle\|(S_{n}\phi_{1},\dots,S_{n}\phi_{j})-(\hat{v}_{t,1},\dots,\hat{v}_{t,j})O\|_{2}$
$\displaystyle=\inf_{O\in
O(j)}\|S_{n}(\lambda_{t,k}^{-1/2}u_{t,k})_{k=1}^{j}-S_{n}(\hat{\lambda}_{t,k}^{-1/2}\hat{u}_{t,k})_{k=1}^{j}O\|_{2}$
$\displaystyle\leq\|S_{n}\|_{\infty}\cdot\inf_{O\in
O(j)}\|(\lambda_{t,k}^{-1/2}u_{t,k})_{k=1}^{j}-(\hat{\lambda}_{t,k}^{-1/2}\hat{u}_{t,k})_{k=1}^{j}O\|_{2}$
$\displaystyle\leq C\cdot\inf_{O\in
O(j)}\|(u_{t,k})_{k=1}^{j}-(\hat{u}_{t,k})_{k=1}^{j}O\|_{2}$
$\displaystyle+C\|((\lambda_{t,k}^{-1/2}-1)u_{t,k})_{k=1}^{j}\|_{2}+C\|((\hat{\lambda}_{t,k}^{-1/2}-1)\hat{u}_{t,k})_{k=1}^{j}\|_{2}$
$\displaystyle\leq C\|P_{t,\leq j}-\hat{P}_{t,\leq j}\|_{2}$
$\displaystyle+C\sqrt{j}\max_{1\leq k\leq
j}|\lambda_{t,k}^{-1/2}-1|+C\sqrt{j}\max_{1\leq k\leq
j}|\hat{\lambda}_{t,k}^{-1/2}-1|,$

where we applied the fact that $\|S_{n}\|_{\infty}^{2}=\hat{\lambda}_{t,1}\leq
C$ with high probability in the second inequality and Lemma 11 in the last
inequality. Inserting Theorem 2, (4.6), (4.4) and $\mu_{j+1}t\leq 1$ the claim
follows. ∎

##### Reduction to the heat graph Laplacian.

We have

$\displaystyle\inf_{O\in
O(j)}\|(\hat{v}_{t,1},\dots,\hat{v}_{t,j})-(u_{1}(\mathscr{L}_{k_{t}}),\dots,u_{j}(\mathscr{L}_{k_{t}}))O\|_{2}$
$\displaystyle\leq\|P_{\leq j}(\tfrac{1}{t}(I_{n}-K_{t}))-P_{\leq
j}(\mathscr{L}_{k_{t}})\|_{2}\leq C\frac{1}{\mu_{j+1}-\mu_{j}}\sqrt{\frac{\log
n}{nt^{d/2+2}}}.$

with high probability.

###### Proof.

The first equality holds by Lemma 11. To see the second claim, first note that

$\displaystyle\frac{1-\lambda_{t,j+1}}{t}-\frac{1-\lambda_{t,j}}{t}$
$\displaystyle=\frac{e^{-\mu_{j}t}-e^{-\mu_{j+1}t}}{t}$
$\displaystyle=\frac{e^{(\mu_{j+1}-\mu_{j})t}-1}{te^{\mu_{j+1}t}}\geq\frac{(\mu_{j+1}-\mu_{j})t}{te}=\frac{\mu_{j+1}-\mu_{j}}{e},$

where we applied the assumption $\mu_{j+1}t\leq 1$ in the inequality.
Combining this with Weyl’s bound and Lemma 4, we arrive at

$\displaystyle\lambda_{j+1}\Big{(}\frac{I_{n}-K_{t}}{t}\Big{)}-\lambda_{j}\Big{(}\frac{I_{n}-K_{t}}{t}\Big{)}=\frac{1-\hat{\lambda}_{t,j+1}}{t}-\frac{1-\hat{\lambda}_{t,j}}{t}$
$\displaystyle\geq\frac{1-\lambda_{t,j+1}}{t}-\frac{1-\lambda_{t,j}}{t}-\frac{2}{t}\|\hat{\Sigma}_{t}-\Sigma_{t}\|_{\infty}$
$\displaystyle\geq\frac{\mu_{j+1}-\mu_{j}}{e}-C\sqrt{\frac{\log
n}{nt^{d/2+2}}}$ $\displaystyle\geq\frac{\mu_{j+1}-\mu_{j}}{2e},$

with high probability, provided that $c>0$ in (4.4) is chosen small enough
(such that $c\leq 1/(2Ce)$). Combining this with the Davis-Kahan bound in
Corollary 5, we get

$\displaystyle\|P_{\leq j}(\tfrac{1}{t}(I_{n}-K_{t}))-P_{\leq
j}(\mathscr{L}_{k_{t}})\|_{2}\leq
C\sqrt{j}\frac{1}{t}\frac{\|I_{n}-D_{k_{t}}\|_{\infty}}{\mu_{j+1}-\mu_{j}}$
(4.7)

with high probability. Inserting (4.3), the claim follows. ∎

##### Reduction to the Gaussian graph Laplacian.

We have

$\displaystyle\|P_{\leq j}(\mathscr{L}_{k_{t}})-P_{\leq
j}(\mathscr{L}_{w_{t}})\|_{2}\leq
C\sqrt{j}\frac{\mu_{j+1}}{\mu_{j+1}-\mu_{j}}t\log^{2}(\tfrac{e}{t})$

with high probability.

###### Proof.

For $K\in\operatorname{{\mathbb{N}}}$ let
$\tilde{\mathscr{L}}_{k_{t}}=\mathscr{L}_{k_{t}}+t^{K}I_{n}$ and
$\tilde{\mathscr{L}}_{w_{t}}=\mathscr{L}_{w_{t}}+t^{K}I_{n}$. Then
$\tilde{\mathscr{L}}_{k_{t}}$ and $\tilde{\mathscr{L}}_{w_{t}}$ are strictly
positive and Corollary 4 yields

$\displaystyle\|\tilde{\mathscr{L}}_{k_{t}}^{-1/2}(\tilde{\mathscr{L}}_{w_{t}}-\tilde{\mathscr{L}}_{k_{t}})\tilde{\mathscr{L}}_{k_{t}}^{-1/2}\|_{\infty}\leq
Ct\log^{2}(\tfrac{e}{t})$

for all $t\in(0,c)$. In order to apply Corollary 5, it remains to upper bound

$\displaystyle\frac{\lambda_{j+1}(\tilde{\mathscr{L}}_{k_{t}})}{\lambda_{j+1}(\tilde{\mathscr{L}}_{k_{t}})-\lambda_{j}(\tilde{\mathscr{L}}_{k_{t}})}.$

First, by Theorem 1, (4.1), (4.4) and (2.4), we have, with high probability,

$\displaystyle\lambda_{j+1}(\tilde{\mathscr{L}}_{k_{t}})$
$\displaystyle=\lambda_{j+1}(\mathscr{L}_{k_{t}})+t^{K}$
$\displaystyle\leq\frac{1-e^{-\mu_{j+1}t}}{t}+C\sqrt{\frac{\log
n}{nt^{d/2+2}}}+t^{K}$ $\displaystyle\leq\mu_{j+1}+C\sqrt{\frac{\log
n}{nt^{d/2+2}}}+t^{K}\leq C\mu_{j+1}$

for all $t\in(0,c)$. Second, by (4.3) and (4.4), we have, with high
probability,

$\displaystyle\lambda_{j+1}(\tilde{\mathscr{L}}_{k_{t}})-\lambda_{j}(\tilde{\mathscr{L}}_{k_{t}})$
$\displaystyle=\lambda_{j+1}(\mathscr{L}_{k_{t}})-\lambda_{j}(\mathscr{L}_{k_{t}})$
$\displaystyle\geq\lambda_{j+1}\Big{(}\frac{I-K_{t}}{t}\Big{)}-\lambda_{j}\Big{(}\frac{I-K_{t}}{t}\Big{)}-\frac{2}{t}\|I_{n}-D_{k_{t}}\|_{\infty}$
$\displaystyle\geq\frac{\mu_{j+1}-\mu_{j}}{2e}-2C\sqrt{\frac{\log
n}{nt^{d/2+2}}}$ $\displaystyle\geq\frac{\mu_{j+1}-\mu_{j}}{4e},$

provided that $c>0$ in (4.4) is chosen small enough (such that $c\leq
1/(8Ce)$). Applying Corollary 4 conclude that

$\displaystyle\|P_{\leq j}(\mathscr{L}_{k_{t}})$ $\displaystyle-P_{\leq
j}(\mathscr{L}_{w_{t}})\|_{2}=\|P_{\leq
j}(\tilde{\mathscr{L}}_{k_{t}})-P_{\leq j}(\tilde{\mathscr{L}}_{w_{t}})\|_{2}$
$\displaystyle\leq
C\sqrt{j}\frac{\lambda_{j+1}(\tilde{\mathscr{L}}_{k_{t}})}{\lambda_{j+1}(\tilde{\mathscr{L}}_{k_{t}})-\lambda_{j}(\tilde{\mathscr{L}}_{k_{t}})}\|\tilde{\mathscr{L}_{k_{t}}}^{-1/2}(\tilde{\mathscr{L}}_{w_{t}}-\tilde{\mathscr{L}}_{k_{t}})\tilde{\mathscr{L}_{k_{t}}}^{-1/2}\|_{\infty}$
$\displaystyle\leq
C\sqrt{j}\frac{\mu_{j+1}}{\mu_{j+1}-\mu_{j}}t\log^{2}(\tfrac{e}{t}).$

for all $t\in(0,c)$. ∎

##  Appendix A Appendix

###  A.1 Perturbation bounds

####  A.1.1 Positive self-adjoint operators

Let $\Sigma$ be a self-adjoint positive operator on a separable Hilbert space
$\operatorname{{\mathcal{H}}}$. Let $\lambda_{1}\geq\lambda_{2}\geq\dots>0$ be
the sequence of positive eigenvalues and let $u_{1},u_{2},\dots$ be a sequence
of corresponding eigenvectors. We assume that $u_{1},u_{2},\dots$ form an
orthonormal basis of $\operatorname{{\mathcal{H}}}$. For
$j\in\operatorname{{\mathbb{N}}}$, let

$\displaystyle P_{\leq j}=\sum_{k=1}^{j}P_{k},\qquad P_{k}=u_{k}\otimes u_{k}$

be the orthogonal projection onto the eigenspace spanned by
$u_{1},\dots,u_{j}$. Let $\hat{\Sigma}$ be another self-adjoint positive
operator on $\operatorname{{\mathcal{H}}}$. Let
$\hat{\lambda}_{1}\geq\hat{\lambda}_{2}\geq\dots\geq 0$ be the sequence of
non-negative eigenvalues and let $\hat{u}_{1},\hat{u}_{2},\dots$ be a sequence
of corresponding eigenvectors. We also assume that
$\hat{u}_{1},\hat{u}_{2},\dots$ form an orthonormal basis of
$\operatorname{{\mathcal{H}}}$. For $j\in\operatorname{{\mathbb{N}}}$, let

$\displaystyle\hat{P}_{\leq
j}=\sum_{k=1}^{j}\hat{P}_{k},\qquad\hat{P}_{k}=\hat{u}_{k}\otimes\hat{u}_{k}.$

The following lemma states some well-known absolute perturbation bounds for
eigenvalues and eigenvectors (see, e.g., [6]).

######  Lemma 8 (Absolute Weyl and Davis-Kahan bound).

For all $j\in\operatorname{{\mathbb{N}}}$, we have

$\displaystyle|\hat{\lambda}_{j}-\lambda_{j}|$
$\displaystyle\leq\|\hat{\Sigma}-\Sigma\|_{\infty},$
$\displaystyle\|\hat{P}_{\leq j}-P_{\leq j}\|_{2}$
$\displaystyle\leq\sqrt{32j}\frac{\|\hat{\Sigma}-\Sigma\|_{\infty}}{\lambda_{j}-\lambda_{j+1}}.$

For the case of the leading eigenvalue and eigenspace, we formulate relative
perturbation bounds derived in [35, 28, 47]. Let
$m\in\operatorname{{\mathbb{N}}}$ be the multiplicity of $\lambda_{1}$ such
that

$\displaystyle\lambda_{1}=\dots=\lambda_{m}>\lambda_{m+1}.$

Moreover, let

$\displaystyle\delta_{\leq
m}(\hat{\Sigma}-\Sigma)=\Big{\|}\Big{(}\frac{P_{\leq
m}}{\lambda_{1}-\lambda_{m+1}}+R_{>m}\Big{)}^{\frac{1}{2}}(\hat{\Sigma}-\Sigma)\Big{(}\frac{P_{\leq
m}}{\lambda_{1}-\lambda_{m+1}}+R_{>m}\Big{)}^{\frac{1}{2}}\Big{\|}_{\infty}$

with (outer) reduced resolvent

$\displaystyle R_{>m}=\sum_{k>m}\frac{P_{k}}{\lambda_{1}-\lambda_{k}}.$

######  Lemma 9.

We have

$\displaystyle\|\hat{P}_{\leq m}-P_{\leq m}\|_{2}$ $\displaystyle\leq
4\sqrt{2}\sqrt{m}\cdot\delta_{\leq m}(\hat{\Sigma}-\Sigma)$

and

$\displaystyle\|\hat{P}_{\leq m}-P_{\leq m}\|_{2}\leq\sqrt{2}\|P_{\leq
m}(\hat{\Sigma}-\Sigma)R_{>m}\|_{2}+20\sqrt{2}m\cdot\delta_{\leq
m}(\hat{\Sigma}-\Sigma)^{2}.$

###### Proof.

See Proposition 1 in [26]. For the second bound combine (2.4) in [26] with the
triangle inequality. ∎

######  Lemma 10.

Assume that $\delta_{\leq m}(\hat{\Sigma}-\Sigma)\leq 1/4$. Then

$\displaystyle|\hat{\lambda}_{j}-\lambda_{1}|$
$\displaystyle\leq(\lambda_{1}-\lambda_{m+1})\cdot\delta_{\leq
m}(\hat{\Sigma}-\Sigma).$

and

$\displaystyle|\hat{\lambda}_{j}-\lambda_{1}|\leq\|P_{\leq m}EP_{\leq
m}\|_{2}+C(\lambda_{1}-\lambda_{m+1})m\cdot\delta_{\leq
m}(\hat{\Sigma}-\Sigma)^{2}$

for all $1\leq j\leq m$, with some absolute constant $C>0$.

###### Proof.

Follows from proceeding as in Lemma 8 of [26] or [47]. See also Theorem 3 in
[28]. ∎

######  Lemma 11.

Consider $(u_{1},\dots,u_{j})$ and $(\hat{u}_{1},\dots,\hat{u}_{j})$ as linear
maps from $\operatorname{{\mathbb{R}}}^{j}$ to $\operatorname{{\mathcal{H}}}$.
Then we have

$\displaystyle\inf_{O\in
O(j)}\|(u_{1},\dots,u_{j})-(\hat{u}_{1},\dots,\hat{u}_{j})O\|_{2}\leq\|\hat{P}_{\leq
j}-P_{\leq j}\|_{2}$

with $\|\cdot\|_{2}$ denoting the Hilbert-Schmidt norm.

###### Proof.

See, e.g., Equation (2.6) and Proposition 2 in [46]. ∎

####  A.1.2 Symmetric matrices

We reformulate the results of Section A.1.1 in the case of matrices, since our
assumptions and notations for Laplacian matrices are slightly different from
those for covariance operators (for instance, the eigenvalues are listed in
reverse order). Let $A\in\operatorname{{\mathbb{R}}}^{n\times n}$ be a
symmetric matrix. Let

$\displaystyle\lambda_{1}(A)\leq\lambda_{2}(A)\leq\dots\leq\lambda_{n}(A)$

be the eigenvalues of $A$ (in non-decreasing order), and let

$\displaystyle
u_{1}(A),u_{2}(A),\dots,u_{n}(A)\in\operatorname{{\mathbb{R}}}^{n}$

be corresponding eigenvectors. For $1\leq j\leq n$, let

$\displaystyle P_{\leq j}(A)=\sum_{k=1}^{j}P_{k}(A),\qquad
P_{k}(A)=u_{k}(A)u_{k}(A)^{\top},$

be the orthogonal projection onto the eigenspace spanned by
$u_{1}(A),\dots,u_{j}(A)$. For $1\leq j\leq n$ with
$\lambda_{j+1}(A)>\lambda_{j}(A)$, let

$\displaystyle
R_{>j}(A)=\sum_{k>j}\frac{P_{k}(A)}{\lambda_{k}(A)-\lambda_{j}(A)}.$

If $A,B\in\operatorname{{\mathbb{R}}}^{n\times n}$ are symmetric, then we
define

$\displaystyle\delta_{\leq j}(B-A)$
$\displaystyle=\Big{\|}\Big{(}\frac{P_{\leq
j}(A)}{\lambda_{j+1}(A)-\lambda_{j}(A)}+R_{>j}(A)\Big{)}^{\frac{1}{2}}(B-A)\Big{(}\frac{P_{\leq
j}(A)}{\lambda_{j+1}(A)-\lambda_{j}(A)}+R_{>j}(A)\Big{)}^{\frac{1}{2}}\Big{\|}_{\infty}$

for every $1\leq j\leq n$ such that $\lambda_{j+1}(A)>\lambda_{j}(A)$.

######  Lemma 12 (Relative Davis-Kahan bound).

Let $A,B\in\operatorname{{\mathbb{R}}}^{n\times n}$ be symmetric. Then we have

$\displaystyle\|\hat{P}_{\leq j}(A)-P_{\leq j}(A)\|_{\infty}$
$\displaystyle\leq\sqrt{32j}\cdot\delta_{\leq j}(B-A).$

for every $1\leq j\leq n$ such that $\lambda_{j+1}(A)>\lambda_{j}(A)$.

###### Proof.

See again Proposition 1 in [26]. ∎

######  Lemma 13.

Let $A,B\in\operatorname{{\mathbb{R}}}^{n\times n}$ be symmetric and let
$1\leq j\leq n$ such that $\lambda_{j+1}(A)>\lambda_{j}(A)$. Then

$\displaystyle\delta_{\leq
j}(B-A)\leq\frac{\|B-A\|_{\infty}}{\lambda_{j+1}(A)-\lambda_{j}(A)}$

and, if $A$ is additionally positive definite, then also

$\displaystyle\delta_{\leq
j}(B-A)\leq\frac{\lambda_{j+1}(A)}{\lambda_{j+1}(A)-\lambda_{j}(A)}\|A^{-1/2}(B-A)A^{-1/2}\|_{\infty}.$

###### Proof.

Follows from simple properties of the operator norm. ∎

######  Corollary 5.

Let $A,B\in\operatorname{{\mathbb{R}}}^{n\times n}$ be symmetric and let
$1\leq j\leq n$ such that $\lambda_{j+1}(A)>\lambda_{j}(A)$. Then

$\displaystyle\|\hat{P}_{\leq j}(B)-P_{\leq j}(A)\|_{\infty}$
$\displaystyle\leq\sqrt{32j}\frac{\|B-A\|_{\infty}}{\lambda_{j+1}(A)-\lambda_{j}(A)}$

and, if $A$ is additionally positive definite, then also

$\displaystyle\|\hat{P}_{\leq j}(B)-P_{\leq j}(A)\|_{\infty}$
$\displaystyle\leq\sqrt{32j}\frac{\lambda_{j+1}(A)}{\lambda_{j+1}(A)-\lambda_{j}(A)}\|A^{-1/2}(B-A)A^{-1/2}\|_{\infty}.$

###### Proof.

Follows from inserting Lemma 13 into Lemma 12. ∎

######  Lemma 14.

Let $A,B\in\operatorname{{\mathbb{R}}}^{n\times n}$ be symmetric and let
$1\leq j\leq n$. Then,

$\displaystyle|\lambda_{j}(B)-\lambda_{j}(A)|$
$\displaystyle\leq\|B-A\|_{\infty}$

and, if $A$ is additionally strictly positive definite, then also

$\displaystyle|\lambda_{j}(B)-\lambda_{j}(A)|$
$\displaystyle\leq\lambda_{j}(A)\|A^{-1/2}(B-A)A^{-1/2}\|_{\infty}.$

###### Proof.

See Theorem 2.7 in [25]. ∎

###  A.2 Concentration inequalities

The following lemma states an operator Bernstein inequality (see, e.g., Lemma
5 in [17] and also [43]).

######  Lemma 15.

Let $\xi_{1},\dots,\xi_{n}$ be a sequence of independently and identically
distributed self-adjoint Hilbert-Schmidt operators on a separable Hilbert
space. Suppose that $\mathbb{E}\xi_{1}=0$ and that
$\|\xi_{1}\|_{\operatorname{op}}\leq R$ almost surely for some constant $R>0$.
Moreover, suppose that there are constants $V,D>0$ satisfying
$\|\mathbb{E}\xi_{1}^{2}\|_{\operatorname{op}}\leq V$ and
$\operatorname{tr}(\mathbb{E}\xi_{1}^{2})\leq VD$. Then, for all $u>0$,

$\displaystyle\mathbb{P}\Big{(}\Big{\|}\frac{1}{n}\sum_{i=1}^{n}\xi_{i}\Big{\|}_{\operatorname{op}}\geq
u\Big{)}\leq 4D\exp\Big{(}-\frac{nu^{2}}{2V+(2/3)uR}\Big{)}.$

The next lemma states an extension of Lemma A.1 in [24].

######  Lemma 16.

Let $(a_{k})$ be a non-increasing sequence of non-negative real numbers such
that $\|(a_{k})\|_{1}=\sum_{k=1}^{\infty}a_{k}<\infty$. Let $(Z_{ik})$ be a
sequence of real-valued centered random variables with
$k\in\operatorname{{\mathbb{N}}}$ and $1\leq i\leq n$. Suppose that
$(Z_{ik})_{i=1}^{n}$ are i.i.d. for each $k\in\operatorname{{\mathbb{N}}}$ and
that there is a constant $C_{1}>0$ such that

$\displaystyle\forall
N\in\operatorname{{\mathbb{N}}},\qquad\sum_{k=1}^{N}Z_{1k}^{2}\leq
C_{2}N\quad\text{a.s.}$

Then there is a constant $C>0$ depending only on $C_{2}$ such that, for every
$t\geq 1$, we have

$\displaystyle\sum_{k=1}^{\infty}a_{k}\Big{(}\frac{1}{n}\sum_{i=1}^{n}Z_{ik}\Big{)}^{2}\leq
C\Big{(}\|(a_{k})\|_{1}\cdot\frac{t}{n}+\|(ka_{k})\|_{1}\frac{t^{2}}{n^{2}}\Big{)}$

with probability at least $1-e^{-t}$.

###### Proof.

For $p\in\operatorname{{\mathbb{N}}}$ Minkowski’s inequality yields

$\displaystyle\Big{\|}\sum_{k=1}^{\infty}a_{k}\Big{(}\frac{1}{n}\sum_{i=1}^{n}Z_{ik}\Big{)}^{2}\Big{\|}_{L^{p}}\leq\sum_{k=1}^{\infty}a_{k}\Big{\|}\frac{1}{n}\sum_{i=1}^{n}Z_{ik}\Big{\|}_{L^{2p}}^{2}$
(A.1)

By assumption $Z_{1k}$ is centered with $|Z_{1k}|\leq\sqrt{C_{2}k}$. Hence,
Bernstein’s inequality yields

$\displaystyle\operatorname{{\mathbb{P}}}\Big{(}\frac{1}{n}\sum_{i=1}^{n}Z_{ik}\geq\sqrt{\frac{2z\operatorname{{\mathbb{E}}}Z_{1k}^{2}}{n}}+\frac{z\sqrt{C_{2}k}}{n}\Big{)}\leq
e^{-z}$

for all $z>0$ and all $k\in\operatorname{{\mathbb{N}}}$. Since the same
deviation bound holds for $-n^{-1}\sum_{i=1}^{n}Z_{ik}$, Theorem 2.3 in [8]
yields

$\displaystyle\forall
p\in\operatorname{{\mathbb{N}}},\qquad\Big{\|}\frac{1}{n}\sum_{i=1}^{n}Z_{ik}\Big{\|}_{L^{2p}}^{2}$
$\displaystyle\leq\Big{(}p!\Big{(}\frac{8\operatorname{{\mathbb{E}}}Z_{1k}^{2}}{n}\Big{)}^{p}+(2p)!\Big{(}\frac{4\sqrt{C_{2}k}}{n}\Big{)}^{2p}\Big{)}^{1/p}$
$\displaystyle\leq
C\Big{(}\frac{p}{n}\operatorname{{\mathbb{E}}}Z_{1k}^{2}+\frac{p^{2}}{n^{2}}k\Big{)}.$

Inserting this into (A.1), we get

$\displaystyle\forall
p\in\operatorname{{\mathbb{N}}},\qquad\Big{\|}\sum_{k=1}^{\infty}a_{k}\Big{(}\frac{1}{n}\sum_{i=1}^{n}Z_{ik}\Big{)}^{2}\Big{\|}_{L^{p}}\leq
C\Big{(}\frac{p}{n}\operatorname{{\mathbb{E}}}\sum_{k=1}^{\infty}a_{k}Z_{1k}^{2}+\frac{p^{2}}{n^{2}}\sum_{k=1}^{\infty}ka_{k}\Big{)}.$

Set $B_{k}=\sum_{l=1}^{k}Z_{1l}^{2}$. Then $B_{k}\leq Ck$ for all
$k\in\operatorname{{\mathbb{N}}}$ by assumption. Hence, for all
$N\in\operatorname{{\mathbb{N}}}$, we have

$\displaystyle\sum_{k=1}^{N}a_{k}Z_{1k}^{2}$
$\displaystyle=\sum_{k=1}^{N}a_{k}(B_{k}-B_{k-1})$
$\displaystyle=a_{N}B_{N}-a_{1}B_{0}+\sum_{k=1}^{N-1}(a_{k}-a_{k-1})B_{k}$
$\displaystyle\leq
C\Big{(}a_{N}N+\sum_{k=1}^{N-1}(a_{k}-a_{k-1})k\Big{)}=C\sum_{k=1}^{N}a_{k}$

almost surely. Letting $N\rightarrow\infty$, this implies

$\displaystyle\sum_{k=1}^{\infty}a_{k}Z_{1k}^{2}\leq C\|(a_{k})\|_{1}$

almost surely. We arrive at

$\displaystyle\forall
p\in\operatorname{{\mathbb{N}}},\qquad\Big{\|}\sum_{k=1}^{\infty}a_{k}\Big{(}\frac{1}{n}\sum_{i=1}^{n}Z_{ik}\Big{)}^{2}\Big{\|}_{L^{p}}\leq
C\Big{(}\frac{p}{n}\|(a_{k})\|_{1}+\frac{p^{2}}{n^{2}}\|(ka_{k})\|_{1}\Big{)}.$

The claim now follows from an application of Markov’s inequality with an
appropriate choice of $p$ (see, e.g., Equation (3.2) in [20]). ∎

###  A.3 Eigenvalue estimates

######  Lemma 17.

Let $(\mu_{j})_{j=m+1}^{\infty}$ be a sequence of real numbers such that
$\mu_{j}\geq cj^{2/d}$ for all $j>m$ and some constants $d\geq 3$ and $c>0$.
Then there is an absolute constant $C>0$ depending only on $c$ and $d$ such
that

$\displaystyle\sum_{j>m}\frac{e^{-\mu_{j}t}}{1-e^{-\mu_{j}t}}\leq Ct^{-d/2},$
$\displaystyle\sum_{j>m}\frac{e^{-\mu_{j}t}}{(1-e^{-\mu_{j}t})^{2}}\leq
Ct^{-d/2},$
$\displaystyle\sum_{j>m}\frac{je^{-\mu_{j}t}}{(1-e^{-\mu_{j}t})^{2}}\leq
Ct^{-d}$

for all $t\in(0,1]$. In the last inequality, we additionally assume that
$d\geq 5$.

###### Proof.

Since $x\mapsto x/(1-x)$ is increasing for $x\in(0,1]$, we have

$\displaystyle\sum_{j>m}\frac{e^{-\mu_{j}t}}{1-e^{-\mu_{j}t}}$
$\displaystyle\leq\sum_{j>m}\frac{e^{-cj^{2/d}t}}{1-e^{-cj^{2/d}t}}$
$\displaystyle\leq\sum_{j=m+1}^{M}\frac{1}{e^{cj^{2/d}t}-1}+\sum_{j=M+1}^{\infty}\frac{e^{-cj^{2/d}t}}{1-e^{-cj^{2/d}t}}$

for $M>m$. Choose $M=\max\\{j>m:cj^{2/d}t\leq 1\\}$ and $M=m$ if the latter
set is empty. Then

$\displaystyle\sum_{j=m+1}^{M}\frac{1}{e^{cj^{2/d}t}-1}$
$\displaystyle\leq\sum_{j=m+1}^{M}\frac{1}{cj^{2/d}t}$
$\displaystyle\leq\frac{C}{t}\int_{m}^{M}\frac{1}{x^{2/d}}\,dx$
$\displaystyle\leq Ct^{-1}M^{1-d/2}\leq Ct^{-1}(t^{-d/2})^{1-d/2}=Ct^{-d/2}$

and

$\displaystyle\sum_{j=M+1}^{\infty}\frac{e^{-cj^{2/d}t}}{1-e^{-cj^{2/d}t}}$
$\displaystyle\leq\frac{1}{(1-e^{-1})}\sum_{j=M+1}^{\infty}e^{-cx^{2/d}t},$
$\displaystyle\leq\frac{1}{1-e^{-1}}\int_{M}^{\infty}e^{-cx^{2/d}t}\,dx$
$\displaystyle=\frac{1}{1-e^{-1}}t^{-d/2}\int_{Mt^{d/2}}^{\infty}e^{-cx^{2/d}}\,dx\leq
Ct^{-d/2}.$

The other bounds follow similarly. ∎

## References

  * [1] F. Bach.  Information theory with kernel methods.  IEEE Trans. Inform. Theory, 69(2):752–775, 2023.
  * [2] A. S. Bandeira, A. Singer, and T. Strohmer.  Mathematics of data science.  Book in preparation.
  * [3] M. Belkin and P. Niyogi.  Laplacian eigenmaps for dimensionality reduction and data representation.  Neural Computation, 15(6):1373–1396, 2003.
  * [4] M. Belkin and P. Niyogi.  Convergence of laplacian eigenmaps.  In Neural Information Processing Systems, 2006.
  * [5] M. Belkin and P. Niyogi.  Towards a theoretical foundation for Laplacian-based manifold methods.  J. Comput. System Sci., 74(8):1289–1308, 2008.
  * [6] R. Bhatia.  Matrix analysis.  Springer-Verlag, New York, 1997.
  * [7] G. Blanchard and J.-B. Fermanian.  Nonasymptotic one- and two-sample tests in high dimension with unknown covariance structure.  In Foundations of modern statistics, volume 425 of Springer Proc. Math. Stat., pages 121–162. Springer, Cham, [2023] ©2023.
  * [8] S. Boucheron, G. Lugosi, and P. Massart.  Concentration inequalities: a nonasymptotic theory of independence.  Oxford University Press, Oxford, 2013.
  * [9] D. Burago, S. Ivanov, and Y. Kurylev.  A graph discretization of the Laplace-Beltrami operator.  J. Spectr. Theory, 4(4):675–714, 2014.
  * [10] J. Calder and N. García Trillos.  Improved spectral convergence rates for graph Laplacians on $\varepsilon$-graphs and $k$-NN graphs.  Appl. Comput. Harmon. Anal., 60:123–175, 2022.
  * [11] F. Chatelin.  Spectral approximation of linear operators.  Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2011.
  * [12] I. Chavel.  Eigenvalues in Riemannian geometry.  Academic Press, Inc., Orlando, FL, 1984.
  * [13] X. Cheng and N. Wu.  Eigen-convergence of Gaussian kernelized graph Laplacian by manifold heat interpolation.  Appl. Comput. Harmon. Anal., 61:132–190, 2022.
  * [14] F. R. K. Chung.  Spectral graph theory.  Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 1997.
  * [15] R. R. Coifman and S. Lafon.  Diffusion maps.  Appl. Comput. Harmon. Anal., 21(1):5–30, 2006.
  * [16] E. B. Davies.  Heat kernels and spectral theory.  Cambridge University Press, Cambridge, 1990.
  * [17] L. H. Dicker, D. P. Foster, and D. Hsu.  Kernel ridge vs. principal component regression: minimax bounds and the qualification of regularization operators.  Electron. J. Stat., 11(1):1022–1047, 2017.
  * [18] N. García Trillos, M. Gerlach, M. Hein, and D. Slepčev.  Error estimates for spectral convergence of the graph Laplacian on random geometric graphs toward the Laplace-Beltrami operator.  Found. Comput. Math., 20(4):827–887, 2020.
  * [19] E. Giné and V. Koltchinskii.  Empirical graph Laplacian approximation of Laplace-Beltrami operators: large sample results.  In High dimensional probability, volume 51 of IMS Lecture Notes Monogr. Ser., pages 238–259. Inst. Math. Statist., Beachwood, OH, 2006.
  * [20] E. Giné, R. Latał a, and J. Zinn.  Exponential and moment inequalities for $U$-statistics.  In High dimensional probability, II (Seattle, WA, 1999), volume 47 of Progr. Probab., pages 13–38. Birkhäuser Boston, Boston, MA, 2000.
  * [21] A. Grigor’yan.  Heat kernel and analysis on manifolds.  American Mathematical Society, Providence, RI; International Press, Boston, MA, 2009.
  * [22] A. Grigor’yan.  Estimates of heat kernels on Riemannian manifolds, page 140–225.  London Mathematical Society Lecture Note Series. Cambridge University Press, 1999.
  * [23] T. Hsing and R. Eubank.  Theoretical foundations of functional data analysis, with an introduction to linear operators.  John Wiley & Sons, Ltd., Chichester, 2015.
  * [24] Laura Hucker and Martin Wahl.  A note on the prediction error of principal component regression in high dimensions.  Theory Probab. Math. Statist., 109:37–53, 2023.
  * [25] I. C. F. Ipsen.  Relative perturbation results for matrix eigenvalues and singular values.  In Acta numerica, 1998, volume 7 of Acta Numer., pages 151–201. Cambridge Univ. Press, Cambridge, 1998.
  * [26] M. Jirak and M. Wahl.  Quantitative limit theorems and bootstrap for empirical spectral projectors.  Available at https://arxiv.org/abs/2208.12871.
  * [27] M. Jirak and M. Wahl.  Perturbation bounds for eigenspaces under a relative gap condition.  Proc. Amer. Math. Soc., 148(2):479–494, 2020.
  * [28] M. Jirak and M. Wahl.  Relative perturbation bounds with applications to empirical covariance operators.  Adv. Math., 412:Paper No. 108808, 59 pp, 2023.
  * [29] I. M. Johnstone and D. Paul.  PCA in high dimensions: An orientation.  Proceedings of the IEEE, 106(8):1277–1292, 2018.
  * [30] I. Koch.  Analysis of multivariate and high-dimensional data.  Cambridge University Press, New York, 2014.
  * [31] V. Koltchinskii and E. Giné.  Random matrix approximation of spectra of integral operators.  Bernoulli, 6(1):113–167, 2000.
  * [32] V. Koltchinskii, M. Löffler, and R. Nickl.  Efficient estimation of linear functionals of principal components.  Ann. Statist., 48(1):464–490, 2020.
  * [33] V. Koltchinskii and K. Lounici.  Concentration inequalities and moment bounds for sample covariance operators.  Bernoulli, 23(1):110–133, 2017.
  * [34] S. Minakshisundaram and Å. Pleijel.  Some properties of the eigenfunctions of the Laplace-operator on Riemannian manifolds.  Canad. J. Math., 1:242–256, 1949.
  * [35] M. Reiss and M. Wahl.  Nonasymptotic upper bounds for the reconstruction error of PCA.  Ann. Statist., 48(2):1098–1123, 2020.
  * [36] J. W. Robbin and D. A. Salamon.  Introduction to differential geometry.  Springer Spektrum, Wiesbaden, 2022.
  * [37] L. Rosasco, M. Belkin, and E. De Vito.  On learning with integral operators.  J. Mach. Learn. Res., 11:905–934, 2010.
  * [38] S. Rosenberg.  The Laplacian on a Riemannian manifold.  Cambridge University Press, Cambridge, 1997.
  * [39] B. Schölkopf, A. Smola, and K.-R. Müller.  Nonlinear component analysis as a kernel eigenvalue problem.  Neural Computation, 10(5):1299–1319, 1998.
  * [40] Z. Shi.  Convergence of laplacian spectra from random samples.  Available at https://arxiv.org/abs/1507.00151.
  * [41] A. Singer.  From graph to manifold Laplacian: the convergence rate.  Appl. Comput. Harmon. Anal., 21(1):128–134, 2006.
  * [42] I. Steinwart and A. Christmann.  Support vector machines.  Springer, New York, 2008.
  * [43] J. A. Tropp.  An Introduction to Matrix Concentration Inequalities.  2015\.
  * [44] U. von Luxburg.  A tutorial on spectral clustering.  Stat. Comput., 17(4):395–416, 2007.
  * [45] U. von Luxburg, M. Belkin, and O. Bousquet.  Consistency of spectral clustering.  Ann. Statist., 36(2):555–586, 2008.
  * [46] V. Q. Vu and J. Lei.  Minimax sparse principal subspace estimation in high dimensions.  Ann. Statist., 41(6):2905–2947, 2013.
  * [47] M. Wahl.  On the perturbation series for eigenvalues and eigenprojections.  Available at https://arxiv.org/abs/1910.08460.
  * [48] M. J. Wainwright.  High-dimensional statistics.  Cambridge University Press, Cambridge, 2019.