Applied Mathematics Colloquia with Mauro Maggioni - Two Estimation Problems for Dynamical Systems: Linear Systems on Graphs, and Interacting Particle Systems

Speaker: Mauro Maggioni, Bloomberg Distinguished Professor of Mathematics and Applied Mathematics and Statistics, Johns Hopkins University

Title: Two Estimation Problems for Dynamical Systems: Linear Systems on Graphs, and Interacting Particle Systems

Abstract: 

We are interested in problems where certain key parameters of a dynamical system need to be estimated from observations of trajectories of the dynamical systems. In this talk I will discuss two problems of this type.

The first one is the following: suppose we have a linear dynamical systems on a graph, represented by a matrix A. For example, A may be a random walk on the graph. Suppose we observe some entries of A, some entries of A^2, …, some entries of A^T, for some time T, and wish to estimate A. We are interested in the regime when the number of entries observed at each time is small relative to the total number of entries of A. When T=1 and A is low-rank, this is a matrix completion problem. When T>1, the problem is interesting also in the case when A is not low rank, as one may hope that sampling at multiple times can compensate for the small number of entries observed at each time. We develop conditions that ensure that this estimation problem is well-posted, introduce a procedure for estimating A by reducing the problem to the matrix completion of a low-rank structured block-Hankel matrix, obtain results that capture at least some of trade-offs between sampling in space and time, and finally show that this estimator can be constructed by a fast algorithm that provably locally converges quadratically to A. We verify this numerically on a variety of examples. This is joint work with C. Kuemmerle and S. Tang.

The second problem is when the dynamical system is nonlinear, and models a set of interacting agents. These systems are ubiquitous in science, from modeling of particles in Physics to prey-predator and colony models in Biology, to opinion dynamics in social sciences. Oftentimes the laws of interactions between the agents are quite simple, for example they depend only on pairwise interactions, and only on pairwise distance in each interaction. We consider the following inference problem for a system of interacting particles or agents: given only observed trajectories of the agents in the system, can we learn what the laws of interactions are? We would like to do this without assuming any particular form for the interaction laws, i.e. they might be “any” function of pairwise distances. We discuss when this problem is well-posed, we construct estimators for the interaction kernels with provably good statistically and computational properties, and discuss extensions to second-order systems, more general interaction kernels, and stochastic systems. We measure empirically the performance of our techniques on various examples, that include extensions to agent systems with different types of agents, second-order systems, families of systems with parametric interaction kernels, and settings where the interaction kernels depend on unknown variables. We also conduct numerical experiments to test the large time behavior of these systems, especially in the cases where they exhibit emergent behavior. This is joint work with F. Lu, J. Feng, P. Martin, J. Miller, S. Tang and M. Zhong.

Applied Mathematics Colloquia