Cluster Trees on Manifolds
Abstract
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 study a $k$-nearest neighbor based algorithm recently proposed by Chaudhuri and Dasgupta. 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 provide a sample complexity lower bound for a natural class of clustering algorithms that use $D$-dimensional neighborhoods.
Cite
Text
Balakrishnan et al. "Cluster Trees on Manifolds." Neural Information Processing Systems, 2013.Markdown
[Balakrishnan et al. "Cluster Trees on Manifolds." Neural Information Processing Systems, 2013.](https://mlanthology.org/neurips/2013/balakrishnan2013neurips-cluster/)BibTeX
@inproceedings{balakrishnan2013neurips-cluster,
title = {{Cluster Trees on Manifolds}},
author = {Balakrishnan, Sivaraman and Narayanan, Srivatsan and Rinaldo, Alessandro and Singh, Aarti and Wasserman, Larry},
booktitle = {Neural Information Processing Systems},
year = {2013},
pages = {2679-2687},
url = {https://mlanthology.org/neurips/2013/balakrishnan2013neurips-cluster/}
}