Clustering using Max-norm Constrained Optimization

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

paper · pdf · doi:10.48550/arxiv.1202.5598

arxiv created 2012/04/13 · arxiv updated 2012/04/16

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