Data Driven Estimation of Stochastic Switched Linear Systems of Unknown Order

Tuhin Sarkar, Alexander Rakhlin, Munther A. Dahleh

Abstract

We address the problem of learning the parameters of a mean square stable switched linear systems (SLS) with unknown latent space dimension, or order, from its noisy input--output data. In particular, we focus on learning a good lower order approximation of the underlying model allowed by finite data. Motivated by subspace-based algorithms in system theory, we construct a Hankel-like matrix from finite noisy data using ordinary least squares. Such a formulation circumvents the non-convexities that arise in system identification, and allows for accurate estimation of the underlying SLS as data size increases. Since the model order is unknown, the key idea of our approach is model order selection based on purely data dependent quantities. We construct Hankel-like matrices from data of dimension obtained from the order selection procedure. By exploiting tools from theory of model reduction for SLS, we obtain suitable approximations via singular value decomposition (SVD) and show that the system parameter estimates are close to a balanced truncated realization of the underlying system with high probability.

Introduction

Identifying Stochastic Switched Linear Systems (SLS) is a fundamental challenge in control theory and robotics. These systems model complex behaviors that switch between different linear regimes, such as a drone changing flight modes or financial indices reacting to market shifts. However, two major hurdles typically impede identification: the unknown "true" dimension (order) of the hidden state and the non-convex nature of traditional optimization-based identification methods.

This paper introduces a provably efficient framework to learn a high-fidelity, low-order approximation of an SLS from finite, noisy input-output data without prior knowledge of the system's true dimension.

Methodology: Subspace-Based Identification

The proposed approach avoids iterative optimization by leveraging subspace-based algorithms and model reduction theory. The process involves three primary stages:

  1. Hankel Matrix Construction: A "Hankel-like" matrix is built using entries estimated via Ordinary Least Squares (OLS) from noisy observations. Unlike Linear Time-Invariant (LTI) systems, the SLS Hankel matrix dimensions grow exponentially with the rollout length, capturing the diverse possible switching sequences.
Data collection from $N_S$ independent trajectories of the Switched Linear System.
  1. Data-Dependent Model Selection: To handle the unknown order, the algorithm employs a novel selection rule. This rule balances estimation error (noise from finite samples) against truncation error (loss of dynamics from simplification), determining the optimal "effective" size for the Hankel matrix.
  2. Balanced Truncation via SVD: Singular Value Decomposition (SVD) is applied to the estimated Hankel matrix to extract system parameters ($C, \{A_i\}, B$). This yields a "balanced truncated realization," providing the most informative low-order summary of the potentially high-dimensional underlying system.

Key Insights: Effective Order and Model Reduction

A central theme of this work is the distinction between "true order" and "effective order." In practical scenarios with finite data, the true order may be unidentifiable due to noise. Instead, the framework seeks the best approximation supported by the current signal-to-noise ratio.

Approximation framework: Relating the true system $M$ to the data-driven estimate $\hat{M}_r(T)$.

The theoretical framework ensures that the data-driven estimate $\hat{M}_r(T)$ converges toward a balanced truncated version of the true system $M$. Notably, the authors show that when the number of modes is reduced to one ($s=1$), their derived error rates align perfectly with optimal rates known for standard LTI systems, demonstrating that this framework is a robust generalization of classical theory.

Results and Performance

The efficacy of the method is validated through rigorous mathematical proofs and synthetic examples:

  • Consistency: The finite-time estimator for the Hankel matrix is proven to be consistent, converging to the true system as the number of samples ($N_S$) increases.
  • Error Bounds: High-probability bounds on parameter estimation error are provided, scaling approximately with $\tilde{O}(N_S^{-\Delta_s/2})$, where $\Delta_s$ is a stability-related constant.
  • Subspace Recovery: Using a variant of Wedin’s Theorem, the algorithm successfully recovers the "principal subspace" of the system dynamics, ensuring that the low-order model captures essential physical behaviors.

Conclusion and Future Directions

While this framework provides a strong foundation for SLS identification, several avenues for future research remain. Currently, the method assumes the system's "mode" is observable at each time step. Future extensions could address hidden switches, such as those found in Markov Jump Linear Systems or state-dependent switching. Integrating clustering algorithms may eventually allow for the identification of systems where the switch sequence is entirely unobserved.

Summary updated

Abstract

We address the problem of learning the parameters of a mean square stable switched linear systems (SLS) with unknown latent space dimension, or \textit{order}, from its noisy input--output data. In particular, we focus on learning a good lower order approximation of the underlying model allowed by finite data. Motivated by subspace-based algorithms in system theory, we construct a Hankel-like matrix from finite noisy data using ordinary least squares. Such a formulation circumvents the non-convexities that arise in system identification, and allows for accurate estimation of the underlying SLS as data size increases. Since the model order is unknown, the key idea of our approach is model order selection based on purely data dependent quantities. We construct Hankel-like matrices from data of dimension obtained from the order selection procedure. By exploiting tools from theory of model reduction for SLS, we obtain suitable approximations via singular value decomposition (SVD) and show that the system parameter estimates are close to a balanced truncated realization of the underlying system with high probability.
BibTeX
@inproceedings{sarkar2019data,
  author = {Tuhin Sarkar and Alexander Rakhlin and Munther A. Dahleh},
  title = {{Data Driven Estimation of Stochastic Switched Linear Systems of Unknown Order}},
  booktitle = {CDC},
  year = {2019},
  doi = {10.1109/cdc40024.2019.9030173},
}
Figure