An official website of the United States government
Learning a dynamical system from input/output data is a fundamental task in the control design pipeline. In the partially observed setting there are two components to identification: parameter estimation to learn the Markov parameters, and system realization to obtain a state space model. In both sub-problems it is implicitly assumed that standard numerical algorithms such as the singular value decomposition (SVD) can be easily and reliably computed. When trying to fit a high-dimensional model to data, even computing an SVD may be intractable. In this work we show that an approximate matrix factorization obtained using randomized methods can replace the standard SVD in the realization algorithm while maintaining the finite-sample performance and robustness guarantees of classical methods.
more »
« less
This content will become publicly available on May 22, 2026
Finite Sample Identification of Partially Observed Bilinear Dynamical Systems
We consider the problem of learning a realization of a partially observed bilinear dynamical system (BLDS) from noisy input-output data. Given a single trajectory of input-output samples, we provide an algorithm and a finite time analysis for learning the system’s Markov-like parameters, from which a balanced realization of the bilinear system can be obtained. The stability of BLDS depends on the sequence of inputs used to excite the system. Moreover, our identification algorithm regresses the outputs to highly correlated, nonlinear, and heavy-tailed covariates. These properties, unique to partially observed bilinear dynamical systems, pose significant challenges to the analysis of our algorithm for learning the unknown dynamics. We address these challenges and provide high probability error bounds on our identification algorithm under a uniform stability assumption. Our analysis provides insights into system theoretic quantities that affect learning accuracy and sample complexity. Lastly, we perform numerical experiments with synthetic data to reinforce these insights.
more »
« less
- PAR ID:
- 10632235
- Editor(s):
- Ozay, N; Balzano, L; Panagou, D; Abate, A
- Publisher / Repository:
- Proceedings of Machine Learning Research
- Date Published:
- Volume:
- 238
- Page Range / eLocation ID:
- 1271-1285
- Format(s):
- Medium: X
- Location:
- Ann Arbor, MI
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Function approximation from input and output data pairs constitutes a fundamental problem in supervised learning. Deep neural networks are currently the most popular method for learning to mimic the input-output relationship of a general nonlinear system, as they have proven to be very effective in approximating complex highly nonlinear functions. In this work, we show that identifying a general nonlinear function y = ƒ(x1,…,xN) from input-output examples can be formulated as a tensor completion problem and under certain conditions provably correct nonlinear system identification is possible. Specifically, we model the interactions between the N input variables and the scalar output of a system by a single N-way tensor, and setup a weighted low-rank tensor completion problem with smoothness regularization which we tackle using a block coordinate descent algorithm. We extend our method to the multi-output setting and the case of partially observed data, which cannot be readily handled by neural networks. Finally, we demonstrate the effectiveness of the approach using several regression tasks including some standard benchmarks and a challenging student grade prediction task.more » « less
-
Bilinear dynamical systems are ubiquitous in many different domains and they can also be used to approximate more general control-affine systems. This motivates the problem of learning bilinear systems from a single trajectory of the system’s states and inputs. Under a mild marginal meansquare stability assumption, we identify how much data is needed to estimate the unknown bilinear system up to a desired accuracy with high probability. Our sample complexity and statistical error rates are optimal in terms of the trajectory length, the dimensionality of the system and the input size. Our proof technique relies on an application of martingale small-ball condition. This enables us to correctly capture the properties of the problem, specifically our error rates do not deteriorate with increasing instability. Finally, we show that numerical experiments are well-aligned with our theoretical results.more » « less
-
null (Ed.)We consider abstraction-based design of output-feedback controllers for dynamical systemswith a finite set of inputs and outputs against specifications in linear-time temporal logic. The usual procedure for abstraction-based controller design (ABCD) first constructs a finite-state abstraction of the underlying dynamical system, and second, uses reactive synthesis techniques to compute an abstract state-feedback controller on the abstraction. In this context, our contribution is two-fold: (I) we define a suitable relation between the original systemand its abstractionwhich characterizes the soundness and completeness conditions for an abstract state-feedback controller to be refined to a concrete output-feedback controller for the original system, and (II) we provide an algorithm to compute a sound finite-state abstraction fulfilling this relation. Our relation generalizes feedback-refinement relations fromABCD with state-feedback. Our algorithm for constructing sound finitestate abstractions is inspired by the simultaneous reachability and bisimulation minimization algorithm of Lee and Yannakakis. We lift their idea to the computation of an observation-equivalent system and show how sound abstractions can be obtained by stopping this algorithm at any point. Additionally, our new algorithm produces a realization of the topological closure of the input/output behavior of the original system if it is finite state realizable.more » « less
-
Estimating central aortic blood pressure is important for cardiovascular health and risk prediction purposes. Cardiovascular system is a multi-channel dynamical system that yields multiple blood pressures at various body sites in response to central aortic blood pressure. This paper concerns the development and analysis of an observer-based approach to de-convolution of unknown input in a class of coprime multi-channel systems applicable to non-invasive estimation of central aortic blood pressure. A multi-channel system yields multiple outputs in response to a common input. Hence, the relationship between any pair of two outputs constitutes a hypothetical input-output system with unknown input embedded as a state. The central idea underlying our approach is to derive the unknown input by designing an observer for the hypothetical input-output system. In this paper, we developed an unknown input observer (UIO) for input de-convolution in coprime multi-channel systems. We provide a universal design algorithm as well as meaningful physical insights and inherent performance limitations associated with the algorithm. The validity and potential of our approach was illustrated using a case study of estimating central aortic blood pressure waveform from two non-invasively acquired peripheral arterial pulse waveforms. The UIO could reduce the root-mean-squared error associated with the central aortic blood pressure by up to 27.5% and 28.8% against conventional inverse filtering and peripheral arterial pulse scaling techniques.more » « less
