Let $X$ be a matrix. The max-norm regularizes maximum of its singular values
$$|X|_{\infty} = \max(\sigma_i)$$
while trace-norm penalizes sum of all singular values
$$|X|_* = \sum_{i = 1}^m \sigma_i$$
However, the trace-norm is now much more popular in matrix completion, mainly because
- nice theoretical analysis, e.g., Candès 2009, and
- fast algorithms to do optimization, like proximal gradient descents ones (active, AIS-Impute).
However, besides computational issues, in practice, which one performs better?
I've seen some old comments on this topic:
- Practical Large-Scale Optimization for Max-Norm Regularization. NIPS 2010.
which said max-norm gave better prediction on non-uniform sampled data. If this were true, then max-norm should be better in real cases due to long-tail effects.