file.pdf (215.55 kB)
Download file

Cluster Trees on Manifolds

Download (215.55 kB)
journal contribution
posted on 01.12.2013, 00:00 by Sivaraman Balakrishnan, Srivatsan Narayanan, Alessandro Rinaldo, Aarti Singh, Larry Wasserman

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 R D. We analyze a modified version of a k-nearest neighbor based algorithm recently proposed by Chaudhuri and Dasgupta (2010). 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. Finally, we sketch a construction of a sample complexity lower bound instance for a natural class of manifold oblivious clustering algorithms.

History

Date

01/12/2013

Usage metrics

Exports