A Greedy Data Collection Scheme For Linear Dynamical Systems

Karim Cherifi, Pawan Goyal, Peter Benner

In the world of control theory and signal processing, building a mathematical model of a complex system—like a vibrating bridge or a high-speed circuit—is a foundational task. Traditionally, researchers collect massive amounts of data and then "compress" it into a model. But what if data collection is expensive, time-consuming, or physically difficult?

A new paper by Karim Cherifi, Pawan Goyal, and Peter Benner introduces a "greedy" scheme that flips the script. Instead of collecting data blindly, their algorithm adaptively picks the most informative measurement points one by one, building highly accurate models of linear dynamical systems with a fraction of the usual data.

TL;DR

This paper proposes an adaptive, greedy algorithm to select the most informative frequency points for learning linear dynamical systems. By focusing measurements where the model is most uncertain, it achieves high accuracy with significantly fewer data points than standard uniform sampling, even in the presence of noise.

What Problem Does This Paper Address?

To understand a system's behavior, engineers often use Linear Time-Invariant (LTI) models. These are typically learned from data in either the frequency domain (how the system responds to different vibrations) or the time domain (how the system responds to an input over time).

The standard approach is to sample data across a wide range of frequencies on a uniform or logarithmic grid. However, this is inefficient. Some frequency ranges (like a system's natural resonance peaks) contain vital information, while others are relatively "quiet." Collecting data in those quiet zones is a waste of resources.

Existing "optimal" sampling methods often require you to already have a high-fidelity model to guide the search—which is a "chicken and egg" problem. This paper aims to find those vital points in a purely data-driven way, without any prior knowledge of the system's internal complexity.

Methods

The authors leverage the Loewner Framework, a powerful mathematical tool for "data-to-model" realization. Their core innovation is a Greedy Selection Scheme:

  1. The Surrogate Error: Since the "true" system is unknown, the algorithm looks at the difference between the model at the current step ($H_k$) and the previous step ($H_{k-1}$). Where this difference is largest, the model is likely missing something important.
  2. The Mask Function: To prevent the algorithm from repeatedly sampling the same spot, they introduce a "mask function" (essentially a notch filter). This function "hides" already-sampled frequencies, forcing the algorithm to explore new parts of the frequency spectrum.
  3. Iterative Refinement: The algorithm identifies the frequency that maximizes this masked difference, takes a new measurement there, updates the model, and repeats until the model stops changing significantly.
  4. Time-Domain Extension: For systems where you can't measure frequency directly, the authors designed a specific input signal (a sum of sines and cosines) based on these greedy frequencies to extract the necessary information from time-series data.

Datasets

The methodology was validated using three well-known benchmarks in the systems and control community:

  • The Penzl Example: A large-scale model (order 1,006) used to test model reduction techniques.
  • The Beam Example: A model representing the vibrations of a physical beam, derived from discretized partial differential equations.
  • RLC Circuit: A 100-component electrical network consisting of resistors, inductors, and capacitors.

Key Insights and Ideas

  • Change as a Proxy for Knowledge: The "aha moment" here is that you don't need the ground truth to find informative points. The rate of change in the model's transfer function serves as a highly effective heuristic for where the "interesting" dynamics (like poles or resonances) are hidden.
  • Exploration vs. Exploitation: The mask function $g(\sigma)$ is the secret sauce. It balances the need to "exploit" areas of high model change while "exploring" the rest of the spectrum by zeroing out the influence of points we've already visited.
  • Minimalism: Theoretically, a system of order $n$ can be perfectly captured by $2n$ points. This greedy approach gets remarkably close to that theoretical limit in practice.

Key Results

  • Efficiency: In the Penzl example, the greedy scheme converged using only 24 interpolation points. A standard equidistant sampling approach with the same number of points resulted in a significantly higher error, failing to capture the system's sharp resonance peaks.
  • Superior Accuracy: Across all benchmarks, the "Adaptive Loewner" approach showed an $H_2$ error (a standard measure of model mismatch) that was several orders of magnitude lower than uniform sampling.
  • Noise Robustness: The authors tested the system with Gaussian white noise. Even with high noise levels ($\sigma = 10^{-4}$), the adaptive scheme remained robust, producing models that were much more reliable than those built from uniform data.

Limitations and Future Work

  • Heuristic Parameters: The mask function relies on two hyperparameters ($\beta$ and $\epsilon$). While the authors show the algorithm is relatively insensitive to small changes in these values, they still require some manual tuning.
  • Linearity Constraint: The current work is strictly limited to Linear Time-Invariant (LTI) systems. Extending this greedy logic to non-linear systems remains a significant challenge.
  • Experimental Feasibility: While the time-domain extension is promising, real-world hardware might have constraints on the types of input signals (like the sum-of-sines used here) that can be safely applied.

This research represents a significant step toward "smart" data collection, potentially saving engineers countless hours of experimental time by letting the math decide what to measure next.

Summary updated

Abstract

Mathematical models are essential to analyze and understand the dynamics of complex systems. Recently, data-driven methodologies have got a lot of attention which is leveraged by advancements in sensor technology. However, the quality of obtained data plays a vital role in learning a good and reliable model. Therefore, in this paper, we propose an efficient heuristic methodology to collect data both in the frequency domain and time-domain, aiming at the best possible information gain from limited experimental data. The efficiency of the proposed methodology is illustrated by means of several examples, and also, its robustness in the presence of noisy data is shown.
BibTeX
@misc{cherifi2021greedy,
  author = {Karim Cherifi and Pawan Goyal and Peter Benner},
  title = {{A Greedy Data Collection Scheme For Linear Dynamical Systems}},
  year = {2021},
  eprint = {2107.12950},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2107.12950},
}
Figure