  Low-rank matrix models have been universally useful for numerous
applications, from classical system identification to more modern matrix
completion in signal processing and statistics. The nuclear norm has been
employed as a convex surrogate of the low-rankness since it induces a low-rank
solution to inverse problems. While the nuclear norm for low rankness has an
excellent analogy with the $\ell_1$ norm for sparsity through the singular
value decomposition, other matrix norms also induce low-rankness. Particularly
as one interprets a matrix as a linear operator between Banach spaces, various
tensor product norms generalize the role of the nuclear norm. We provide a
tensor-norm-constrained estimator for the recovery of approximately low-rank
matrices from local measurements corrupted with noise. A tensor-norm
regularizer is designed to adapt to the local structure. We derive statistical
analysis of the estimator over matrix completion and decentralized sketching by
applying Maurey's empirical method to tensor products of Banach spaces. The
estimator provides a near-optimal error bound in a minimax sense and admits a
polynomial-time algorithm for these applications.
