Sample Complexity of Kalman Filtering for Unknown Systems

• URL: http://arxiv.org/abs/1912.12309v3
• Date: Wed, 13 May 2020 06:23:16 GMT
• Title: Sample Complexity of Kalman Filtering for Unknown Systems
• Authors: Anastasios Tsiamis, Nikolai Matni, George J. Pappas
• Abstract summary: 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. We show that when the system identification step produces sufficiently accurate estimates, a Certainty Equivalent (CE) KF enjoys provable sub-optimality guarantees.
• Score: 21.565920482293592
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 bounded by $\tilde O(1/\sqrt{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.

Related papers

• State Estimation and Control for Stochastic Quantum Dynamics with Homodyne Measurement: Stabilizing Qubits under Uncertainty [1.4811951486536687]
  This paper introduces a Lyapunov-based control approach with homodyne measurement. We study two filtering approaches: (i) the traditional quantum filtering and (ii) a modified version of the extended Kalman filtering.
  arXiv  Detail & Related papers  (2024-03-09T22:29:00Z)
• Closed-form Filtering for Non-linear Systems [83.91296397912218]
  We propose a new class of filters based on Gaussian PSD Models, which offer several advantages in terms of density approximation and computational efficiency. We show that filtering can be efficiently performed in closed form when transitions and observations are Gaussian PSD Models. Our proposed estimator enjoys strong theoretical guarantees, with estimation error that depends on the quality of the approximation and is adaptive to the regularity of the transition probabilities.
  arXiv  Detail & Related papers  (2024-02-15T08:51:49Z)
• System Identification for Continuous-time Linear Dynamical Systems [0.7510165488300368]
  Generalizing the learning of latent linear dynamical systems to continuous-time may extend the use of the hybrid Kalman filter. We apply the method by learning the parameters of a latent, multivariate Fokker-Planck SDE representing a toggle-switch genetic circuit.
  arXiv  Detail & Related papers  (2023-08-23T05:53:13Z)
• Learning the Kalman Filter with Fine-Grained Sample Complexity [4.301206378997673]
  We develop the first end-to-end sample complexity of model-free policy gradient (PG) methods in discrete-time infinite-horizon Kalman filtering. Our results shed light on applying model-free PG methods to control a linear dynamical system where the state measurements could be corrupted by statistical noises and other (possibly adversarial) disturbances.
  arXiv  Detail & Related papers  (2023-01-30T02:41:18Z)
• Robust Control for Dynamical Systems With Non-Gaussian Noise via Formal Abstractions [59.605246463200736]
  We present a novel controller synthesis method that does not rely on any explicit representation of the noise distributions. First, we abstract the continuous control system into a finite-state model that captures noise by probabilistic transitions between discrete states. We use state-of-the-art verification techniques to provide guarantees on the interval Markov decision process and compute a controller for which these guarantees carry over to the original control system.
  arXiv  Detail & Related papers  (2023-01-04T10:40:30Z)
• Formal Controller Synthesis for Markov Jump Linear Systems with Uncertain Dynamics [64.72260320446158]
  We propose a method for synthesising controllers for Markov jump linear systems. Our method is based on a finite-state abstraction that captures both the discrete (mode-jumping) and continuous (stochastic linear) behaviour of the MJLS. We apply our method to multiple realistic benchmark problems, in particular, a temperature control and an aerial vehicle delivery problem.
  arXiv  Detail & Related papers  (2022-12-01T17:36:30Z)
• Deep learning-enhanced ensemble-based data assimilation for high-dimensional nonlinear dynamical systems [0.0]
  Ensemble Kalman filter (EnKF) is a DA algorithm widely used in applications involving high-dimensional nonlinear dynamical systems. In this work, we propose hybrid ensemble Kalman filter (H-EnKF), which is applied to a two-layer quasi-geostrophic flow system as a test case.
  arXiv  Detail & Related papers  (2022-06-09T23:34:49Z)
• On optimization of coherent and incoherent controls for two-level quantum systems [77.34726150561087]
  This article considers some control problems for closed and open two-level quantum systems. The closed system's dynamics is governed by the Schr"odinger equation with coherent control. The open system's dynamics is governed by the Gorini-Kossakowski-Sudarshan-Lindblad master equation.
  arXiv  Detail & Related papers  (2022-05-05T09:08:03Z)
• Finite-time System Identification and Adaptive Control in Autoregressive Exogenous Systems [79.67879934935661]
  We study the problem of system identification and adaptive control of unknown ARX systems. We provide finite-time learning guarantees for the ARX systems under both open-loop and closed-loop data collection.
  arXiv  Detail & Related papers  (2021-08-26T18:00:00Z)
• Correct-by-construction reach-avoid control of partially observable linear stochastic systems [7.912008109232803]
  We formalize a robust feedback controller for reach-avoid control of discrete-time, linear time-invariant systems. The problem is to compute a controller that satisfies the required provestate abstraction problem.
  arXiv  Detail & Related papers  (2021-03-03T13:46:52Z)
• Learning Stabilizing Controllers for Unstable Linear Quadratic Regulators from a Single Trajectory [85.29718245299341]
  We study linear controllers under quadratic costs model also known as linear quadratic regulators (LQR) We present two different semi-definite programs (SDP) which results in a controller that stabilizes all systems within an ellipsoid uncertainty set. We propose an efficient data dependent algorithm -- textsceXploration -- that with high probability quickly identifies a stabilizing controller.
  arXiv  Detail & Related papers  (2020-06-19T08:58:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.