Clustering using Max-norm Constrained Optimization

Abstract

We suggest using the max-norm as a convex surrogate constraint for clustering. We show how this yields a better exact cluster recovery guarantee than previously suggested nuclear-norm relaxation, and study the effectiveness of our method, and other related convex relaxations, compared to other clustering approaches.

References in corpus (1)

• Large Scale Correlation Clustering Optimization

Cited by in corpus (6)

• Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
• Near-Optimal Joint Object Matching via Convex Relaxation
• Breaking the Small Cluster Barrier of Graph Clustering
• Recovery guarantees for exemplar-based clustering
• An Inexact Proximal Path-Following Algorithm for Constrained Convex Minimization
• Online Optimization for Large-Scale Max-Norm Regularization