Linear Time Sequential Inference via Recursive Smoothing

17 concepts13 papers1 proposal

When modeling time-series data, physical trajectories, or continuous-time dynamical processes, we often face a global optimization problem. Whether we are computing a Maximum A Posteriori (MAP) trajectory, fitting a Gaussian Process (GP), or regularizing a state-space model to find sparse anomalies, the traditional approach involves constructing a massive joint objective function over all $T$ time steps.

The mathematical bottleneck of this batch approach is severe: optimizing a global trajectory or inverting a dense covariance matrix scales cubically ($O(T^3)$) with the number of observations. For long-duration sequences, this cubic wall quickly leads to memory exhaustion and computational paralysis.

However, a powerful family of algorithms bypasses this bottleneck entirely, achieving a computational complexity that scales linearly ($O(T)$) with time. The secret lies in a profound realization: many complex, non-linear, non-Gaussian, and constrained optimization problems can be mathematically rewritten so that their core computational steps are solved using recursive state-space smoothers.

The Core Intuition: Exploiting Markovian Structure

Why can we optimize a global sequence in linear time? The answer lies in the Markov property. In a state-space model, the future is conditionally independent of the past given the current state. This conditional independence means that the joint probability distribution of the sequence factors into a chain of local transitions.

Instead of solving a massive, dense $T \times T$ system of equations all at once, we can pass messages sequentially through the chain. A forward pass (filtering) propagates information forward in time, and a backward pass (smoothing) propagates information backward to incorporate future observations. As shown by Paul Smith et al. in Computing MAP trajectories by representing, propagating and combining PDFs over groups, combining these sequential passes yields the globally optimal MAP trajectory in $O(T)$ time, completely avoiding the cubic cost of global batch optimization.

Mapping Optimization to Kalman Smoothing

The linear-time advantage of recursive smoothing is well-known for simple linear-Gaussian models via the classical Kalman filter and Rauch-Tung-Striebel (RTS) smoother. But how does this help when the system is highly non-linear or non-Gaussian?

The breakthrough comes from recognizing that standard iterative optimization algorithms—like Newton-Raphson, Gauss-Newton, or Levenberg-Marquardt—can have their inner loops mapped directly onto Kalman smoothing operations.

To maximize a non-Gaussian or non-linear posterior, an optimizer computes a sequence of local linear approximations (the gradient and Hessian). Crucially, because the underlying process is temporal, this Hessian matrix possesses a block-tridiagonal structure reflecting the Markovian dependencies. Instead of performing a standard matrix inversion on this Hessian, we can interpret the Newton-Raphson step as solving a synthetic linear-Gaussian smoothing problem.

This mathematical reduction has been successfully deployed across several domains:

Transforming Global Kernels into State Spaces

This connection opens up a way to scale up non-parametric methods like Gaussian Processes (GPs) and Latent Force Models (LFMs). Traditionally, GPs require computing a kernel matrix over all pairs of time steps, incurring a strict $O(T^3)$ cost.

However, many commonly used kernels (such as the Matérn family) can be viewed as the steady-state solutions to linear stochastic differential equations (SDEs). By converting the global kernel-based representation into an equivalent continuous-time state-space model, inference can be performed using sequential filtering and smoothing.

Kernel View:         [ Dense Covariance Matrix (T x T) ]  --> Requires O(T³) Inversion
                                    │
                        State-Space Reformulation
                                    ▼
State-Space View:    [ x₀ ] ──> [ x₁ ] ──> [ x₂ ] ──> [ x_T ] --> Solved via O(T) Smoothing

Jouni Hartikainen et al. leveraged this transformation in Sequential Inference for Latent Force Models to enable linear-time inference for models combining physical differential equations with GPs. This state-space reformulation has also been applied to physics-infused regression. For example, Filip Tronarp et al. introduced Fenrir: Physics-Enhanced Regression for Initial Value Problems, which casts parameter estimation in initial value problems as a sequential state-space problem to achieve linear scaling relative to the number of observations.

Handling Constraints and Sparsity via Variable Splitting

What happens when our trajectory optimization problem involves non-differentiable objectives, such as $L_1$-regularization for sparse spike detection, or hard physical constraints like preventing a vehicle from passing through a boundary?

To solve these problems without losing linear-time scaling, researchers combine recursive smoothers with variable splitting optimization techniques, such as the Alternating Direction Method of Multipliers (ADMM). Variable splitting works by breaking a complex optimization problem into smaller, decoupled subproblems that are solved iteratively.

Typically, one subproblem handles the non-differentiable constraint or regularizer locally (which is computationally cheap and can be done point-wise), while the other subproblem handles the global temporal consistency. Because the temporal subproblem retains its Markovian structure, it can be solved exactly and efficiently using a recursive Kalman smoother rather than a batch matrix inversion.

This combination has proven highly effective across several distinct problem domains:

Parameter Learning and Graph Topologies

The benefits of linear-time state estimation extend beyond tracking states to learning the underlying system parameters themselves. In the Expectation-Maximization (EM) algorithm, the "E-step" typically requires a full smoothing pass over the data, making each iteration scale linearly with $T$. To speed this up even further, James Martens developed the ASOS algorithm in Learning the Linear Dynamical System with ASOS, which restructures parameter estimation in Linear Dynamical Systems by pre-calculating data autocorrelations. Under steady-state assumptions, this makes the computational cost per EM iteration completely independent of the total number of time steps.

Furthermore, this linear-time framework scales to spatial-temporal problems, such as tracking processes over networks. Georgios B. Giannakis et al. integrated Rauch-Tung-Striebel smoothing into a joint topology and signal estimation framework in Semi-Blind Inference of Topologies and Dynamical Processes Over Dynamic Graphs, reducing the cost of tracking dynamic graph processes to be linear with respect to time.

The unifying theme across these diverse applications is that we do not need to sacrifice global optimality for computational speed. By recognizing the underlying Markovian structure of a time-series problem—whether it originates from an ODE, a Gaussian Process, or a physical trajectory—we can replace expensive, cubic-time batch matrix operations with elegant, linear-time recursive smoothing passes.

Key Foundational Work

Computing MAP trajectories by representing, propagating and combining PDFs over groups (2003) — contributed 1 concept elements to this direction.
Learning the Linear Dynamical System with ASOS (2010) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_linear_time_state_estimation_dfa343fa,
  title = {linear-time state estimation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/linear-time-state-estimation/rdr_dfa343faadef4d8ea2bf6bb3882fb105},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_linear_time_state_estimation_dfa343fa_v1,
  title = {linear-time state estimation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/linear-time-state-estimation/rdr_dfa343faadef4d8ea2bf6bb3882fb105/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake