Sample Complexity of Kalman Filtering for Unknown Systems
\NameAnastasios Tsiamis* \NameNikolai Matni* \NameGeorge J. Pappas*
Abstract
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
中文速览
针对未知线性时不变系统，如何在只有有限观测数据的情况下设计一个可靠的卡尔曼滤波器（Kalman Filter），是控制与机器学习领域长期悬而未决的难题。研究者提出一个两步流程：先用子空间系统辨识方法从有限数据中估计出系统的状态空间参数和卡尔曼增益，再用这些估计参数设计滤波器；当估计误差较大、导致"确定性等价"滤波器（Certainty Equivalent KF）的特征值逼近单位圆、滤波器趋于不稳定时，额外施加鲁棒性约束来构造鲁棒卡尔曼滤波器。理论分析表明，无论是确定性等价滤波器还是鲁棒滤波器，其均方预测误差均以高概率被 $\tilde{O}(1/\sqrt{N})$ 界定，其中 $N$ 是系统辨识阶段采集的数据点数量。这是目前已知首个针对未知系统卡尔曼滤波的端到端样本复杂度保证，为在实际中安全地将数据驱动系统辨识与最优滤波设计相结合提供了坚实的理论基础。
原文 arXiv:1912.12309;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1912.12309v3