  In this paper, we present a unified analysis of matrix completion under
general low-dimensional structural constraints induced by {\em any} norm
regularization. We consider two estimators for the general problem of
structured matrix completion, and provide unified upper bounds on the sample
complexity and the estimation error. Our analysis relies on results from
generic chaining, and we establish two intermediate results of independent
interest: (a) in characterizing the size or complexity of low dimensional
subsets in high dimensional ambient space, a certain partial complexity measure
encountered in the analysis of matrix completion problems is characterized in
terms of a well understood complexity measure of Gaussian widths, and (b) it is
shown that a form of restricted strong convexity holds for matrix completion
problems under general norm regularization. Further, we provide several
non-trivial examples of structures included in our framework, notably the
recently proposed spectral $k$-support norm.
