Recovering Trees with Convex Clustering

Convex clustering refers, for given leftx1, dots, xnright subset ℝp, to the minimization of begineqnarray* u(γ) & = & undersetu1, dots, un argmin;sumi=1nlVert xi - ui rVert2 + γ sumi,j=1nwij lVert ui - ujrVert, endeqnarray* where wij ≥ 0 is an affinity that quantifies the similarity between xi and xj. We prove that if the affinities wij reflect a tree structure in the leftx1, dots, xnright, then the convex clustering solution path reconstructs the tree exactly. The main technical ingredient implies the following combinatorial byproduct: for every set leftx1, dots, xn right subset ℝp of n ≥ 2 distinct points, there exist at least n/6 points with the property that for any of these points x there is a unit vector v ∈ ℝp such that, when viewed from x, `most' points lie in the direction v begineqnarray* frac1n-1sumi=1 atop xi neq xn leftlangle fracxi - xlVert xi - x rVert, v rightrangle & ≥ & frac14. endeqnarray*