Skip to yearly menu bar Skip to main content


Poster

Convex Optimization Procedure for Clustering: Theoretical Revisit

Changbo Zhu · Huan Xu · Chenlei Leng · Shuicheng Yan

Level 2, room 210D

Abstract:

In this paper, we present theoretical analysis of SON~--~a convex optimization procedure for clustering using a sum-of-norms (SON) regularization recently proposed in \cite{ICML2011Hocking_419,SON, Lindsten650707, pelckmans2005convex}. In particular, we show if the samples are drawn from two cubes, each being one cluster, then SON can provably identify the cluster membership provided that the distance between the two cubes is larger than a threshold which (linearly) depends on the size of the cube and the ratio of numbers of samples in each cluster. To the best of our knowledge, this paper is the first to provide a rigorous analysis to understand why and when SON works. We believe this may provide important insights to develop novel convex optimization based algorithms for clustering.

Live content is unavailable. Log in and register to view live content