Minimal Order Recovery through Rank-adaptive Identification

Frédéric Zheng, Yassir Jedra, Alexandre Proutière

Abstract

System identification for Linear Time-Invariant (LTI) systems traditionally requires prior knowledge of the system order to handle noisy data effectively. This paper introduces Thresholded Ho-Kalman, a rank-adaptive algorithm that utilizes Universal Singular Value Thresholding (USVT) to identify system parameters and order simultaneously from finite-sample data. We demonstrate that this approach achieves statistical error bounds comparable to an oracle with known order, providing a robust framework for identification in the finite-sample regime.

Introduction

In control theory and signal processing, system identification involves constructing mathematical models of dynamic systems from observed input-output data. For LTI systems, the Ho-Kalman algorithm is a foundational tool that utilizes the Hankel matrix to recover internal state-space parameters. However, in practical scenarios characterized by noise, the standard Ho-Kalman algorithm requires the system order ($n$)—the dimension of the internal state—to be known a priori.

Most existing literature either assumes this order is given or focuses on asymptotic guarantees that only hold as the sample size approaches infinity. This work addresses the finite-sample regime, exploring how much data is required to correctly estimate the system order and build an accurate model without prior structural information.

Methodology: Thresholded Ho-Kalman

The proposed Thresholded Ho-Kalman algorithm follows a two-step identification process:

  1. Initial Estimation: A standard Least-Squares approach is used to obtain a noisy estimate of the Hankel matrix. Due to noise, this empirical matrix typically appears full-rank, obscuring the true underlying system complexity.
  2. Universal Singular Value Thresholding (USVT): To denoise the estimate, the algorithm applies a threshold ($\xi$). Singular values below this threshold are discarded, effectively filtering out noise and retaining only the significant signal components.
  3. Rank Adaptation: The number of singular values exceeding $\xi$ defines the estimated system order. This "cleaned" matrix is then processed through the Ho-Kalman pipeline to extract the Markov parameters ($A, B, C$).

The threshold $\xi$ is mathematically derived based on the noise level and sample size, balancing the risk of over-modeling noise against the risk of under-modeling the system's true dynamics.

Key Results and Discussion

The effectiveness of the Thresholded Ho-Kalman algorithm was validated through synthetic numerical experiments on a stable system with order $n=5$, 3 inputs, and 2 outputs.

Convergence of the estimated system rank to the true order (n=5) as sample size T increases.

As shown in the experiments, the algorithm successfully recovers the true system order as the number of samples ($T$) increases. Specifically, the estimated rank converges toward the true order of $n=5$, reaching it reliably as $T$ approaches 6,000 samples.

Comparison of estimation error between the proposed Thresholded Ho-Kalman and the Oracle (Known order) method.

A critical finding is that the "blind" thresholding approach achieves performance parity with the "Known Order" oracle. As illustrated in the error plots, the Frobenius norm of the parameter estimation error for the Thresholded Ho-Kalman algorithm tracks closely with the oracle method. Even in the low-sample regime where the order is slightly underestimated, the algorithm avoids overfitting, eventually converging to the oracle's performance as more data is collected. This suggests that there is no significant statistical penalty for not knowing the system order beforehand.

Conclusion

Thresholded Ho-Kalman provides a principled way to perform system identification without prior knowledge of system complexity. By leveraging USVT, the algorithm adapts to the "effective rank" of the data, avoiding overfitting in high-noise or low-data scenarios.

Future work aims to refine the thresholding bounds, which currently remain somewhat conservative for multiple-trajectory settings. Additionally, establishing the absolute lower bounds for identification error in partially observed systems remains an open challenge in the field.

Summary updated

BibTeX
@inproceedings{zheng2025minimal,
  author = {Frédéric Zheng and Yassir Jedra and Alexandre Proutière},
  title = {{Minimal Order Recovery through Rank-adaptive Identification}},
  booktitle = {CDC},
  year = {2025},
  doi = {10.1109/cdc57313.2025.11312165},
}
Figure