  In this paper, we study the convergence of the spectral embeddings obtained
from the leading eigenvectors of certain similarity matrices to their
population counterparts. We opt to study this convergence in a uniform (instead
of average) sense and highlight the benefits of this choice. Using the
Newton-Kantorovich Theorem and other tools from functional analysis, we first
establish a general perturbation result for orthonormal bases of invariant
subspaces. We then apply this general result to normalized spectral clustering.
By tapping into the rich literature of Sobolev spaces and exploiting some
concentration results in Hilbert spaces, we are able to prove a finite sample
error bound on the uniform consistency error of the spectral embeddings in
normalized spectral clustering.
