Timezone: »

Convex Optimization Procedure for Clustering: Theoretical Revisit
Changbo Zhu · Huan Xu · Chenlei Leng · Shuicheng Yan

Mon Dec 08 04:00 PM -- 08:59 PM (PST) @ Level 2, room 210D

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.

Author Information

Changbo Zhu (National University of Singapore)
Huan Xu (National University of Singapore)
Chenlei Leng
Shuicheng Yan (National University of Singapore)

More from the Same Authors