  Koopman operators provide tractable means of learning linear approximations
of non-linear dynamics. Many approaches have been proposed to find these
operators, typically based upon approximations using an a-priori fixed class of
models. However, choosing appropriate models and bounding the approximation
error is far from trivial. Motivated by these difficulties, in this paper we
propose an optimization based approach to learning Koopman operators from data.
Our results show that the Koopman operator, the associated Hilbert space of
observables and a suitable dictionary can be obtained by solving two
rank-constrained semi-definite programs (SDP). While in principle these
problems are NP-hard, the use of standard relaxations of rank leads to convex
SDPs. Further, these SDPs exhibit chordal sparsity leading to algorithms that
scale linearly with the number of data points.
