A dual reformulation and solution framework for regularized convex clustering problems

Clustering techniques are powerful tools commonly used in statistical learning and data analytics. Most of the past research formulates clustering tasks as a non-convex problem, where a global optimum often cannot be found. Recent studies show that hierarchical clustering and k-means clustering can be relaxed and analyzed as a convex problem. Moreover, sparse convex clustering algorithms are proposed to extend the convex clustering framework to high-dimensional space by introducing an adaptive group-Lasso penalty term. Due to the non-smoothness nature of the associated objective functions, there are still no efficient fast-convergent algorithms for clustering problems even with convexity. In this paper, we first review the structure of convex clustering problems and prove the differentiability of their dual problems. We then show that such reformulated dual problems can be efficiently solved by the accelerated first-order methods with the feasibility projection. Furthermore, we present a general framework for convex clustering with regularization terms and discuss a specific implementation of this framework using L1,1-norm. We also derive the dual form for the regularized convex clustering problems and show that it can be efficiently solved by embedding a projection operator and a proximal operator in the accelerated gradient method. Finally, we compare our approach with several other co-clustering algorithms using a number of example clustering problems. Numerical results show that our models and solution methods outperform all the compared algorithms for both convex clustering and convex co-clustering.