System identification for the bar model: Algorithms, consistency and sample complexity

System identification has been extensively studied in the context of linear state-space models with continuous state variables. In this thesis, we focus on system identification problems in dynamical systems where the state takes values in a discrete set. If the state vector has p components and each component of the vector can take on two values, then the number of possible states is 2^p, thus leading to a combinatorial explosion in the number of parameters to be identified. To overcome this difficulty, we consider a recently introduced structured dynamical system model, called the Bernoulli Autoregressive (BAR) Model, which consists of (p^2+p) parameters. For this model, we first consider two estimators of the system parameters: a maximum likelihood (ML) estimator and a variant of the ML estimator which leads to closed-form expressions for the estimated parameters. We prove that both of these estimators are consistent in the sense that the estimates converge to the true parameter values when the number of observations goes to infinity. Then, we consider the sample complexity of the closed-form estimator. Using concentration results for random matrices and Lipschitz functions, we derive a bound on the probability that the estimates deviate from the true parameter values by a certain amount, and use the bound to show that the sample complexity is polynomial in p. Finally, building upon the tools used to study the closed-form estimator, we derive new concentration inequalities for vector-valued Lipschitz functions of Markov processes and use them to improve sample complexity results for other estimation problems beyond the BAR model.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Industrial Engineering

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2022

Author dc:creator

• Xie, Xiaotian

Contributors dc:contributor

• Beck, Carolyn L.
• Srikant, Rayadurgam
• Sowers, Richard B.
• Varshney, Lav R.
• Katselis, Dimitrios

• System identification
• Network inference
• Sample complexity
• Concentration inequalities

Statement dc:rights

• Copyright 2022 Xiaotian Xie

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/115520

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F115520