Research map / Learning theory and algorithms / Sample complexity

The Noisy Laplacian: a Threshold Phenomenon for Non-Linear Dimension Reduction

ICML 2025 · Learning theory and algorithms › Sample complexity · approach: Sample complexity of learning distributions

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows theoretically and empirically that low-frequency Laplacian eigenpairs (Diffusion Maps) of noisy tubular manifold data stay close to the noiseless manifold's eigenpairs under constant noise, up to a dimension-independent threshold of order r^-2, and observes similar robustness for LTSA and VAE.

Problem

Existing consistency results for spectral nonlinear dimension reduction (e.g., Diffusion Maps) under noise require the noise amplitude or ambient dimension to vary with sample size; the paper asks why these methods remain effective with fixed noise amplitude and dimension.

Approach

Decomposes the Laplacian on a noisy tubular neighborhood in the Sasaki metric into horizontal (manifold) and vertical (normal) operators, showing the eigenpairs below λ1^V/r^2 equal those of the noiseless manifold up to O(r) error, giving a sharp threshold independent of ambient dimension.

Key results

• Low-frequency eigenpairs of the noisy Laplacian approximate noiseless manifold eigenpairs with error linear in noise radius r (|λk(∆M)-λk(∆)| ≤ 8λk C r), with threshold λ1^V/r^2 independent of ambient dimension.
• Empirical eigenvector correlations with the noiseless manifold drop sharply for eigenvectors above the noise threshold λ1^V/r^2, independent of sample size.
• VAE and LTSA embeddings show the same behavior: low-frequency coordinates are stable across noise radius and noise dimension, while high-frequency coordinates encode noise.

Measured effects reported in the paper

Surprising findings

• Increasing noise dimension tends to slightly decrease the error of low-frequency eigenpairs, rather than harming recovery.
• Diffusion Maps spectral estimates are robust to noise even though existing consistency results assumed noise shrinking with n or growing dimension.

Limitations

• Theory assumes tubular, orthogonally uniform, independent-of-x noise with compact support within the reach; results do not directly cover non-tubular or position-dependent noise.
• Results are in the population (continuum) setting; no matching lower bound is provided, so optimality of the O(r) bias is conjectured.
• Recovery of eigenpairs above the O(r^-2) threshold is not established.

Experimental setup

Datasets: S^1 circle S^2 sphere S-Shape Bottle (synthetic) Toluene MDS Malonaldehyde MDS Ethanol MDS

Benchmarks: synthetic manifolds (S^2, S-Shape, Bottle) MDS molecular datasets (Toluene, Malonaldehyde, Ethanol)

Metrics: projector error between eigenspaces eigenvector correlations eigenvalue stability vs noise threshold polynomial regression predictability of eigenvectors from no

Baselines: Diffusion Maps LTSA VAE

Builds on: Diffusion Maps Laplacian Eigenmaps Sasaki metric LTSA

Closest papers by meaning

• Fast, Accurate Manifold Denoising by Tunneling Riemannian Optimization (ICML 2025 · similarity 0.88)
• Diffusion Models Encode the Intrinsic Dimension of Data Manifolds (ICML 2024 · similarity 0.87)
• Improving the Euclidean Diffusion Generation of Manifold Data by Mitigating Score Function Singularity (NeurIPS 2025 · similarity 0.87)
• The Geometry of Noise: Why Diffusion Models Don't Need Noise Conditioning (NeurIPS 2026 · similarity 0.87)
• Adapting to Unknown Low-Dimensional Structures in Score-Based Diffusion Models (NeurIPS 2024 · similarity 0.86)
• Nonlinear Laplacians: Tunable principal component analysis under directional prior information (NeurIPS 2025 · similarity 0.86)