  While spectral embedding is a widely applied dimension reduction technique in
various fields, so far it is still challenging to make it scalable to handle
``big data''. On the other hand, the robustness property is less explored and
there exists only limited theoretical results. Motivated by the need of
handling such data, recently we proposed a novel spectral embedding algorithm,
which we coined Robust and Scalable Embedding via Landmark Diffusion
(ROSELAND). In short, we measure the affinity between two points via a set of
landmarks, which is composed of a small number of points, and ``diffuse'' on
the dataset via the landmark set to achieve a spectral embedding. Roseland can
be viewed as a generalization of the commonly applied spectral embedding
algorithm, the diffusion map (DM), in the sense that it shares various
properties of DM. In this paper, we show that Roseland is not only numerically
scalable, but also preserves the geometric properties via its diffusion nature
under the manifold setup; that is, we theoretically explore the asymptotic
behavior of Roseland under the manifold setup, including handling the
U-statistics-like quantities, and provide a $L^\infty$ spectral convergence
with a rate. Moreover, we offer a high dimensional noise analysis and show that
Roseland is robust to noise. We also compare Roseland with other existing
algorithms with numerical simulations.
