# Sample Complexity of Kalman Filtering for Unknown Systems

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Dec 2019.

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

- [Streaming Linear System Identification with Reverse Experience Replay](https://mlsanity.com/paper/2103.05896/) (2021)
- [Can Transformers Learn Optimal Filtering for Unknown Systems?](https://mlsanity.com/paper/2308.08536/) (2023)
- [Learning Mixtures of Linear Dynamical Systems](https://mlsanity.com/paper/2201.11211/) (2022)
- [Provable Sim-to-real Transfer in Continuous Domain with Partial Observations](https://mlsanity.com/paper/2210.15598/) (2022)
- [Smoothed Online Learning for Prediction in Piecewise Affine Systems](https://mlsanity.com/paper/2301.11187/) (2023)
- [Oracle-Efficient Smoothed Online Learning for Piecewise Continuous Decision Making](https://mlsanity.com/paper/2302.05430/) (2023)
- [Time varying regression with hidden linear dynamics](https://mlsanity.com/paper/2112.14862/) (2021)
- [Fairness in Forecasting of Observations of Linear Dynamical Systems](https://mlsanity.com/paper/2209.05274/) (2022)
- [Adversarially Robust Stability Certificates can be Sample-Efficient](https://mlsanity.com/paper/2112.10690/) (2021)
- [Safe Linear-Quadratic Dual Control with Almost Sure Performance Guarantee](https://mlsanity.com/paper/2103.13278/) (2021)
- [Dynamic Structure Estimation from Bandit Feedback using Nonvanishing Exponential Sums](https://mlsanity.com/paper/2206.00861/) (2022)
- [Spatial Context or Memory? Sizing the Inputs of Neural Surrogates for Partially Observed Fields](https://mlsanity.com/paper/2610.12723/) (2026)

## Abstract (arXiv)

In this paper, we consider the task of designing a Kalman Filter (KF) for an unknown and partially observed autonomous linear time invariant system driven by process and sensor noise. To do so, we propose studying the following two step process: first, using system identification tools rooted in subspace methods, we obtain coarse finite-data estimates of the state-space parameters and Kalman gain describing the autonomous system; and second, we use these approximate parameters to design a filter which produces estimates of the system state. We show that when the system identification step produces sufficiently accurate estimates, or when the underlying true KF is sufficiently robust, that a Certainty Equivalent (CE) KF, i.e., one designed using the estimated parameters directly, enjoys provable sub-optimality guarantees. We further show that when these conditions fail, and in particular, when the CE KF is marginally stable (i.e., has eigenvalues very close to the unit circle), that imposing additional robustness constraints on the filter leads to similar sub-optimality guarantees. We further show that with high probability, both the CE and robust filters have mean prediction error bounded by tilde O(1/√N), where N is the number of data points collected in the system identification step. To the best of our knowledge, these are the first end-to-end sample complexity bounds for the Kalman Filtering of an unknown system.