  We introduce a new family of matrix norms, the "local max" norms,
generalizing existing methods such as the max norm, the trace norm (nuclear
norm), and the weighted or smoothed weighted trace norms, which have been
extensively used in the literature as regularizers for matrix reconstruction
problems. We show that this new family can be used to interpolate between the
(weighted or unweighted) trace norm and the more conservative max norm. We test
this interpolation on simulated data and on the large-scale Netflix and
MovieLens ratings data, and find improved accuracy relative to the existing
matrix norms. We also provide theoretical results showing learning guarantees
for some of the new norms.
