Abstract
This paper presents a unified analysis of the identification of dynamical systems with low-rank constraints under high-dimensional scaling. Identifying dynamic systems is inherently challenging due to the temporal dependency of data. To address this, we formulate the identification problem as a multivariate linear regression problem with a row-sub-Gaussian measurement matrix using general input designs and independent repeated sampling schemes. We propose a nuclear norm heuristic method to estimate the parameter matrix from limited input-state data samples. In the noiseless scenario, we introduce the "weak restricted isometry property" (Weak RIP) and demonstrate that it holds with high probability, allowing for exact rank-minimization recovery. In the noisy scenario, we establish a regularized framework and introduce the operator norm curvature condition. We prove that the resulting operator norm error bound is sharper than the standard Frobenius norm bounds found in existing literature.
1. Introduction
In modern engineering and data science, modeling complex systems—such as power grids, biological networks, or financial markets—often involves high-dimensional variables where the number of parameters significantly exceeds the number of available observations. Standard statistical tools typically fail in these "high-dimensional" regimes because they tend to overfit the data. To mitigate this, researchers often assume the underlying system possesses a hidden "simple" structure, most commonly a low-rank property, implying that the system's behavior is governed by a small number of latent factors.
However, identifying dynamic systems (e.g., where the current state is a function of the previous state) is significantly more complex than identifying static ones. In dynamic systems, data points are not independent; they are linked across time. This paper bridges the gap between low-rank matrix recovery theory and the dependent nature of dynamic system data by introducing a novel theoretical framework for Vector Auto-Regressive with eXogenous variables (VARX) models.
2. Methodology
2.1 Independent Repeated Sampling
To overcome the challenge of temporal data dependency, the proposed method utilizes an independent repeated sampling scheme. Instead of observing a single long trajectory, the system is "reset" and sampled at a fixed time across multiple independent runs. This strategy transforms the dynamic identification problem into a multivariate linear regression problem with a measurement matrix where the rows are independent. This allows for the application of powerful tools from random matrix theory, specifically those involving row-sub-Gaussian matrices.
2.2 Nuclear Norm Heuristics
Directly minimizing the rank of a matrix is an NP-hard problem. To make the optimization computationally tractable, this paper employs the nuclear norm (the sum of singular values) as a convex proxy for the rank. This transformation allows the identification problem to be solved efficiently using standard convex programming tools.
3. Theoretical Contributions
3.1 The Weak Restricted Isometry Property (Weak RIP)
In the noiseless scenario, the paper introduces the notion of the Weak Restricted Isometry Property. While the standard RIP is often too restrictive for many practical measurement matrices, the Weak RIP allows for a gap between the upper and lower bounds of the matrix transformation. The author proves that this property holds with high probability for row-sub-Gaussian measurement matrices, ensuring that the low-rank system matrix can be recovered exactly from a finite number of samples.
3.2 Operator-Norm Curvature and Noisy Recovery
For noisy environments, the paper establishes a regularized framework involving a nuclear norm penalty. A key contribution is the definition of the "operator norm curvature condition" for the loss function. By showing this condition holds for row-sub-Gaussian matrices, the author derives an error bound for the optimal solution in terms of the operator norm.
Crucially, this operator norm error bound is shown to be "sharper" and more meaningful than the Frobenius norm bounds common in previous work, providing a tighter guarantee on the fidelity of the estimated system matrix.
4. Key Results and Efficiency
- Exact Recovery: In noiseless settings, the system matrix can be recovered exactly with a sample complexity on the order of $\Omega((m+n)r)$, where $r$ is the rank and $m, n$ are the system dimensions.
- Sharp Error Bounds: In noisy settings, the operator norm error scales as $O(\sqrt{(m+n)/N})$, where $N$ is the number of samples.
- Sample Efficiency: The results demonstrate that the required sample size depends on the "degrees of freedom" of the low-rank structure rather than the massive ambient dimension of the system, making it highly efficient for high-dimensional applications.
5. Discussion and Limitations
While the theoretical results are robust, the practical application of the repeated sampling scheme requires the ability to reset a dynamic system to its initial state. This may be difficult in fields like climate science or macroeconomics where only a single continuous trajectory is available. Furthermore, while nuclear norm minimization is convex, it remains more computationally intensive than simple least-squares methods for extremely large-scale matrices.
Future research directions include extending these results to systems that are simultaneously low-rank and sparse, as well as generalizing the framework from VARX(1) to higher-order VARX(d) models to capture more complex temporal dependencies.
Summary updated