Recovering Trees with Convex Clustering

Hierarchical clustering is a fundamental unsupervised learning task, whose aim is to organize a collection of points into a tree of nested clusters. Convex clustering has been proposed recently as a new way to construct tree organizations of data that are more robust to perturbations in the input data than standard hierarchical clustering algorithms. In this paper, we present conditions that guarantee when the convex clustering solution path recovers a tree and also make explicit how affinity parameters in the convex clustering formulation modulate the structure of the recovered tree. The proof of our main result relies on establishing a novel property of point clouds in a Hilbert space, which is potentially of independent interest.