# Laplacian Eigenmaps from Sparse, Noisy Similarity Measurements

arXiv: https://arxiv.org/abs/1603.03972 · HTML: https://mlsanity.com/paper/1603.03972/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Mar 2016.

## Built on by (most cited first, 3 of 3)

- [Detection of Model-based Planted Pseudo-cliques in Random Dot Product Graphs by the Adjacency Spectral Embedding and the Graph Encoder Embedding](https://mlsanity.com/paper/2312.11054/) (2023)
- [Multi-view Sparse Laplacian Eigenmaps for nonlinear Spectral Feature Selection](https://mlsanity.com/paper/2307.15905/) (2023)
- [Uncertainty-aware t-distributed Stochastic Neighbor Embedding for Single-cell RNA-seq Data](https://mlsanity.com/paper/2410.00473/) (2024)

## Abstract (arXiv)

Manifold learning and dimensionality reduction techniques are ubiquitous in science and engineering, but can be computationally expensive procedures when applied to large data sets or when similarities are expensive to compute. To date, little work has been done to investigate the tradeoff between computational resources and the quality of learned representations. We present both theoretical and experimental explorations of this question. In particular, we consider Laplacian eigenmaps embeddings based on a kernel matrix, and explore how the embeddings behave when this kernel matrix is corrupted by occlusion and noise. Our main theoretical result shows that under modest noise and occlusion assumptions, we can (with high probability) recover a good approximation to the Laplacian eigenmaps embedding based on the uncorrupted kernel matrix. Our results also show how regularization can aid this approximation. Experimentally, we explore the effects of noise and occlusion on Laplacian eigenmaps embeddings of two real-world data sets, one from speech processing and one from neuroscience, as well as a synthetic data set.