Technical Summary: CHASM – Online Changepoint Detection in Temporal and Cross-Variable Dependence

Problem Definition

The paper addresses the challenge of online changepoint detection in multivariate time series, specifically focusing on shifts in temporal and cross-variable dependence rather than shifts in marginal statistics (e.g., mean or variance). In many applications (finance, neuroscience, climate), the underlying generative process is a Vector Autoregressive (VAR) process where the transition matrix $\Theta$ encodes the system's dynamics. A change in $\Theta$ may be subtle and not manifest in the marginal distribution of individual variables, rendering standard methods that monitor marginal statistics ineffective.

The problem is formulated as detecting a single changepoint $\tau$ in a stream of observations $x_t \in \mathbb{R}^d$ where the transition matrix shifts from $\Theta_0$ to $\Theta_1$. The method must operate in an online regime, processing each observation in constant time with memory independent of the sequence length, without relying on parametric assumptions about the noise distribution.

Methodology: CHASM

The authors propose CHASM (Complex Hungarian-Aligned Spectrum Monitoring), an unsupervised, nonparametric method that monitors the dominant eigenvalues of a recursively estimated dynamics operator. The approach consists of three main stages:

1. Online Dynamics Estimation

CHASM employs Recursive Least Squares (RLS) to estimate the transition matrix $\Theta_n$ online, corresponding to an online version of Dynamic Mode Decomposition (DMD).

• The estimator uses a forgetting factor $\rho \in (0, 1]$ to weight recent observations, allowing the algorithm to adapt to changes.
• Unlike methods that regularize during estimation (e.g., via $\ell_1$-penalization), CHASM leaves the estimation unconstrained and applies rank truncation as a post-estimation step.
• At each step, the algorithm computes the truncated eigendecomposition of $\Theta_n$, retaining the $r$ dominant eigenvalues $\lambda_n \in \mathbb{C}^r$. This transforms the multivariate real-valued stream into a sequence of complex spectral summaries.

2. Optimal Eigenvalue Alignment

A critical challenge in monitoring eigenvalues is the permutation invariance of eigendecompositions; numerical solvers do not guarantee consistent ordering of eigenvalues across time steps, leading to artificial discontinuities.

• CHASM addresses this by formulating the alignment of consecutive eigenvalue vectors $\lambda_{n-1}$ and $\lambda_n$ as an optimal transport problem.
• The authors prove that the optimal coupling is a permutation map that minimizes the squared 2-Wasserstein distance between the empirical measures of the eigenvalues.
• This is solved efficiently via a linear assignment problem (using the Hungarian algorithm or its variants), reducing the complexity from factorial to polynomial time ($O(r^3)$). This ensures the trajectories of individual eigenvalues are continuous and interpretable.

3. Complex Multivariate Changepoint Detection

The aligned sequence of eigenvalue vectors is treated as a multivariate complex-valued time series.

• The method tracks the first-order differences (spectral velocity) $v_n = \lambda_n - \lambda_{n-1}$. Under stationarity, these velocities fluctuate around zero; a changepoint induces a coherent directional shift.
• To handle the complex nature of the data, CHASM extends the Multivariate Exponentially Weighted Moving Average (MEWMA) scheme. It constructs an augmented vector $z_n = (v_n, v_n^*)$ to account for both the Hermitian covariance and the pseudo-covariance (improperness) of the complex sequence.
• A detection statistic $D_n^2$ is defined as the squared Mahalanobis distance of the augmented state from its mean. A changepoint is declared when $D_n^2$ exceeds a threshold $h$.

Key Contributions

1. Direct Operator Monitoring: CHASM is the first online changepoint method to directly track the operator spectrum (eigenvalues) of a dynamics operator, rather than relying on indirect reconstruction errors or scalar functionals that may discard structural information.
2. Complex Eigenvalue Alignment: The paper introduces a novel method to align consecutive complex eigenvalue vectors via optimal transport (linear assignment), resolving the permutation ambiguity inherent in numerical eigendecompositions.
3. Complex-Valued Detection Scheme: It proposes an extension of MEWMA to the complex domain, utilizing augmented vectors to capture the full second-order statistics (covariance and pseudo-covariance) of the spectral velocities.
4. Theoretical Guarantees: The authors establish the consistency and characterize the bias of the online DMD estimator under the canonical VAR model with minimal assumptions (finite moments, no parametric noise distribution). They reveal a trade-off between estimation accuracy and detection sensitivity controlled by the forgetting factor $\rho$.
5. Empirical Performance: CHASM demonstrates competitive or superior performance against modern baselines (including subspace-based, high-dimensional, and Bayesian methods) across diverse synthetic noise distributions (Gaussian, heavy-tailed, contaminated) and real-world modalities (motion, image, text, video).

Results

• Synthetic Data: CHASM consistently achieves the highest F1-scores across bivariate and high-dimensional VAR processes with various noise distributions (including Student's $t$ and Huber contamination). It maintains robustness even when the rank is misspecified or the dynamics are full-rank, where competitors relying on sparsity assumptions (e.g., Tian & Safikhani) degrade.
• Real-World Data: The method is evaluated on five datasets: HASC (accelerometry), CIFAR-100 (images), 20 Newsgroups (text), UCF-Crime (video), and WikiSection (token-level text). CHASM is the only method to perform consistently well across all modalities, particularly excelling in settings with nonlinear temporal dynamics (UCF-Crime) and piecewise i.i.d. shifts (CIFAR-100, 20 Newsgroups).
• Efficiency: The algorithm operates with $O(d^2 r)$ time complexity and $O(d^2)$ space complexity per step, making it suitable for high-dimensional streaming data. It avoids the cubic cost of full eigendecompositions by using rank-truncated updates.

Significance and Claims

The paper claims that CHASM provides a direct, interpretable, and computationally efficient approach to detecting changes in the dynamical structure of multivariate time series. By monitoring the operator spectrum directly, it captures shifts in stability and oscillatory behavior that marginal statistics miss.

The authors emphasize that the method is unsupervised and requires no distributional assumptions beyond finite moments, making it readily deployable across scientific domains where noise characteristics are unknown or non-Gaussian. While the theoretical analysis is grounded in the VAR framework, the empirical results demonstrate that CHASM generalizes effectively to non-VAR settings, including complex video and text data, suggesting its utility as a general-purpose tool for monitoring dynamical systems. The work highlights the importance of addressing the permutation invariance of eigenvalues and the specific statistical properties of complex-valued sequences in online detection tasks.