Minimax Rates and Improved Spectral Convergence for Multi-Manifold Clustering

Haoyu Chen; Chenghui Li

stat.MLOct 11, 2026

Minimax Rates and Improved Spectral Convergence for Multi-Manifold Clustering

Authors: Haoyu Chen, Chenghui Li

Organizations: Department of Statistics University of Wisconsin Madison Madison, WI 53706, USA

Abstract

We study eigenpair estimation for the tensorized, density-weighted Laplace--Beltrami operator from $n$ independent data points sampled from a multi-manifold mixture distribution where manifolds may intersect. Let $d$ denote the largest intrinsic dimension of the manifold components and $s\geq2$ the smoothness of the sampling densities. For simple, nontrivial eigenpairs, we establish the minimax rate $n^{-s/(d+2s)}$ for approximating the eigenvalue and eigenfunction of the tensorized Laplace--Beltrami operator, and show that a continuum plug-in estimator based on kernel density estimation attains the same rate when the supporting manifolds are known. We further analyze a manifold-agnostic graph Laplacian estimator and prove that its eigenpairs converge to those of the tensorized Laplace--Beltrami operator at rate $n^{-1/(2.5d-1)}$ , up to logarithmic factors, improving upon previously known spectral convergence rates for multi-manifold learning. Numerical experiments on synthetic multi-manifold data corroborate the rates guaranteed by our theorems. These results characterize the information-theoretic difficulty of multi-manifold spectral estimation and quantify the additional cost of learning without oracle component information.

Figures & tables

$r$	$\varphi_{r}$	$a_{1r}$	$a_{2r}$	$\bm{k}_{1r}^{(2)}$	$\bm{k}_{2r}^{(2)}$	$\bm{k}_{1r}^{(3)}$	$\bm{k}_{2r}^{(3)}$
1	$\cos$	0.19429357	0.21530560	$(2,0)$	$(2,0)$	$(2,0,0)$	$(2,0,0)$
2	$\cos$	0.07146951	0.16111551	$(0,2)$	$(0,2)$	$(0,2,0)$	$(0,2,0)$
3	$\cos$	0.035	0.040	$(1,1)$	$(1,-1)$	$(1,1,0)$	$(1,-1,0)$
4	$\sin$	0.025	0.020	$(2,1)$	$(1,2)$	$(2,1,0)$	$(1,2,0)$
5	$\cos$	0.11797347	0.07914921	$(4,0)$	$(4,0)$	$(0,0,2)$	$(0,0,2)$
6	$\cos$	0.05728538	0.10603882	$(0,4)$	$(0,4)$	$(0,4,0)$	$(0,4,0)$

Table 1: Density amplitudes and frequencies used in the numerical experiments. Coefficients are displayed to eight decimal places; the computations use their unrounded values.

Figure 1: The nonuniform sampling densities $\rho_{j}^{(d)}$ on the unit-volume flat tori for $d\in\{1,2,3\}$ and $j\in\{1,2\}$ . Each column displays the densities for the two components at dimension $d$ .

Panel of Figure 2 — Figure 2: Oracle KDE spectral convergence rate for $d\in\{1,2,3\}$ .

Panel of Figure 3 — Figure 3: Realistic spectral convergence rate for $d\in\{1,2,3\}$ .

$d$	$C_{\epsilon}$	$\beta$	$c_{\epsilon}$	$C_{r}$	$p$	$\alpha$
1	0.028	$1/3$	0.6	0.50	3	3.5 $\epsilon_{+}$
2	0.11	$1/8$	0.78	0.60	3	3.5 $\epsilon_{+}$
3	0.18	$1/13$	0.8	0.72	3	3.8 $\epsilon_{+}$

Table 2: Parameters used in the PBC experiments.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Case	$\operatorname{dist}(x,\mathcal{M}_{k})$	$\operatorname{dist}(y,\mathcal{M}_{j})$	$\mathsf{N}_{jk}(\alpha)$	$\sup_{x}\mathsf{D}_{jk}(x;\beta)$	$\mathfrak{C}_{jk}^{(2)}(\alpha,\beta)$
(1)	$(r,\epsilon_{+}]$	$(0,q]$	$C_{jk}n\epsilon_{+}^{c_{jk}}$	$C_{jk}n\epsilon_{+}^{d+3}$	$C_{jk}n^{3}\epsilon_{+}^{2d+c+6}\leq C_{jk}n^{3}\epsilon_{+}^{2d+7}$
(2)	$(q,r]$	$(0,r]$	$C_{jk}n\epsilon_{+}^{c_{jk}+2}$	$C_{jk}n\epsilon_{+}^{d+2}$	$C_{jk}n^{3}\epsilon_{+}^{2d+c+6}\leq C_{jk}n^{3}\epsilon_{+}^{2d+7}$
(3)	$(0,q]$	$(0,\epsilon_{+}]$	$C_{jk}n\epsilon_{+}^{c_{jk}+3}$	$C_{jk}n\epsilon_{+}^{d}$	$C_{jk}n^{3}\epsilon_{+}^{2d+c_{jk}+3}\leq C_{jk}n^{3}\epsilon_{+}^{2d+4}$

Appendix

Table 3: Global squared-neighbor counts for an ordered pair

(j,k)

. The last column counts

j

-endpoints weighted by the square of their admissible

k

-neighbor counts.

Case	$\operatorname{dist}(x,\mathcal{M}_{k})$	$\operatorname{dist}(y,\mathcal{M}_{j})$	$\mathsf{N}_{jk,Q}(\alpha)$	$\sup_{x}\mathsf{D}_{jk}(x;\beta)$	$\mathfrak{C}_{jk,Q}^{(1)}(\alpha,\beta)$
(1)	$(r,\epsilon_{+}]$	$(0,q]$	$C_{jk}ns^{d-c_{jk}}\epsilon_{+}^{c_{jk}}$	$C_{jk}n\epsilon_{+}^{d+3}$	$C_{jk}n^{2}s^{d-{c_{jk}}}\epsilon_{+}^{d+{c_{jk}}+3}$
(2)	$(q,r]$	$(0,r]$	$C_{jk}ns^{d-{c_{jk}}}\epsilon_{+}^{{c_{jk}}+2}$	$C_{jk}n\epsilon_{+}^{d+2}$	$C_{jk}n^{2}s^{d-{c_{jk}}}\epsilon_{+}^{d+{c_{jk}}+4}$
(3)	$(0,q]$	$(0,\epsilon_{+}]$	$C_{jk}ns^{d-{c_{jk}}}\epsilon_{+}^{{c_{jk}}+3}$	$C_{jk}n\epsilon_{+}^{d}$	$C_{jk}n^{2}s^{d-{c_{jk}}}\epsilon_{+}^{d+{c_{jk}}+3}$

Appendix

Table 4: Cellwise ordinary connection counts for an ordered pair

(j,k)

. The last column counts ordered retained edges

(x,y)

with

x\in Q

Manifold Learning

Manifold learning finds low-dimensional structure in complex data to support visualization, geometric analysis, and more efficient learning.

See all 117 papers

Complex Interpolation of Matrices with an application to Multi-Manifold Learning
Apr 15, 2026Adi Arbel, Stefan Steinerberger, Ronen TalmonMulti-View Learning Manifold Learning
Viterbi Faculty of Electrical and Computer Engineering, Technion – Israel Institute of Technology, Haifa, Israel · Department of Mathematics and Department of Applied Mathematics, University of Washington, Seattle, WA 98195, USA
Learning manifold diffusion semigroups from graph transition matrices
May 25, 2026Xiuyuan Cheng, Nan WuManifold Learning Graph Diffusion
Department of Mathematics, Duke University · Department of Mathematical Sciences, The University of Texas at Dallas
Multi-kernel spectral clustering: Entrywise eigenvector perturbation bounds and exact recovery
Aug 9, 2026Zeqin Lin, Guangming Pan, Zhixiang Zhang +1Clustering Unsupervised Clustering
1Nanyang Technological University · University of Macau · 3Dalian University of Technology

Apr 15, 2026J/K move · Enter open · S save

Complex Interpolation of Matrices with an application to Multi-Manifold Learning

Adi Arbel, Stefan Steinerberger, Ronen Talmon

Viterbi Faculty of Electrical and Computer Engineering, Technion – Israel Institute of Technology, Haifa, Israel · Department of Mathematics and Department of Applied Mathematics, University of Washington, Seattle, WA 98195, USA

Multi-View Learning Manifold Learning

Open paper AskPDF arXiv

Given two symmetric positive-definite matrices

A, B \in \mathbb{R}^{n \times n}

, we study the spectral properties of the interpolation

A^{1-x} B^x

for

0 \leq x \leq 1

. The presence of `common structures' in

A

and

B

, eigenvectors pointing in a similar direction, can be investigated using this interpolation perspective. Generically, exact log-linearity of the operator norm

\|A^{1-x} B^x\|

is equivalent to the existence of a shared eigenvector in the original matrices; stability bounds show that approximate log-linearity forces principal singular vectors to align with leading eigenvectors of both matrices. These results give rise to and provide theoretical justification for a multi-manifold learning framework that identifies common and distinct latent structures in multiview data.

Abstract

Manifold Learning

Explore similar work

Complex Interpolation of Matrices with an application to Multi-Manifold Learning

Learning manifold diffusion semigroups from graph transition matrices

Multi-kernel spectral clustering: Entrywise eigenvector perturbation bounds and exact recovery