Numerical Methods
Data Assimilation and Kalman Filter
Цели урока
- Derive the Kalman filter update equations from Bayesian inference and implement them for a linear system
- Extend to nonlinear systems with the Extended and Unscented Kalman Filters
- Apply the Ensemble Kalman Filter (EnKF) and 4D-Var for large-scale geophysical data assimilation
- Implement a particle filter for non-Gaussian state estimation and compare its cost with Kalman variants
Предварительные знания
- nm-10
- nm-27
Data assimilation fuses imperfect model predictions with imperfect observations to produce the best possible state estimate. Every weather forecast, spacecraft trajectory correction, autonomous robot localization, and financial time-series model relies on some form of this machinery.
- ECMWF's operational 4D-Var assimilation ingests ~10 million observations per day - satellite radiances, radiosondes, aircraft reports - to initialize global weather forecasts
- NASA's Mars rover Curiosity uses an Extended Kalman Filter for wheel odometry fusion with IMU data to maintain localization accuracy on rough terrain
- Tesla and Waymo autonomous vehicles use sensor fusion via Unscented Kalman Filters combining LiDAR, radar, camera, and GPS at 100 Hz
- COVID-19 epidemiological models used EnKF to assimilate hospitalization and case count data, providing real-time estimates of the reproduction number R_t
History of Data Assimilation and Kalman Filter
1960: Rudolph Kalman publishes 'A New Approach to Linear Filtering and Prediction Problems' - one of the most cited engineering papers ever. 1961: Kalman-Bucy extend the filter to continuous-time systems; NASA adopts it for Apollo navigation computer. 1993: Evensen proposes the Ensemble Kalman Filter, making data assimilation tractable for large geophysical models
Kalman Filter: Optimal Linear State Estimation
The Kalman filter solves the optimal linear state estimation problem: given a linear dynamical system with Gaussian noise and noisy measurements, it computes the minimum-variance unbiased estimate of the hidden state at each time step. It operates in two alternating phases - predict (propagate state forward using the model) and update (correct using new observations).
The continuous-time version (Kalman-Bucy filter) satisfies a matrix Riccati ODE for the covariance. The steady-state covariance solves the algebraic Riccati equation (ARE), which can be computed once for time-invariant systems.
For a linear-Gaussian state-space model x_k = F x_{k-1} + w_k, z_k = H x_k + v_k, why is the Kalman filter optimal (minimum-variance unbiased estimator) rather than just one of many possible filters?
Gaussian conjugacy is the deep reason behind the Kalman recursions, and it is also why every practical extension (EKF, UKF, EnKF, 4D-Var) tries to preserve a Gaussian-like posterior. When the linearity or Gaussian assumptions break, particle filters become the fallback at significant cost.
Extended and Unscented Kalman Filters for Nonlinear Systems
Real systems are rarely linear. The Extended Kalman Filter (EKF) linearizes the dynamics and measurement functions around the current estimate using Jacobians, then applies standard Kalman equations. The Unscented Kalman Filter (UKF) avoids Jacobians entirely by propagating a carefully chosen set of sigma points through the nonlinear functions.
For a nonlinear dynamical system, what is the key algorithmic difference between EKF and UKF, and why does UKF capture more of the nonlinearity?
UKF earns its accuracy by passing the actual nonlinear function over a deterministic sample set rather than a derivative approximation. This is the practical pattern for robotic sensor fusion and avionics where Jacobians are messy and runtime budgets are tight.
Ensemble Kalman Filter and 4D-Var for Meteorology
Operational weather forecasting involves state vectors of size 10^8 to 10^9 (grid values over the globe). Full covariance matrices are computationally infeasible. The Ensemble Kalman Filter (EnKF) approximates the covariance from a Monte Carlo ensemble of N model runs (typically N = 50-100). The 4D-Var method instead minimizes a cost function over a time window, implicitly propagating the full error covariance through the adjoint model.
Operational weather assimilation uses state vectors of size n ~ 10^9. The Ensemble Kalman Filter (EnKF) succeeds where the classical KF cannot. What is the storage trick and what is the corresponding price?
Implicit covariance via an ensemble is the only way to fit operational weather assimilation in memory. Localization is then mandatory to suppress sampling noise, and combined with hybrid 4D-Var these are the methods running at ECMWF, NOAA, and JMA today.
Particle Filter for Non-Gaussian State Estimation
Kalman variants assume Gaussian distributions. For highly nonlinear systems or non-Gaussian noise - such as robot localization with multi-modal posteriors, or fault detection with discrete-state switching - particle filters represent the state distribution as a weighted sample set and propagate it through arbitrary nonlinear models.
Particle filters work well in low dimensions (< 20 state variables). In high dimensions, exponentially many particles are needed to cover the state space - making SIR impractical for geophysical applications. Gaussian mixture filters, implicit particle filters, and localized variants address this.
A particle filter approximates the posterior with weighted samples. What signals weight degeneracy, and what is the standard fix?
Effective sample size is the diagnostic that tells you when the particle cloud has collapsed onto a degenerate set. Resampling restores diversity, which is why SIR is the workhorse for robot localization and target tracking in low to moderate state dimensions.
Related Topics
The Kalman smoother (backward pass) is mathematically equivalent to the adjoint sensitivity method for ODEs (nm-25): both propagate sensitivity information backward through a dynamical system
- 4D-Var Adjoint Gradient — Related topic
- Ensemble Covariance and Randomized SVD — Related topic
- Sequential UQ and Particle Filters — Related topic
Key Takeaways
- The Kalman filter solves optimal linear Gaussian state estimation via predict-update cycles; the Kalman gain balances model and measurement uncertainty
- EKF linearizes nonlinear dynamics via Jacobians; UKF propagates sigma points through the exact nonlinear function, achieving higher accuracy without analytical derivatives
- EnKF approximates the covariance from N ensemble members - reducing storage from O(n^2) to O(Nn) - enabling DA for 10^9-dimensional geophysical models
- Particle filters handle arbitrary non-Gaussian distributions but suffer curse-of-dimensionality; SIR with resampling prevents weight degeneracy in low dimensions
Вопросы для размышления
- A GPS navigation system has measurement noise R = 10 m^2 and initial position uncertainty P = 100 m^2. Compute the Kalman gain K = P/(P+R) and the updated variance P_updated. Interpret physically what K=0.9 means for the balance between GPS and prior.
- The Lorenz-63 attractor has a Lyapunov exponent of ~0.9. Estimate how quickly an ensemble of 50 particles with initial spread of 0.01 diverges, and why this sets a minimum ensemble refresh rate for EnKF.
- Describe the key difference between 4D-Var and EnKF in how they represent the background error covariance B. Under what conditions (ensemble size, model complexity, observation density) is each method preferable?