Recovering Trees with Convex Clustering

Abstract

Convex clustering refers, for given _1, , x_n\ R^p, to the minimization of eqnarray* u( ) & = & u_1, , u_n \; _i=1^n x_i - u_i ^2 + _i,j=1^nw_ij u_i - u_j ,\\ eqnarray* where w_ij 0 is an affinity that quantifies the similarity between x_i and x_j. We prove that if the affinities w_ij reflect a tree structure in the _1, , x_n\, then the convex clustering solution path reconstructs the tree exactly. The main technical ingredient implies the following combinatorial byproduct: for every set _1, , x_n \ R^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 R^p such that, when viewed from x, `most' points lie in the direction v eqnarray* 1n-1 _i=1 x_i x^n x_i - x x_i - x , v & & 14. eqnarray*

Tasks

Reproductions