High-dimensional dynamic systems identification with additional constraints

Junlin Li

TL;DR

This paper provides a new theoretical framework for identifying high-dimensional dynamic systems (where parameters outnumber data points) by assuming the underlying system matrices are low-rank. By using a clever repeated sampling strategy and nuclear norm minimization, the author proves that we can achieve exact system recovery in noiseless settings and highly accurate estimates in noisy ones, offering tighter error bounds than previous state-of-the-art methods.

What Problem Does This Paper Address?

In modern engineering and data science, we often try to model complex systems (like power grids or biological networks) where the number of variables (the "ambient dimension") is much larger than the number of observations we can collect. This is the "high-dimensional" challenge.

Standard statistical tools break down here because they overfit the data. To solve this, researchers usually assume the system has some hidden "simple" structure, such as being low-rank (meaning the system's behavior is driven by only a few underlying factors).

However, identifying dynamic systems (where the current state depends on the previous state) is harder than identifying static ones because the data points are not independent—they are linked across time. This paper aims to bridge the gap between low-rank matrix recovery theory and the messy, dependent nature of dynamic system data.

Methods

The author focuses on VARX models (Vector Auto-Regressive with eXogenous variables), which describe how a system's state changes based on its past and external inputs.

Key methodological steps include:

  1. Independent Repeated Sampling: To get around the problem of data dependency over time, the author proposes a scheme where the system is "reset" and sampled at a fixed time across multiple independent runs. This transforms the dynamic problem into a more manageable multivariate linear regression problem.
  2. Nuclear Norm Heuristics: Since minimizing the "rank" of a matrix is a computationally "NP-hard" problem, the paper uses the nuclear norm (the sum of singular values) as a convex proxy. This makes the optimization problem solvable using standard convex programming tools.
  3. New Theoretical Tools:
    • Weak Restricted Isometry Property (Weak RIP): A relaxed version of the standard RIP that allows for a wider range of measurement matrices (specifically "row-sub-Gaussian" matrices) while still guaranteeing recovery.
  4. Operator-norm Curvature Condition: A new condition for the loss function in noisy scenarios that leads to sharper error bounds.

Datasets

This is a theoretical paper focused on mathematical proofs and statistical consistency. Consequently, it does not use empirical datasets or specific benchmarks. Instead, it defines the performance of the algorithm based on general classes of random matrices (Gaussian, Bernoulli, and sub-Gaussian) that represent system inputs and noise.

Key Insights and Ideas

  • Breaking the Dependency: The "aha moment" is the formalization of the repeated sampling scheme. By looking at a specific "moment" across many independent trials, the author creates a measurement matrix where the rows are independent, allowing the use of powerful tools from random matrix theory.
  • Weak RIP is Enough: Most previous work relied on the strict Restricted Isometry Property (RIP). The author shows that a "Weak RIP"—which allows for a gap between the upper and lower bounds of the matrix transformation—is sufficient for exact recovery in the noiseless case.
  • Stronger Error Bounds: In the noisy case, the author proves an error bound based on the operator norm rather than the more common Frobenius norm. The paper argues this provides a "sharper" and more meaningful guarantee for how well the estimated system matrix matches the true one.

Key Results

  • Exact Recovery (Noiseless): In the absence of noise, the low-rank system matrix can be recovered exactly with high probability from a finite number of samples, specifically on the order of $\Omega((m+n)r)$, where $r$ is the rank and $m, n$ are system dimensions.
  • Sharp Error Bounds (Noisy): In noisy environments, the error of the estimate (in terms of the operator norm) scales as $O(\sqrt{(m+n)/N})$, where $N$ is the number of samples.
  • Sample Efficiency: The results show that the required sample size depends on the "degrees of freedom" of the low-rank structure, not the massive ambient dimension of the system.

Limitations and Future Work

  • The "Reset" Requirement: The repeated sampling scheme assumes you can reset a dynamic system to its initial state and run it again multiple times. In many real-world scenarios (like economics or climate science), you only get one continuous "trajectory" of data, making this specific sampling scheme difficult to apply.
  • Computational Complexity: While nuclear norm minimization is convex and "tractable," it can still be slow for extremely large-scale matrices compared to simpler methods like least squares.
  • Future Directions: The author suggests extending this work to systems that are simultaneously low-rank and sparse, which would cover even more complex real-world structures. Additionally, the paper briefly notes that these results can be generalized from VARX(1) to higher-order VARX(d) models.

Summary updated

Abstract

This note presents a unified analysis of the identification of dynamical systems with low-rank constraints under high-dimensional scaling. This identification problem for dynamic systems is challenging due to the intrinsic dependency of the data. To alleviate this problem, we first formulate this identification problem into a multivariate linear regression problem with a row-sub-Gaussian measurement matrix using the more general input designs and the independently repeated sampling schemes. We then propose a nuclear norm heuristic method that estimates the parameter matrix of a dynamic system from a few input-state data samples. Based on this, we can extend the existing results. In this article, we consider two scenarios. (i) In the noiseless scenario, nuclear-norm minimization is introduced for promoting low-rank. We define the notion of weak restricted isometry property, which is weaker than the ordinary restricted isometry property, and show it holds with high probability for the row-sub-Gaussian measurement matrix. Thereby, the rank-minimization matrix can be exactly recovered from a finite number of data samples. (ii) In the noisy scenario, a regularized framework involving the nuclear norm penalty is established. We give the notion of operator norm curvature condition for the loss function and show it holds for the row-sub-Gaussian measurement matrix with high probability. Consequently, when specifying the suitable choice of the regularization parameter, the operator norm error of the optimal solution of this program has a sharp bound given a finite amount of data samples. This operator norm error bound is always smaller than the ordinary Frobenius norm error bound obtained in the existing work.
BibTeX
@inproceedings{li2020high,
  author = {Junlin Li},
  title = {{High-dimensional dynamic systems identification with additional constraints}},
  booktitle = {Communication},
  year = {2020},
  doi = {10.1080/03610926.2020.1836219},
}
Figure