Cluster Trees on Manifolds
This addresses the challenge of high-dimensional clustering for data on manifolds, providing dimension-independent guarantees that are incremental improvements over existing methods.
The paper tackles the problem of estimating cluster trees for densities on manifolds, showing that a modified k-nearest neighbor algorithm achieves convergence rates dependent only on the intrinsic manifold dimension rather than the ambient space dimension.
In this paper we investigate the problem of estimating the cluster tree for a density $f$ supported on or near a smooth $d$-dimensional manifold $M$ isometrically embedded in $\mathbb{R}^D$. We analyze a modified version of a $k$-nearest neighbor based algorithm recently proposed by Chaudhuri and Dasgupta. The main results of this paper show that under mild assumptions on $f$ and $M$, we obtain rates of convergence that depend on $d$ only but not on the ambient dimension $D$. We also show that similar (albeit non-algorithmic) results can be obtained for kernel density estimators. We sketch a construction of a sample complexity lower bound instance for a natural class of manifold oblivious clustering algorithms. We further briefly consider the known manifold case and show that in this case a spatially adaptive algorithm achieves better rates.