  We consider the nonlinear inverse problem of learning a transition operator
$\mathbf{A}$ from partial observations at different times, in particular from
sparse observations of entries of its powers
$\mathbf{A},\mathbf{A}^2,\cdots,\mathbf{A}^{T}$. This Spatio-Temporal
Transition Operator Recovery problem is motivated by the recent interest in
learning time-varying graph signals that are driven by graph operators
depending on the underlying graph topology. We address the nonlinearity of the
problem by embedding it into a higher-dimensional space of suitable
block-Hankel matrices, where it becomes a low-rank matrix completion problem,
even if $\mathbf{A}$ is of full rank. For both a uniform and an adaptive random
space-time sampling model, we quantify the recoverability of the transition
operator via suitable measures of incoherence of these block-Hankel embedding
matrices. For graph transition operators these measures of incoherence depend
on the interplay between the dynamics and the graph topology. We develop a
suitable non-convex iterative reweighted least squares (IRLS) algorithm,
establish its quadratic local convergence, and show that, in optimal scenarios,
no more than $\mathcal{O}(rn \log(nT))$ space-time samples are sufficient to
ensure accurate recovery of a rank-$r$ operator $\mathbf{A}$ of size $n \times
n$. This establishes that spatial samples can be substituted by a comparable
number of space-time samples. We provide an efficient implementation of the
proposed IRLS algorithm with space complexity of order $O(r n T)$ and
per-iteration time complexity linear in $n$. Numerical experiments for
transition operators based on several graph models confirm that the theoretical
findings accurately track empirical phase transitions, and illustrate the
applicability and scalability of the proposed algorithm.
