  Regularization techniques are widely employed in optimization-based
approaches for solving ill-posed inverse problems in data analysis and
scientific computing. These methods are based on augmenting the objective with
a penalty function, which is specified based on prior domain-specific expertise
to induce a desired structure in the solution. We consider the problem of
learning suitable regularization functions from data in settings in which
precise domain knowledge is not directly available. Previous work under the
title of `dictionary learning' or `sparse coding' may be viewed as learning a
regularization function that can be computed via linear programming. We
describe generalizations of these methods to learn regularizers that can be
computed and optimized via semidefinite programming. Our framework for learning
such semidefinite regularizers is based on obtaining structured factorizations
of data matrices, and our algorithmic approach for computing these
factorizations combines recent techniques for rank minimization problems along
with an operator analog of Sinkhorn scaling. Under suitable conditions on the
input data, our algorithm provides a locally linearly convergent method for
identifying the correct regularizer that promotes the type of structure
contained in the data. Our analysis is based on the stability properties of
Operator Sinkhorn scaling and their relation to geometric aspects of
determinantal varieties (in particular tangent spaces with respect to these
varieties). The regularizers obtained using our framework can be employed
effectively in semidefinite programming relaxations for solving inverse
problems.
