Understanding linear systems with noisy data from single runs
Learning Linear Systems under Heavy-Tailed Noise: A Non-Asymptotic Analysis from A Single Trajectory
Machine Learning
Summary
Measuring how systems change over time can be tricky when the data collected is noisy or unusual. This paper explains how to estimate these changes reliably using a single long observation, even when the noise behaves unpredictably. The authors provide clear bounds on how much data is needed for a good estimate, depending on the noise's characteristics. They also offer a general method that works with different types of noise and extend their findings to models with external inputs.
What this means in practice
- •For control engineers: Estimate system dynamics from limited and noisy operational data to tune controllers more accurately under challenging noise conditions.
- •For signal processing teams: Improve parameter estimation in time series models where noise shows heavy tails or bursts from a single data sequence.
Authors
Xiaomian Yang, Sungho Shin
Abstract
We establish non-asymptotic sample complexity bounds for the least-squares estimation of vector autoregressive models for exponentially stable systems with heavy-tailed noise based on a single observed trajectory. By assuming i.i.d. noise, bounded noise covariance, and persistent excitation, we show that the estimation error is $\widetilde{\mathcal{O}}(r^{1/2}T^{-1/2+1/p})$ under bounded $p$th moment for $p > 2$, where $T$ is the number of samples, $r$ is the noise dimension, and $\widetilde{\mathcal{O}}(\cdot)$ hides logarithmic terms. We also introduce a unifying approach to sample complexity analysis applicable to broad classes of noise distributions and showcase this by deriving error bounds for sub-exponential and sub-Gaussian noise distributions. Finally, we specialize our analysis to autoregressive models with exogenous inputs and show that the dimension factor of the error bound is independent of the model order.