Search research articles

ABOUT JoVE

Overview Leadership Blog JoVE Help Center

AUTHORS

Publishing Process Editorial Board Scope & Policies Peer Review FAQ Submit

LIBRARIANS

Testimonials Subscriptions Access Resources Library Advisory Board FAQ

RESEARCH

JoVE Journal Methods Collections JoVE Encyclopedia of Experiments Archive

EDUCATION

JoVE Core JoVE Business JoVE Science Education JoVE Lab Manual Faculty Resource Center Faculty Site

Terms & Conditions of Use

Search research articles

Related Experiment Videos

Diffusion maps and coarse-graining: A unified framework for dimensionality reduction, graph partitioning, and data

Stéphane Lafon¹, Ann B Lee

¹Google Inc., 1600 Amphitheater Parkway, Mountain View, CA 94043, USA. stephane.lafon@gmail.com

IEEE Transactions on Pattern Analysis and Machine Intelligence

|August 26, 2006

Summary

This summary is machine-generated.

This study unifies nonlinear dimensionality reduction, clustering, and data parameterization using a novel framework based on Markov random walks. This approach robustly handles high-dimensional data and provides a rigorous justification for clustering algorithms like k-means.

Related Experiment Videos

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by

Same author

The Performance of Critical Congenital Heart Disease Screening in Rural Versus Urban Locations in the Northwest United States.

Journal of pediatrics. Clinical practice·2024

Same author

Prevalence, risk factors, and surveillance patterns for gastric intestinal metaplasia among patients undergoing upper endoscopy with biopsy.

Gastrointestinal endoscopy·2019

Same author

Most genetic risk for autism resides with common variation.

Nature genetics·2014

Same author

REFINING GENETICALLY INFERRED RELATIONSHIPS USING TREELET COVARIANCE SMOOTHING.

The annals of applied statistics·2014

Same author

An optimal transportation approach for nuclear structure-based pathology.

IEEE transactions on medical imaging·2010

Same author

A SPECTRAL GRAPH APPROACH TO DISCOVERING GENETIC ANCESTRY.

The annals of applied statistics·2010

Same journal

HardFlow: Hard-Constrained Sampling for Flow-Matching Models Via Trajectory Optimization.

IEEE transactions on pattern analysis and machine intelligence·2026

Same journal

Industrial Brain: Self-Evolving Neuro-Symbolic Autonomy with Causal Resilience for Cyber-Physical Systems.

IEEE transactions on pattern analysis and machine intelligence·2026

Same journal

Adaptive Hardness-Driven Dictionary Distillation for Incomplete Streaming View Clustering.

IEEE transactions on pattern analysis and machine intelligence·2026

Same journal

Mixture of Global and Local Experts with Diffusion Transformer for Controllable Face Generation.

IEEE transactions on pattern analysis and machine intelligence·2026

Same journal

Task-KV: Task-aware KV Cache Optimization via Semantic Differentiation of Attention Heads.

IEEE transactions on pattern analysis and machine intelligence·2026

Same journal

Achieving Text-based Person Retrieval with Any Granularity.

IEEE transactions on pattern analysis and machine intelligence·2026

See all related articles

Area of Science:

Data Science
Machine Learning
Computational Geometry

Background:

Dimensionality reduction, clustering, and parameterization are key data analysis tasks.
Existing methods often treat these problems separately.
A unified framework could enhance efficiency and theoretical understanding.

Purpose of the Study:

To develop a single framework for nonlinear dimensionality reduction, clustering, and data set parameterization.
To introduce a robust coordinate system reflecting data connectivity and noise resilience.
To provide a rigorous theoretical basis for clustering algorithms.

Main Methods:

Utilizing a Markov random walk on the data to define intrinsic geometry and connectivity.
Developing a coordinate system with an explicit metric robust to noise.
Demonstrating equivalence between clustering in embedding spaces and operator compression.

Main Results:

A general scheme for reorganizing and subsampling graphs and high-dimensional data sets.
Clustering is shown to be equivalent to compressing operators.
Quantization distortion in diffusion space bounds operator compression error.

Conclusions:

The proposed framework unifies distinct data analysis tasks.
Provides rigorous justification for k-means clustering in diffusion space.
Offers a precise measure for evaluating general clustering algorithm performance.