Convex Optimization Procedure for Clustering: Theoretical Revisit
Lists
Only you see this
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.
BibTeX
@inproceedings{zhu2014convex,
author = {Changbo Zhu and Huan Xu and Chenlei Leng and Shuicheng YAN},
title = {{Convex Optimization Procedure for Clustering: Theoretical Revisit}},
booktitle = {Advances in Neural Information Processing Systems},
year = {2014},
}Loading related content...