Clustering using Max-norm Constrained Optimization

2012/02/25 by Jalali, Ali, Srebro, Nathan
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.1202.5598

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.

Related

• Clustering, Hamming Embedding, Generalized LSH and the Max Norm
• The Why and How of Convex Clustering
• Convex Clustering: Model, Theoretical Guarantee and Efficient Algorithm
• Clustering to Minimize Cluster-Aware Norm Objectives
• Distribution free optimality intervals for clustering