Ziyue Liu, Ruijie Zhang, Zhengyang Wang, Mingsong Yan, Zi Yang, Paul D. Hovland, Bogdan Nicolae, Franck Cappello, Sui Tang, Zheng Zhang. Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing. 2025.

We consider the nonlinear inverse problem of learning a transition operator A from partial observations at T different times, in the form of sparse observations of entries of the powers$\mathbf {A},\mathbf {A}^{2},\cdots ,\mathbf {A}^{T}$. We address the nonlinearity of this spatio-temporal transition operator recovery problem by a suitable embedding into block-Hankel matrices, transforming it to a low-rank matrix completion problem, even when A has 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 A of size$n \times n$. 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, and confirm in numerical experiments that for several graph transition operators, the theoretical findings accurately track empirical phase transitions.

We consider the space-time sampling and reconstruction of sparse bandlimited graph signals driven by a heat diffusion process. In this paper, we develop a sampling framework consisting of selecting a small subset of space-time nodes at random according to some probability distribution, generalizing the classical variable density sampling to the heat diffusion field. We show that the number of space-time samples required to ensure stable recovery depends on an incoherence parameter determined by the interplay between graph topology, temporal dynamics, and sampling probability distributions. In optimal scenarios, as few as $\mathcal{O}\left( {s\log k} \right)$ space-time samples are sufficient to ensure accurate recovery of all k-bandlimited graph signals that are additionally s-sparse. Our proposed sampling method requires much fewer spatial samples than the static case by leveraging temporal information. Finally, we test our sampling techniques on a wide variety of graphs. The numerical results on synthetic and real climate data sets support our theoretical findings and demonstrate the practical applicability.

Systems of interacting particles, or agents, have wide applications in many disciplines, including Physics, Chemistry, Biology and Economics. These systems are governed by interaction laws, which are often unknown: estimating them from observation data is a fundamental task that can provide meaningful insights and accurate predictions of the behaviour of the agents. In this paper, we consider the inverse problem of learning interaction laws given data from multiple trajectories, in a nonparametric fashion, when the interaction kernels depend on pairwise distances. We establish a condition for learnability of interaction kernels, and construct an estimator based on the minimization of a suitably regularized least squares functional, that is guaranteed to converge, in a suitable $L^2$ space, at the optimal min-max rate for 1-dimensional nonparametric regression. We propose an efficient learning algorithm to construct such estimator, which can be implemented in parallel for multiple trajectories and is therefore well-suited for the high dimensional, big data regime. Numerical simulations on a variety examples, including opinion dynamics, predator-prey and swarm dynamics and heterogeneous particle dynamics, suggest that the learnability condition is satisfied in models used in practice, and the rate of convergence of our estimator is consistent with the theory. These simulations also suggest that our estimators are robust to noise in the observations, and can produce accurate predictions of trajectories in large time intervals, even when they are learned from observations in short time intervals.

Let (I, +) be a finite abelian group and A be a circular convolution operator on ℓ2(I). The problem under consideration is how to construct minimal Ω ⊂ I and lisuch that Y = {ei, Aei, · · · , Aliei: i ∈ Ω} is a frame for ℓ2(I), where {ei: i ∈ I} is the canonical basis of ℓ2(I). This problem is motivated by the spatiotemporal sampling problem in discrete spatially invariant evolution processes. We will show that the cardinality of Ω should be at least equal to the largest geometric multiplicity of eigenvalues of A, and consider the universal spatiotemporal sampling sets (Ω, li) for convolution operators whose eigenvalues subject to the same largest geometric multiplicity. We will give an algebraic characterization for such sampling sets and show how this problem is linked with sparse signal processing theory and polynomial interpolation theory.