Clustering using Max-norm Constrained Optimization
  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. 
Ali Jalali and Nathan Srebro
cs.LG stat.ML