A finite-sample bound for identifying partially observed linear switched systems from a single trajectory

• URL: http://arxiv.org/abs/2503.13766v1
• Date: Mon, 17 Mar 2025 23:02:22 GMT
• Title: A finite-sample bound for identifying partially observed linear switched systems from a single trajectory
• Authors: Daniel Racz, Mihaly Petreczky, Balint Daroczy,
• Abstract summary: We derive a finite-sample probabilistic bound on the parameter estimation error of a system identification algorithm for Linear Switched Systems.<n>Our bound guarantees statistical consistency under the assumption that the true system exhibits quadratic stability.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We derive a finite-sample probabilistic bound on the parameter estimation error of a system identification algorithm for Linear Switched Systems. The algorithm estimates Markov parameters from a single trajectory and applies a variant of the Ho-Kalman algorithm to recover the system matrices. Our bound guarantees statistical consistency under the assumption that the true system exhibits quadratic stability. The proof leverages the theory of weakly dependent processes. To the best of our knowledge, this is the first finite-sample bound for this algorithm in the single-trajectory setting.

Related papers

• A Non-Asymptotic Theory of Seminorm Lyapunov Stability: From Deterministic to Stochastic Iterative Algorithms [15.764613607477887]
  We study the problem of solving fixed-point equations for seminorm-contractive operators. We establish the non-asymptotic behavior of iterative algorithms in both deterministic and foundational settings.
  arXiv  Detail & Related papers  (2025-02-20T02:39:37Z)
• An Iterative Bayesian Approach for System Identification based on Linear Gaussian Models [86.05414211113627]
  We tackle the problem of system identification, where we select inputs, observe the corresponding outputs from the true system, and optimize the parameters of our model to best fit the data. We propose a flexible and computationally tractable methodology that is compatible with any system and parametric family of models.
  arXiv  Detail & Related papers  (2025-01-28T01:57:51Z)
• Exact Recovery Guarantees for Parameterized Non-linear System Identification Problem under Adversarial Attacks [16.705631360131886]
  We study the system identification problem for parameterized non-linear systems using basis functions under adversarial attacks. Motivated by the LASSO-type estimators, we analyze the exact recovery property of a non-smooth estimator. This is the first study on the sample complexity analysis of a non-smooth estimator for the non-linear system identification problem.
  arXiv  Detail & Related papers  (2024-08-30T22:12:57Z)
• A Catalyst Framework for the Quantum Linear System Problem via the Proximal Point Algorithm [9.804179673817574]
  We propose a new quantum algorithm for the quantum linear system problem (QLSP) inspired by the classical proximal point algorithm (PPA) Our proposed method can be viewed as a meta-algorithm that allows inverting a modified matrix via an existing texttimattQLSP_solver. By carefully choosing the step size $eta$, the proposed algorithm can effectively precondition the linear system to mitigate the dependence on condition numbers that hindered the applicability of previous approaches.
  arXiv  Detail & Related papers  (2024-06-19T23:15:35Z)
• A Unified Theory of Stochastic Proximal Point Methods without Smoothness [52.30944052987393]
  Proximal point methods have attracted considerable interest owing to their numerical stability and robustness against imperfect tuning. This paper presents a comprehensive analysis of a broad range of variations of the proximal point method (SPPM)
  arXiv  Detail & Related papers  (2024-05-24T21:09:19Z)
• A least-square method for non-asymptotic identification in linear switching control [17.938732931331064]
  It is known that the underlying partially-observed linear dynamical system lies within a finite collection of known candidate models. We characterize the finite-time sample complexity of this problem by leveraging recent advances in the non-asymptotic analysis of linear least-square methods. We propose a data-driven switching strategy that identifies the unknown parameters of the underlying system.
  arXiv  Detail & Related papers  (2024-04-11T20:55:38Z)
• Discretize Relaxed Solution of Spectral Clustering via a Non-Heuristic Algorithm [77.53604156112144]
  We develop a first-order term to bridge the original problem and discretization algorithm. Since the non-heuristic method is aware of the original graph cut problem, the final discrete solution is more reliable.
  arXiv  Detail & Related papers  (2023-10-19T13:57:38Z)
• Identifiability and Asymptotics in Learning Homogeneous Linear ODE Systems from Discrete Observations [114.17826109037048]
  Ordinary Differential Equations (ODEs) have recently gained a lot of attention in machine learning. theoretical aspects, e.g., identifiability and properties of statistical estimation are still obscure. This paper derives a sufficient condition for the identifiability of homogeneous linear ODE systems from a sequence of equally-spaced error-free observations sampled from a single trajectory.
  arXiv  Detail & Related papers  (2022-10-12T06:46:38Z)
• Robust online joint state/input/parameter estimation of linear systems [0.0]
  This paper presents a method for jointly estimating the state, input, and parameters of linear systems in an online fashion. The method is specially designed for measurements that are corrupted with non-Gaussian noise or outliers.
  arXiv  Detail & Related papers  (2022-04-12T09:41:28Z)
• Data-Driven Reachability Analysis from Noisy Data [5.949143454441281]
  We consider the problem of computing reachable sets directly from noisy data without a given system model. Several reachability algorithms are presented, and their accuracy is shown to depend on the underlying system generating the data.
  arXiv  Detail & Related papers  (2021-05-15T14:11:57Z)
• Understanding Implicit Regularization in Over-Parameterized Single Index Model [55.41685740015095]
  We design regularization-free algorithms for the high-dimensional single index model. We provide theoretical guarantees for the induced implicit regularization phenomenon.
  arXiv  Detail & Related papers  (2020-07-16T13:27:47Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  Maximum a posteriori (MAP) inference in discrete-valued random fields is a fundamental problem in machine learning. Due to the difficulty of this problem, linear programming (LP) relaxations are commonly used to derive specialized message passing algorithms. We present randomized methods for accelerating these algorithms by leveraging techniques that underlie classical accelerated gradient.
  arXiv  Detail & Related papers  (2020-07-01T18:43:32Z)

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.