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:
- Industrial-Scale Forecasting: Matthias Seeger et al. demonstrated in Bayesian Intermittent Demand Forecasting for Large Inventories that non-Gaussian demand forecasting can be accelerated from cubic to linear time by mathematically reducing each Newton-Raphson step to a Kalman smoothing operation.
- Non-Linear Tracking: Simo Särkkä et al. showed in Levenberg-Marquardt and Line-Search Extended Kalman Smoothers that robust Levenberg-Marquardt and line-search extensions of the Extended Kalman Smoother (EKS) maintain this exact $O(T)$ efficiency while stabilizing convergence in highly non-linear tracking tasks.
- Probabilistic ODE Solvers: In the domain of probabilistic numerics, Filip Tronarp et al. proved in Bayesian ODE solvers: the maximum a posteriori estimate that the MAP trajectory of an ordinary differential equation can be computed efficiently using an iterative Kalman smoother acting as a Gauss-Newton optimizer.
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:
- Sparsity and Regularization: Rui Gao integrated the Iterated Extended Kalman Smoother (IEKS) with variable splitting in Iterated Extended Kalman Smoother-Based Variable Splitting for $L_1$-Regularized State Estimation to achieve $O(T)$ complexity for sparse state estimation. Similarly, Rui Gao et al. applied this to autonomous tracking in Autonomous Tracking and State Estimation With Generalized Group Lasso, reducing the primal update complexity from cubic to linear. In neuroimaging, Abbas Kazemipour et al. utilized $L_1$-regularized optimization within a recursive state-space framework in Efficient Estimation of Compressible State-Space Models with Application to Calcium Signal Deconvolution to perform linear-time neural spike tracking.
- Physical Constraints: Rui Gao et al. demonstrated in Variable Splitting Methods for Constrained State Estimation in Partially Observed Markov Processes that combining variable splitting with recursive Kalman smoothing allows constrained state estimation to scale linearly with time, preventing the memory exhaustion typical of batch solvers.
- Alternative Message Passing: Beyond standard smoothers, Yun-Peng Li et al. framed non-Gaussian state-space estimation as a combination of backward message passing and forward decision-making in Backward Filtering Forward Deciding in Linear Non-Gaussian State Space Models, achieving linear complexity for long-duration data with shape constraints.
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.