Matching correlated VAR time series

Abstract

We study the problem of aligning time series databases, where a multivariate time series is observed along with a perturbed and permuted version, and the goal is to recover the unknown matching between them. To model this, we introduce a probabilistic framework in which both series follow a correlated vector autoregressive (VAR) process jointly. This generalizes the classical problem of matching independent point clouds to the time series setting, with envisaged applications in privacy and sensor fusion.

We derive the maximum likelihood estimator (MLE), leading to a quadratic optimization over permutations, and theoretically analyze an estimator based on linear assignment. For the linear assignment approach, we establish recovery guarantees, identifying correlation thresholds that allow for perfect or partial recovery. We also explore convex relaxations of the MLE, including relaxations over the Birkhoff polytope, which allow the joint estimation of the hidden permutationand the autoregressive process parameters. To solve it, we propose an algorithm based on alternating optimization.

Empirically, we find that the linear assignment method often matches or outperforms MLE relaxations, even when the latter have oracle access to the underlying VAR parameters, for recovering the matching. These findings highlight the theoretical and practical effectiveness of efficient algorithms for structured time series alignment.

Biography

Ernesto Araya is a postdoctoral researcher at the Bavarian AI Chair for Mathematical Foundations of AI at LMU Munich. He earned his PhD in Applied Mathematics in 2020 from Université Paris-Saclay under the supervision of Yohann de Castro, focusing on statistical inference on graphs. Following his doctoral studies, he was a postdoctoral fellow in the MODAL group at Inria Lille. His research interests lie at the intersection of mathematical statistics, high-dimensional probability, and algorithms, with a particular focus on matching problems and recovery guarantees in structured estimation.