Scalability and robustness of spectral embedding: landmark diffusion is all you need

Understand

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.