PaperlayerView exact revision on arXiv

Source-linked AI summary

Generalized Kalman Smoothing: Modeling and Algorithms

A. Y. Aravkin, J. V. Burke, L. Ljung, A. Lozano, G. Pillonetto

arXiv:1609.06369v2math.OCstat.ML

TL;DR

Classical quadratic smoothers can be vulnerable to outliers and unable to track impulsive disturbances. This survey connects smoothing to optimization and reviews more general models and algorithms; it presents a convex formulation encompassing varied cases under mild assumptions.

  • Problem

    Classical quadratic smoothers can be vulnerable to measurement outliers and unable to track impulsive disturbances or abrupt state changes.

    Source: §1 · p. 3

  • Method

    The survey develops a generalized MAP and convex-optimization perspective for dynamic models, reviewing modeling choices and algorithms for smoothing.

    Source: §1 · pp. 2–3

  • Results

    The survey presents a general formulation that contains varied smoothing settings as special cases and remains convex under mild, natural assumptions.

    Source: §6 · p. 23

  • Takeaways & Limitations

    The optimization viewpoint gives control and signal-processing communities freedom to develop modeling and inference frameworks for dynamical systems.

    Source: §1 · p. 2

    Nonlinear process and measurement models are outside the survey’s scope because they require solving a nonconvex problem.

    Source: §1.2 · p. 5

Abstract

from arXiv · show

State-space smoothing has found many applications in science and engineering. Under linear and Gaussian assumptions, smoothed estimates can be obtained using efficient recursions, for example Rauch-Tung-Striebel and Mayne-Fraser algorithms. Such schemes are equivalent to linear algebraic techniques that minimize a convex quadratic objective function with structure induced by the dynamic model. These classical formulations fall short in many important circumstances. For instance, smoothers obtained using quadratic penalties can fail when outliers are present in the data, and cannot track impulsive inputs and abrupt state changes. Motivated by these shortcomings, generalized Kalman smoothing formulations have been proposed in the last few years, replacing quadratic models with more suitable, often nonsmooth, convex functions. In contrast to classical models, these general estimators require use of iterated algorithms, and these have received increased attention from control, signal processing, machine learning, and optimization communities. In this survey we show that the optimization viewpoint provides the control and signal processing community great freedom in the development of novel modeling and inference frameworks for dynamical systems. We discuss general statistical models for dynamic systems, making full use of nonsmooth convex penalties and constraints, and providing links to important models in signal processing and machine learning. We also survey optimization techniques for these formulations, paying close attention to dynamic problem structure. Modeling concepts and algorithms are illustrated with numerical examples.

1 Introduction

The introduction motivates moving beyond classical quadratic smoothing, which can be vulnerable to measurement outliers and unable to track impulsive disturbances or abrupt state changes. The survey connects classical smoothing algorithms to optimization and reviews generalized models and algorithms for dynamic inference.

1 Introduction

  • Quadratic penalties can leave impulsive state changes poorly tracked, while quadratic data-misfit losses are vulnerable to outliers.The DC motor examples illustrate poor impulse reconstruction and unsatisfactory output estimates even when the measurement variance is correctly specified.Source: §1 · p. 3, §1.1 · pp. 3, 5

1.1 DC motor example

  • The DC motor examples show L2-opt underestimating the largest disturbance peak and averaging the output when measurement variance is high.The optimal linear estimate uses only noise means and covariances; knowing the true variance does not make its reconstruction satisfactory in the outlier setting.Source: §1.1 · pp. 3, 5

1.2 Scope of the survey

  • The survey links classical smoothers to optimization and reviews generalized models, convex-analysis foundations, and first- and second-order solution methods.Its scope includes modeling process disturbances and measurement errors with general convex functions and incorporating state constraints; nonlinear process and measurement models are excluded because they require nonconvex optimization.Source: §1.2 · p. 5

2 Kalman smoothing, block tridiagonal systems and classical schemes

The section embeds the state sequence and related model data in a structured linear-algebra formulation. It shows how classical smoothing schemes efficiently solve the resulting block-tridiagonal system.

2 Kalman smoothing, block tridiagonal systems and classical schemes

  • The state sequence, measurements, covariance matrices, and initial conditions are embedded in data structures that yield an efficient formulation of the smoothing problem.The resulting linear system has a positive-definite symmetric block-tridiagonal operator.Source: §2 · p. 6
  • The smoothing solution is obtained by solving a positive-definite symmetric block-tridiagonal linear system.The system is defined by block matrices and vectors in the formulation.Source: §2 · p. 6
  • The RTS and Mayne-Fraser schemes both solve the Kalman smoothing problem by efficiently solving the block-tridiagonal system.RTS corresponds to a forward-backward algorithm, while Mayne-Fraser uses two filters running in parallel.Source: §2 · p. 6

3 General formulations: convex losses and penalties, and statistical properties of the resulting estimators

The section generalizes Gaussian least-squares smoothing to convex formulations with flexible measurement losses, process-noise penalties, and state constraints. These choices let the model reflect prior knowledge about disturbances and measurement errors.

3 General formulations: convex losses and penalties, and statistical properties of the resulting estimators

  • The general formulation combines a feasible state domain, measurement-discrepancy loss, and process-transition penalty, with the latter two linked to error and disturbance densities.The regularization parameter γ controls the tradeoff between measurement fit and process-noise modeling and must be tuned from data.Source: §3 · p. 7

3.1 General functions J for modeling process noise

  • For impulsive process disturbances, the ℓ0 penalty counts nonzero components, while the convex ℓ1 relaxation encourages sparse disturbances.The ℓ0 formulation is nonconvex and NP-hard; ℓ1 offers a tractable alternative.Source: §3.1 · pp. 7–8
  • For nearly perfectly correlated impulsive disturbances, elastic net can recover the whole group, whereas ℓ1 alone usually selects one member.When disturbances are grouped by time point, the mixed ℓ2,1 penalty models their joint presence or absence.Source: §3.1 · p. 8

3.2 General functions V to model measurement errors

  • The Huber loss combines quadratic behavior for small measurement errors with absolute-value growth for larger errors, guarding against outliers without sparsifying residuals.By contrast, the ℓ1 measurement loss sparsifies residuals and can fit some data exactly.Source: §3.2 · p. 9
  • The ε-insensitive loss ignores residual fluctuations within a noise-floor radius, while its ε parameter marks the scale below which the signal cannot be resolved.The penalty is described as robust to minor fluctuations below the floor and to large outliers.Source: §3.2 · p. 9
  • Convex losses provide global-minimum guarantees, but redescending influence for extreme residuals requires sublinear growth and therefore excludes convex losses.The Student’s t penalty is contrasted with Gaussian and Laplace penalties in its tail and influence behavior.Source: §3.2 · pp. 9–10, Figure 5 · p. 10

3.3 Incorporating Constraints

  • State constraints can encode nonnegativity, known bounds, monotonicity, and unimodality; the treatment restricts the feasible set to convex cases.The paper focuses on polyhedral sets and sets with simple projection operators.Source: §3.3 · p. 10

4 Efficient algorithms for Kalman smoothing

This section surveys smooth and nonsmooth convex optimization methods for Kalman smoothing, including gradient, Newton, proximal, splitting, and interior-point approaches. It develops splitting algorithms and PLQ-based interior-point methods, whose computational costs and convergence rates depend on the formulation and regularity assumptions.

4.1 Convex sets and functions

  • Convexity basics connect closed convex functions and convex hulls, while PLQ penalties support impulsive-disturbance, robust-measurement, and dynamic-SVR models.Source: §4.1 · p. 11

4.2 Smooth case: first- and second-order methods

  • For least-squares smoothing, steepest descent fractionally reduces objective value and solution distance per iteration, while Newton converges quadratically near a solution.Locally, Newton iterations double the number of correct digits and require only a few steps to reach machine precision.Source: §4.2 · p. 12

4.3 Nonsmooth case: subgradient descent

  • Subgradient descent can converge extremely slowly: its best provable error-bound rate is limited, although suitable square-summable, nonsummable step sizes close the optimality gap.Source: §4.3 · p. 13

4.4 Proximal gradient methods and accelerations

  • Proximal-gradient methods exploit the additive structure of smooth and nonsmooth terms, achieving O(1/κ) for convex functions and faster accelerated rates.When the smooth term is strongly convex, the rate is O((1 −α/β)κ); proximal operators for many nonsmooth functions take O(n) or O(nlogn) time.Source: §4.4 · p. 13

4.5 Splitting methods

  • For robust smoothing with isolated measurement outliers, composing the nonsmooth 1-norm with a general linear operator makes proximal-gradient evaluation impractical, motivating primal-dual splitting methods.Source: §4.5 · p. 15
  • Each ADMM ℓ1-smoother iteration costs O(n^2N) after an initial O(n^3N) factorization investment.The fixed least-squares system can be factorized once and reused across iterations.Source: §4.5 · pp. 15–16
  • Chambolle–Pock requires implementable proximity operators and converges at O(1/κ), with O(1/κ^2) acceleration under specific regularity assumptions.For general nonsmooth Kalman formulations, splitting schemes achieve at best O(1/κ^2); faster rates require stronger assumptions such as primal or dual smoothness.Source: §4.5 · p. 16

4.6 Formulations Using Piecewise Linear Quadratic (PLQ) Penalties [96]

  • PLQ formulations cover a broad class of penalties and polyhedral constraints, enabling second-order smoothing methods at O(n^3N) cost for moderate state size.The class includes quadratic, absolute-value, Huber, Vapnik, Huber-insensitive, and elastic-net penalties.Source: §4.6 · pp. 16–17

4.7 Interior point (second-order) methods for PLQ functions

  • Conjugate-PLQ interior-point iterations cost O(N(n^3 + m^3)), scale linearly with N, and often converge superlinearly or quadratically locally.Damped Newton iterations solve a relaxed KKT system while driving its homotopy parameter toward zero.Source: §4.7 · pp. 17–18

5 Numerical experiments and illustrations

The numerical examples compare optimization algorithms for nonsmooth smoothing and illustrate robust penalties and domain constraints on signal-tracking and DC-motor problems.

5.1 Algorithms and convergence rates

  • CP-V2 reaches 10^-10 objective-gap accuracy in 300 iterations, while IPsolve finishes in 27 iterations; subgradient is very slow and CP-V1 needs 50,000 iterations.CP-V2 uses one reusable factorization; IPsolve has super-linear convergence but solves linear systems at each iteration.Source: §5.1 · p. 19, Figure 6 · p. 20

5.2 DC motor: robust solutions using ℓ1 losses and penalties

  • In the DC-motor impulsive-input example, LASSO-CV recovers the disturbance and outperforms L2-opt, with a 200-run study supporting its effectiveness.The boxplots compare fits from L2-opt and LASSO-CV.Source: Figure 7 · p. 20, §5.2 · p. 21, Figure 8 · p. 21
  • With output-measurement outliers, the ℓ1-loss smoother is robust, while without outliers it has nearly identical fit performance to the optimal linear smoother.The no-outlier comparison uses 200 runs; L2-nom and L2-opt coincide in that setting.Source: §5.2 · p. 21, Figure 9 · p. 22, Figure 10 · p. 22

5.3 Modeling with PLQ using IPsolve

  • For contaminated measurements, Huber fits better than unconstrained L2, cL2 improves on L2, and cHuber gives the best fit by eliminating Huber constraint violations at 3 and 6 seconds.The comparison uses four smoothers, with and without domain constraints.Source: §5.3 · p. 22, Figure 11 · p. 23

6 Concluding remarks

The survey organizes diverse state-estimation models around a general convex optimization formulation. It presents this viewpoint as a tutorial connecting state estimation with convex optimization.

6 Concluding remarks

  • Formulation (15) contains varied state-estimation situations as special cases of its functions V and J.The survey presents this as a general framework for a large literature.Source: §6 · p. 23
  • Under mild and natural assumptions, formulation (15) remains a convex optimization problem.Source: §6 · p. 23
  • The survey treats convex optimization techniques as tools for state estimation and as a tutorial perspective on the subject.Source: §6 · p. 23

Appendix A1. Optimization viewpoint on Kalman smoothing under correlated noise and singular covariances

The appendix extends the Gaussian smoothing optimization viewpoint to correlated noises and singular covariance matrices.

Appendix A1. Optimization viewpoint on Kalman smoothing under correlated noise and singular covariances

A2. Convex analysis and optimization

The appendix reviews convex analysis and optimization concepts used in developing and analyzing the paper’s general smoothing formulation.

A2. Convex analysis and optimization

Fundamental objects in convex analysis

The section develops convex-analysis tools—including duality, separation, subgradients, conjugates, and PLQ calculus—that support algorithm design and sensitivity analysis.

Convex duality

The section constructs primal-dual formulations through a Lagrangian and states conditions for strong duality and attainment. It illustrates these results with sparsity-promoting formulations.

  • The Lagrangian recovers the primal objective by maximizing over dual variables and the dual objective by minimizing over primal variables.Source: Convex duality · p. 26
  • The dual maximizes −f*(w)−g*(v) subject to K^T w+v=0, and can be simplified by eliminating v and reversing sign.Source: Convex duality · p. 26
  • Weak duality gives a nonnegative gap, while strong duality requires additional constraint qualifications; the Fenchel–Rockafellar theorem supplies relative-interior conditions.Source: Convex duality · p. 26
  • When both relative-interior conditions hold, the primal and dual attain finite optimal values with zero duality gap.Source: Convex duality · p. 26
  • The three sparsity-promoting formulation variants in Table 1 all satisfy strong duality.Source: Table 1 · p. 27

Related papers

Loading 1609.06369v2…