# Learning Transition Operators From Sparse Space-Time Samples

arXiv: https://arxiv.org/abs/2212.00746 · HTML: https://mlsanity.com/paper/2212.00746/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 153 references that are in the map.
- First posted on arXiv 1 Dec 2022.

## Builds on (most cited first, 30 of 37)

- [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018)
- [How to learn a graph from smooth signals](https://mlsanity.com/paper/1601.02513/) (2016)
- [Connecting the Dots: Identifying Network Structure via Graph Signal Processing](https://mlsanity.com/paper/1810.13066/) (2018)
- [Near optimal finite time identification of arbitrary linear dynamical systems](https://mlsanity.com/paper/1812.01251/) (2018)
- [Guaranteed Matrix Completion via Non-convex Factorization](https://mlsanity.com/paper/1411.8003/) (2014)
- [Non-asymptotic Identification of LTI Systems from a Single Trajectory](https://mlsanity.com/paper/1806.05722/) (2018)
- [Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition](https://mlsanity.com/paper/1504.05477/) (2015)
- [Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution](https://mlsanity.com/paper/1711.10467/) (2017)
- [Network Topology Inference from Spectral Templates](https://mlsanity.com/paper/1608.03008/) (2016)
- [Learning heat diffusion graphs](https://mlsanity.com/paper/1611.01456/) (2016)
- [Non-asymptotic Identification of Linear Dynamical Systems Using Multiple Trajectories](https://mlsanity.com/paper/2009.00739/) (2020)
- [Scalable Semidefinite Programming](https://mlsanity.com/paper/1912.02949/) (2019)
- [Incoherence-Optimal Matrix Completion](https://mlsanity.com/paper/1310.0154/) (2013)
- [Nonconvex Nonsmooth Low-Rank Minimization via Iteratively Reweighted Nuclear Norm](https://mlsanity.com/paper/1510.06895/) (2015)
- [Finding Low-Rank Solutions via Non-Convex Matrix Factorization, Efficiently and Provably](https://mlsanity.com/paper/1606.03168/) (2016)
- [Guarantees of Riemannian Optimization for Low Rank Matrix Completion](https://mlsanity.com/paper/1603.06610/) (2016)
- [Graph Learning from Filtered Signals: Graph System and Diffusion Kernel Identification](https://mlsanity.com/paper/1803.02553/) (2018)
- [Non-Asymptotic Analysis of Robust Control from Coarse-Grained Identification](https://mlsanity.com/paper/1707.04791/) (2017)
- [Robust Spectral Compressed Sensing via Structured Matrix Completion](https://mlsanity.com/paper/1304.8126/) (2013)
- [A Scalable Second Order Method for Ill-Conditioned Matrix Completion from Few Samples](https://mlsanity.com/paper/2106.02119/) (2021)
- [Algebraic Variety Models for High-Rank Matrix Completion](https://mlsanity.com/paper/1703.09631/) (2017)
- [Structured Gradient Descent for Fast Robust Low-Rank Hankel Matrix Completion](https://mlsanity.com/paper/2204.03316/) (2022)
- [Rank 2r iterative least squares: efficient recovery of ill-conditioned low rank matrices from few entries](https://mlsanity.com/paper/2002.01849/) (2020)
- [GNMR: A provable one-line algorithm for low rank matrix recovery](https://mlsanity.com/paper/2106.12933/) (2021)
- [SDPNAL+: A Matlab software for semidefinite programming with bound constraints (version 1.0)](https://mlsanity.com/paper/1710.10604/) (2017)
- [State-Space Network Topology Identification from Partial Observations](https://mlsanity.com/paper/1906.10471/) (2019)
- [Learning Partially Observed Linear Dynamical Systems from Logarithmic Number of Samples](https://mlsanity.com/paper/2010.04015/) (2020)
- [Harmonic Mean Iteratively Reweighted Least Squares for Low-Rank Matrix Recovery](https://mlsanity.com/paper/1703.05038/) (2017)
- [Tensor Methods for Nonlinear Matrix Completion](https://mlsanity.com/paper/1804.10266/) (2018)
- [Low-rank Optimization with Convex Constraints](https://mlsanity.com/paper/1606.01793/) (2016)

## Built on by (most cited first, 1 of 1)

- [Interacting Particle Systems on Networks: joint inference of the network and the interaction kernel](https://mlsanity.com/paper/2402.08412/) (2024)

## Abstract (arXiv)

We consider the nonlinear inverse problem of learning a transition operator A from partial observations at different times, in particular from sparse observations of entries of its powers A,A2,cdots,AT. 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 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 O(rn log(nT)) space-time samples are sufficient to ensure accurate recovery of a rank-r operator A of size n × 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.