How well behaved is finite dimensional Diffusion Maps embedding?

Diffusion Maps (DM) is a well studied and popular non-linear dimension reduction algorithm. Surprisingly, while the convergence properties of DM are well understood, the \em geometric properties of the embedding, such as reach and smoothness have not yet been studied. Under a set of standard assumptions on a family of submanifolds $\subset {\mathbb{R}}^D$, we derive a series of geometric properties that are preserved by DM, including almost uniform density, finite polynomial approximation and reach. Leveraging these properties, we establish rigorous bounds on the embedding errors introduced by the DM algorithm, of the order $(\frac{\log n}{n}{)}^{\frac{1}{8d+16}}$. These results offer a solid theoretical foundation for understanding the performance and reliability of DM in practical applications.