nucleation

THEORY-728: On a finite data set, a symmetric positive affinity normalized to a Markov operator is conjugate to a symmetric one, and its eigenvectors scaled by powers of their eigenvalues embed the data so that Euclidean distance equals the diffusion distance weighted by the inverse stationary law

3 min read

Properties5
StatusActive
Version2
Tagsmathematics, representation-learning
SourceLIT-981 — Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion maps
Extended byTHEORY-565 — From a symmetric, positivity-preserving, positive semi-definite affinity, the normalized Markov operator is conjugate to a symmetric one, so its leading eigenfunctions scaled by powers of their eigenvalues embed the data with Euclidean distance equal to diffusion distance, and a density-corrected normalization recovers the Laplace–Beltrami operator independently of how the data were sampled

Graph View

Source

Coifman, Lafon, Lee, Maggioni, Nadler, Warner & Zucker (2005), “Diffusion maps”, PNAS 102(21), LIT-981, read in full in NOTE-1441 (2026-10-30), which replaces the skim of NOTE-784. The paper states the construction and the embedding and calls them standard. Its own diffusion distance is the one its symmetric kernel ã^(m) induces, with the eigenfunctions of ã as coordinates. The definitions below are the companion’s (LIT-1246), in particular the 1/π weighting of the diffusion distance, and the derivation is the record’s.

What was actually shown

Take n points and a symmetric matrix K = (k(x, y)) with positive entries. Let d(x) = Σ_y k(x, y), D = diag(d), vol = Σ_x d(x) and π = d/vol.

  • A Markov operator with stationary law π. A = D⁻¹K has rows summing to
    1. πA = 1ᵀK/vol = dᵀ/vol = π, by the symmetry of K.
  • Conjugate to a symmetric matrix. à = D^(1/2) A D^(-1/2) = D^(-1/2) K D^(-1/2) is symmetric, so à = Σ_j λ_j v_j v_jᵀ with orthonormal v_j and real λ_j. A is stochastic, so |λ_j| ≤ 1, and λ₀ = 1 with v₀ = √d/√vol. If K is positive semi-definite, so is Ã, being a congruence of K, and every λ_j ≥ 0.
  • Spectral form of the walk. Put ψ_j = √vol · D^(-1/2) v_j and φ_j = D^(1/2) v_j / √vol. Then A^m = Σ_j λ_j^m ψ_j φ_jᵀ, ψ₀ ≡ 1, and Σ_y φ_i(y) φ_j(y) / π(y) = v_iᵀ v_j = δ_ij.
  • The isometry. Define the diffusion distance D_m(x, z)² = Σ_y (A^m(x, y) − A^m(z, y))² / π(y). Substituting the spectral form, A^m(x, ·) − A^m(z, ·) = Σ_j λ_j^m (ψ_j(x) − ψ_j(z)) φ_j, and the φ_j are orthonormal in the 1/π-weighted inner product, so D_m(x, z)² = Σ_j λ_j^(2m) (ψ_j(x) − ψ_j(z))². The j = 0 term vanishes because ψ₀ is constant. So x ↦ (λ_j^m ψ_j(x))_{j≥1} is an isometry from the diffusion distance to Euclidean distance, for every m.
  • Truncation. Keeping only the first few coordinates drops nonnegative summands. The truncated distance is a lower bound, short by exactly the dropped terms, which are small once λ_j^(2m) is. That is the approximate isometry the paper states.

Without the symmetry of K there is no symmetric conjugate, no real orthonormal eigenbasis, and the identity fails. The positive semi-definite hypothesis is used only for λ_j ≥ 0. Without it the eigenvalues lie in [−1, 1], and the coordinates λ_j^m ψ_j are signed, but the isometry still holds.

What this does not say

  • Anything about the continuum. The α-family and the convergence of the α = 1 normalization to the Laplace–Beltrami operator are THEORY-565’s, Proposed until the companion paper’s proofs are read.
  • That the weighting is the paper’s. The 1/π weighting is the companion’s definition (LIT-1246). The paper’s own distance, seen in NOTE-1441, is induced by ã^(m) and has its own isometry in the unrescaled coordinates. Without the weighting this identity does not hold.
  • How many coordinates to keep. That is set by a precision threshold, not by any task.
  • Anything for non-symmetric kernels. A non-reversible walk has no symmetric conjugate.

Backlinks