Majorization methods for solving the convex clustering problem

The convex clustering problem is a convex relaxation of the problem of finding similar groups in data. Solving this yields a global minimum that can be used to construct a solution path or a network that shows how data points cluster. This research looks at majorization methods to solve the l2 convex clustering problem and compares it with gradient descent in runtime. First, a proximal distance method is used and improved to get a majorization algorithm, next a norm marorization technique is used that gives a fast algorithm that involves solving a system of equations. Finally, another round of majorization gives a method based on eigenvalues, which bypasses solving a linear system and is thus faster for larger problems. The norm majorization method finds the l2 solution path in the same runtime on average as the gradient descent method, which suggests that implementing this norm method in a low level programming language gives a fast algorithm to solve the convex clustering problem.