# Kalman Filtering with Adversarial Corruptions

arXiv: https://arxiv.org/abs/2111.06395 · HTML: https://mlsanity.com/paper/2111.06395/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 57 references that are in the map.
- First posted on arXiv 11 Nov 2021.

## Builds on (most cited first, 22 of 22)

- [Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification](https://mlsanity.com/paper/1802.08334/) (2018)
- [Agnostic Estimation of Mean and Covariance](https://mlsanity.com/paper/1604.06968/) (2016)
- [Learning from Untrusted Data](https://mlsanity.com/paper/1611.02315/) (2016)
- [Being Robust (in High Dimensions) Can Be Practical](https://mlsanity.com/paper/1703.00893/) (2017)
- [Improper Learning for Non-Stochastic Control](https://mlsanity.com/paper/2001.09254/) (2020)
- [Mixture Models, Robustness, and Sum of Squares Proofs](https://mlsanity.com/paper/1711.07454/) (2017)
- [Efficient Algorithms for Outlier-Robust Regression](https://mlsanity.com/paper/1803.03241/) (2018)
- [List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians](https://mlsanity.com/paper/1711.07211/) (2017)
- [Robust Linear Regression: Optimal Rates in Polynomial Time](https://mlsanity.com/paper/2007.01394/) (2020)
- [Robustly Learning a Gaussian: Getting Optimal Error, Efficiently](https://mlsanity.com/paper/1704.03866/) (2017)
- [Optimal Robust Linear Regression in Nearly Linear Time](https://mlsanity.com/paper/2007.08137/) (2020)
- [Settling the Robust Learnability of Mixtures of Gaussians](https://mlsanity.com/paper/2011.03622/) (2020)
- [Outlier-robust estimation of a sparse linear model using ℓ1-penalized Huber's M-estimator](https://mlsanity.com/paper/1904.06288/) (2019)
- [Robustly Learning any Clusterable Mixture of Gaussians](https://mlsanity.com/paper/2005.06417/) (2020)
- [Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination](https://mlsanity.com/paper/2010.04157/) (2020)
- [Online Learning of the Kalman Filter with Logarithmic Regret](https://mlsanity.com/paper/2002.05141/) (2020)
- [Outlier-Robust Clustering of Non-Spherical Mixtures](https://mlsanity.com/paper/2005.02970/) (2020)
- [Local Statistics, Semidefinite Programming, and Community Detection](https://mlsanity.com/paper/1911.01960/) (2019)
- [Learning without Concentration for General Loss Functions](https://mlsanity.com/paper/1410.3192/) (2014)
- [Sum-of-squares proofs and the quest toward optimal algorithms](https://mlsanity.com/paper/1404.5236/) (2014)
- [Rounding Sum-of-Squares Relaxations](https://mlsanity.com/paper/1312.6652/) (2013)
- [ERM and RERM are optimal estimators for regression problems when malicious outliers corrupt the labels](https://mlsanity.com/paper/1910.10923/) (2019)

## Built on by (most cited first, 6 of 6)

- [Planning in Observable POMDPs in Quasipolynomial Time](https://mlsanity.com/paper/2201.04735/) (2022)
- [A New Approach to Learning Linear Dynamical Systems](https://mlsanity.com/paper/2301.09519/) (2023)
- [Learning Mixtures of Linear Dynamical Systems](https://mlsanity.com/paper/2201.11211/) (2022)
- [SQ Lower Bounds for Learning Single Neurons with Massart Noise](https://mlsanity.com/paper/2210.09949/) (2022)
- [Computation-Utility-Privacy Tradeoffs in Bayesian Estimation](https://mlsanity.com/paper/2603.18254/) (2026)
- [Adversarially-Robust Inference on Trees via Belief Propagation](https://mlsanity.com/paper/2404.00768/) (2024)

## Abstract (arXiv)

Here we revisit the classic problem of linear quadratic estimation, i.e. estimating the trajectory of a linear dynamical system from noisy measurements. The celebrated Kalman filter gives an optimal estimator when the measurement noise is Gaussian, but is widely known to break down when one deviates from this assumption, e.g. when the noise is heavy-tailed. Many ad hoc heuristics have been employed in practice for dealing with outliers. In a pioneering work, Schick and Mitter gave provable guarantees when the measurement noise is a known infinitesimal perturbation of a Gaussian and raised the important question of whether one can get similar guarantees for large and unknown perturbations. In this work we give a truly robust filter: we give the first strong provable guarantees for linear quadratic estimation when even a constant fraction of measurements have been adversarially corrupted. This framework can model heavy-tailed and even non-stationary noise processes. Our algorithm robustifies the Kalman filter in the sense that it competes with the optimal algorithm that knows the locations of the corruptions. Our work is in a challenging Bayesian setting where the number of measurements scales with the complexity of what we need to estimate. Moreover, in linear dynamical systems past information decays over time. We develop a suite of new techniques to robustly extract information across different time steps and over varying time scales.