Detecting Abrupt Changes in Irregularly Sampled Series with Linear-Time Sparse Smoothing

Many real time series drift smoothly most of the time and then change abruptly. A drug is given, a sensor is replaced, a vessel turns. These series are also usually sampled unevenly: clinicians measure often during a crisis and rarely when the patient is stable. We want to recover the whole underlying trajectory from such data, including when and how much it jumped. The goal is to do this in time that grows linearly with the number of observations, not cubically.

Linear-time machinery for this exists on uniform grids. A Kalman smoother is a two-pass recursion that computes the best trajectory estimate for a chain-structured model. Combined with variable splitting, which alternates between an easy smooth subproblem and a simple sparsity step, it handles sparse-change penalties on sequences of $10^8$ steps (IEKS-based variable splitting for $L_1$-regularized state estimation). But that formulation indexes time by step count. On irregular data the unevenness is not a nuisance. It decides whether an observed change should be read as ordinary drift over a long gap or as a jump over a short one. We propose a continuous-time jump-diffusion smoother whose jump threshold scales correctly with the gap length, solved exactly in $O(N)$ time in the number of observations $N$. We then test whether getting this scaling right, rather than the solver itself, is what matters.

Core Claim

A change of size $\delta$ between two observations separated by $\Delta t$ is ambiguous. Under a diffusion prior, where the state wanders randomly with variance growing like $q\,\Delta t$, a large $\delta$ over a long gap is unremarkable. The same $\delta$ over a short gap is strong evidence of a jump. Two existing approaches both fail to account for this. Discrete sparse smoothers applied to the observation index use one fixed process-noise level per step. Binning onto a coarse grid does the same. In both cases the implied jump threshold ignores $\Delta t$. This causes false jumps across long gaps and missed jumps in dense bursts.

The failure matters most when sampling is informative, meaning measurements cluster exactly around the events of interest. Our claim is that the correct linear-time estimator separates two components. The first is a Gaussian diffusion part whose covariance is integrated over each interval. The second is a sparse jump part whose penalty does not depend on interval length, because jumps are counted, not accumulated. With observations $y_i$ at times $t_i$, latent state $x_i$ at $t_i$, per-interval jump $u_i$, and interval length $\Delta t_i = t_i - t_{i-1}$, the estimator is

$$ \min_{x,u}\ \sum_i \|y_i - H x_i\|^2_{R^{-1}} + \sum_i \|x_i - A(\Delta t_i)\,x_{i-1} - B u_i\|^2_{Q(\Delta t_i)^{-1}} + \lambda \sum_i \|u_i\|_1 . $$

The terms are defined as follows. $H$ is the observation matrix and $R$ the noise covariance. $A(\Delta t)=\exp(F\Delta t)$ and $Q(\Delta t)$ are the exact discretization of a linear stochastic differential equation, meaning a linear dynamical system driven by random noise, with drift matrix $F$. Examples are a Matérn Gaussian-process prior or an integrated Wiener process. $B$ selects which state components may jump. $\lambda$ is a jump-rate parameter that is independent of $\Delta t$.

The problem is jointly convex. Fixing $u$ turns it into a Kalman smoothing problem with known inputs. Fixing $x$ gives independent small weighted-lasso problems per interval, where the metric $Q(\Delta t_i)^{-1}$ makes the effective threshold grow with $\sqrt{\Delta t_i}$. Each iteration therefore costs $O(N d^3)$, with $d$ the state dimension, regardless of how the timestamps are spread.

Research Program

The method borrows from three sources. The pseudo-measurement splitting of IEKS-based variable splitting and its constrained extension (variable splitting for constrained state estimation) supply the solver template. Both are derived and tested only on uniform grids. The exact per-interval transition and noise matrices come from the kernel-to-state-space conversion used in Markovian Gaussian Process VAEs. That work does exact Kalman smoothing on arbitrary time grids, but only under Gaussian dynamics, so it has no mechanism for sparse jumps. The equivalence between iterated extended Kalman smoothing and Gauss–Newton optimization, established in Bayesian ODE solvers: the MAP estimate and in the Levenberg–Marquardt extended Kalman smoothers, lets us extend the smooth subproblem to nonlinear observation models. In the nonlinear case, global optimality becomes local, a limitation those papers already document.

The work has four parts. First, we derive the estimator and a coordinate-descent/ADMM solver that alternates Kalman smoothing with per-interval soft-thresholding. We prove that each iteration is linear in $N$.

Second, we analyze grid refinement. Suppose a fixed continuous-time signal is observed more densely. Our objective's jump penalty stays fixed, and its diffusion term converges to the continuous-time energy. An index-based objective, by contrast, has a regularization strength that drifts with sampling density. We make this precise and predict the regime where the naive method's error grows: the ratio of longest to shortest gap.

Third, we treat hyperparameters. The file flags penalty tuning as a known weakness of splitting methods (IEKS-ADMM). Because $\lambda$ here is a per-unit-time jump rate, it transfers across datasets with different sampling densities. We select $\lambda$ and $q$ by held-out observation likelihood, and we test whether a single value transfers across sampling regimes.

Fourth, we address honest limits. Within a single interval, the exact jump time is not identifiable. For jumps in velocity rather than level, the effect on the next observation depends on that unknown time. We restrict jumps to components where this does not matter, or we report interval-level localization only.

Baselines

The naive reference is a continuous-time Gaussian smoother with no jump component, using the same Matérn or integrated-Wiener prior as in Markovian GP VAEs. It shows how much of the error comes from smoothing through jumps. We also run a constant-prediction baseline, because Physiome-ODE showed that such baselines can match complex models on weak-dynamics benchmarks. Any reported gain must clear it.

The most direct competitor is IEKS-ADMM from IEKS-based variable splitting, applied in two ways. The first applies it to the observation index directly, with a single tuned process-noise level. The second bins the data onto a uniform grid, with missing bins handled as skipped Kalman updates. It is the strongest competitor because it already solves the sparse-jump problem in linear time. The only thing it lacks is the continuous-time scaling we claim matters.

The key ablation keeps our solver and replaces $Q(\Delta t_i)$ with a constant $Q$. This isolates the ingredient we care about. For reported numbers, the file reports scaling to $10^8$ steps, a 7x speedup over first-order primal-dual at $T=100$, and 26.7 s versus 2,193 s for batch Split Bregman at $T=10^4$ in the constrained variant. These concern speed, not jump-recovery accuracy. No reported result was found on Lacuna for jump recovery under irregular sampling.

For forecasting and interpolation on real data, we include learned continuous-time models. On USHCN the reference number is MSE 0.34 for NCDSSM-NL (Neural Continuous-Discrete SSMs). On Physiome-ODE, LinODEnet, which ranked first on 29 of 50 datasets (Physiome-ODE), is the reference. No per-dataset error values are given in the file.

All methods share the same prior family where applicable, the same observations, and the same hyperparameter search budget, with tuning by held-out likelihood. Runtime is measured on the same hardware.

We count our method as beating a baseline under three conditions. It must achieve better jump-localization F1 and trajectory RMSE on held-out points. The gap must widen as the gap-length ratio grows. On uniformly sampled controls, where the two formulations coincide up to discretization, there should be no loss.

Why not just…?

Why not just run the existing uniform-grid IEKS-ADMM on a fine uniform grid? This is the most serious threat. As the grid is refined, that method approximates our objective. The price is a cost that scales with grid size, not observation count. For clinical timestamps spanning days at minute resolution, the grid can be orders of magnitude larger than $N$. Coarsening the grid instead blurs jump timing and merges intervals. We will report accuracy and runtime against grid resolution. If a moderate grid matches our accuracy at comparable cost, the contribution shrinks to a convenience result, and we will say so.

Why not just use heavy-tailed process noise, such as Student-t, solved by iteratively reweighted Kalman smoothing? This is close to our model family. It is also the kind of non-Gaussian reduction to Kalman steps used in Bayesian intermittent demand forecasting. The distinction is that a single heavy-tailed noise per interval does not decompose cleanly into a diffusion part that grows with $\Delta t$ and a jump part that does not. We include it with its scale grown as $\sqrt{\Delta t}$ as a baseline. If it ties, the finding is that the jump/diffusion decomposition is what matters and the choice of penalty is secondary. That would be a useful and honest outcome.

Why not just let a learned continuous-time model absorb the jumps? Models such as Neural Jump ODEs, NCDSSM, or attention models like mTAN handle irregular times and can fit abrupt changes. However, none of them outputs explicit sparse jump times and sizes. NCDSSM performs forward filtering rather than full smoothing. Such models also need training data containing many similar events. Our estimator works per series without training. On forecasting MSE the learned models may win, and we will report that. The claimed advantage is restricted to event recovery and data-poor settings.

Proposed Experiments

The primary testbed is Physiome-ODE (Physiome-ODE), using its protocol of 80% dropped observations plus Gaussian noise. We inject level jumps at random continuous times into a subset of state variables. We compare two sampling schemes. One is uniform-random. The other is informative, with sampling intensity rising after each jump to mimic clinical practice. We measure jump-localization F1 within a time tolerance, jump-size error, and held-out interpolation RMSE. We do this as a function of the longest-to-shortest-gap ratio. The decisive check is the constant-$Q$ ablation. The central prediction is that it degrades with the gap ratio and especially under informative sampling, while our estimator does not. If the two stay tied, the core claim is wrong.

A second experiment checks transfer. We fix $\lambda$ on one sampling density and evaluate at others. The prediction is that the rate-based $\lambda$ transfers and the index-based one does not.

On real data we use USHCN, where abrupt station-level shifts are plausible but not labeled. We therefore evaluate only held-out interpolation and forecasting MSE, against the NCDSSM-NL figure of 0.34. We also use MIMIC-III held-out value interpolation, making no claims about true events.

Finally, we repeat the $T$-scaling test from IEKS-ADMM with irregular timestamps up to $10^6$–$10^7$ observations. This confirms linear runtime and memory against batch convex solvers and against the fine-grid alternative.