Finite Sample Analysis of Stochastic System Identification
Anastasios Tsiamis ⋆ and George J. Pappas The authors are with the Department of Electrical and Systems Engineering, University of Pennsylvania, Philadelphia, PA 19104. Emails:
Abstract
In this paper, we analyze the finite sample complexity of stochastic system identification using modern tools from machine learning and statistics. An unknown discrete-time linear system evolves over time under Gaussian noise without external inputs. The objective is to recover the system parameters as well as the Kalman filter gain, given a single trajectory of output measurements over a finite horizon of length $N$ . Based on a subspace identification algorithm and a finite number of $N$ output samples, we provide non-asymptotic high-probability upper bounds for the system parameter estimation errors. Our analysis uses recent results from random matrix theory, self-normalized martingales and SVD robustness, in order to show that with high probability the estimation errors decrease with a rate of $1/\sqrt{N}$ . Our non-asymptotic bounds not only agree with classical asymptotic results, but are also valid even when the system is marginally stable.
中文速览
随机系统辨识（stochastic system identification）长期依赖渐近理论，无法回答"有限个数据时误差究竟有多大"这一实际问题。针对无外部输入、仅由噪声驱动的线性系统，本文借助随机矩阵理论、自归一化鞅和SVD鲁棒性等现代统计工具，对一类基于最小二乘的子空间辨识算法进行了首次有限样本分析，给出了系统矩阵A、C以及卡尔曼滤波增益K估计误差的高概率非渐近上界。结果表明，即使系统处于边际稳定（marginal stability，谱半径≤1）的更一般情形，估计误差也能以1/√N的速率收敛（至多差一个对数因子），与经典渐近结论吻合但适用范围更广。这项工作填补了随机子空间辨识领域有限样本理论的空白，为在有限数据条件下可靠地学习预测模型和设计卡尔曼滤波器提供了理论保障。
原文 arXiv:1903.09122;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1903.09122v1