# Certifying clusters from sum-of-norms clustering

arXiv: https://arxiv.org/abs/2006.11355 · HTML: https://mlsanity.com/paper/2006.11355/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Jun 2020.

## Built on by (most cited first, 3 of 3)

- [Local versions of sum-of-norms clustering](https://mlsanity.com/paper/2109.09589/) (2021)
- [Sum-of-norms clustering does not separate nearby balls](https://mlsanity.com/paper/2104.13753/) (2021)
- [Sum-of-norms regularized Nonnegative Matrix Factorization](https://mlsanity.com/paper/2407.00706/) (2024)

## Abstract (arXiv)

Sum-of-norms clustering is a clustering formulation based on convex optimization that automatically induces hierarchy. Multiple algorithms have been proposed to solve the optimization problem: subgradient descent by Hocking et al., ADMM and ADA by Chi and Lange, stochastic incremental algorithm by Panahi et al. and semismooth Newton-CG augmented Lagrangian method by Sun et al. All algorithms yield approximate solutions, even though an exact solution is demanded to determine the correct cluster assignment. The purpose of this paper is to close the gap between the output from existing algorithms and the exact solution to the optimization problem. We present a clustering test that identifies and certifies the correct cluster assignment from an approximate solution yielded by any primal-dual algorithm. Our certification validates clustering for both unit and multiplicative weights. The test may not succeed if the approximation is inaccurate. However, we show the correct cluster assignment is guaranteed to be certified by a primal-dual path following algorithm after sufficiently many iterations, provided that the model parameter λ avoids a finite number of bad values. Numerical experiments are conducted on Gaussian mixture and half-moon data, which indicate that carefully chosen multiplicative weights increase the recovery power of sum-of-norms clustering.