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.
