into a low-dimensional Euclidean space. More precisely, the low-lying spectrum of the graph Laplacian induces an embedding $F_n : \left\{{\mathbf{x}}_1, \dots, {\mathbf{x}}_n \right\} \rightarrow {\mathbb{R}}^N$ mapping a data point ${\mathbf{x}}_i$ into a vector $F_n({\mathbf{x}}_i)$ in ${\mathbb{R}}^N$ whose entries are the first $N$ eigenfunctions of the graph Laplacian evaluated at ${\mathbf{x}}_i$. Here we refer to the map $F_n$ as the [*Laplacian embedding*]{}. After the embedding step, an algorithm such as $k$-means is typically used to identify the meaningful clusters (see [@vonLux_tutorial]). While $k$-means is a standard choice in the literature, in the rest of the paper we are agnostic to the algorithm used to cluster the embedded data set. We refer the reader to section \[sec:Literature\] and in particular to [@LingStromer] for alternatives to $k$-means.

How can one motivate the use of the previous spectral clustering algorithm? Consider the simple scenario where the manifold ${\mathcal{M}}$ has $N$ connected components. Then, given data points uniformly distributed on ${\mathcal{M}}$ one can construct the proximity graph $G$ (at least for $n$ large enough) in such a way that the associated graph Laplacian also has $N$ connected components and its first $N$ eigenvectors coincide with rescaled versions of the indicator functions of the $N$ connected 