Source-linked AI summary
Finite Sample Analysis of Stochastic System Identification
Anastasios Tsiamis, George J. Pappas
TL;DR
The paper asks how accurately stochastic linear systems can be identified from a finite output trajectory when no external inputs are available. It analyzes a subspace-identification procedure with high-probability finite-sample bounds, showing O(1/√N) rates up to logarithmic factors even for marginally stable systems.
Problem
The paper addresses finite-sample identification of partially observed linear systems driven only by noise, including estimation of the system parameters and Kalman filter gain.
Method
The method uses least-squares regression followed by a balanced-realization subspace step, with finite-sample analysis of the Hankel-like matrix estimate.
Results
O(1/√N) up to logarithmic factors is achieved for marginally stable systems, and the paper provides finite-sample guarantees for system and Kalman gain estimation.
Takeaways & Limitations
The bounds extend finite-sample stochastic system-identification guarantees to systems without inputs and to the marginally stable regime.
Takeaways & Limitations
The SVD-based realization requires a sufficiently large singular-value gap, which can make its robustness condition restrictive in practice.
Abstract
from arXiv · showhide
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.
1 Introduction
This paper addresses finite-sample stochastic system identification without external inputs, extending guarantees to system and Kalman gain estimation under marginal stability. It uses subspace identification and establishes high-probability learning rates supported by persistence of excitation.
- Research gap: Prior subspace-identification analyses were largely asymptotic and assumed asymptotic stability, leaving finite-sample guarantees and marginal stability unresolved.Earlier finite-sample results commonly assumed external inputs or fully observed states.
- Problem: The paper studies stochastic system identification without external inputs, where systems are driven only by noise and persistence of excitation is harder to establish.It targets finite-sample estimation of A, C, and the Kalman filter gain.
- Contributions: The paper provides the first finite-sample upper bounds for stochastic identification without inputs and the first finite-sample guarantees for Kalman filter gain estimation.These guarantees concern the estimation errors of the system parameters and Kalman gain.
- Contributions: The authors prove that system outputs satisfy persistence of excitation in finite time with high probability.This supports subspace methods that use outputs as regressors.
- Results: O(1/√N) up to logarithmic factors is achieved for marginally stable systems, while stable-system rates agree with classical asymptotic results.The marginal-stability regime is defined by ρ(A) ≤ 1, whereas stable systems satisfy ρ(A) < 1.
2 Problem formulation
The paper formulates stochastic system identification for marginally stable linear systems driven only by Gaussian noise, estimating A, C, and the Kalman filter gain from finite output data. It seeks high-probability finite-sample error bounds while accounting for similarity-transform ambiguity and a steady-state Kalman filter assumption.
- Model and assumptions: The system has state x_k and output y_k, with Gaussian process and measurement noises and unknown A, C, Q, R, and initial covariance.The model sets B and D to zero, so there are no external inputs.
- Model and assumptions: The analysis assumes known system order, marginal stability ρ(A) ≤1, observability of (A, C), controllability of (A, Q^1/2), and positive-definite R.These conditions are stated as the standing assumptions for the paper.
- Kalman filter: The steady-state Kalman filter is defined through the Riccati-equation solution P, with its state equal to the minimum mean square error prediction.The paper assumes Σ_0 = P so the filter has converged to steady state; general Σ_0 is left for future work.
- Estimation objective: A, C, and K can only be estimated up to an invertible similarity transformation because output sequences are invariant under equivalent state-space representations.The finite-sample problem asks for bounds on the transformed estimation errors with probability at least 1 −δ.
- Estimation objective: The paper analyzes a least-squares subspace identification algorithm for finite output samples in the no-input stochastic setting.This setting is described as more challenging because excitation must come from noise rather than external inputs.
3 Subspace Identification Algorithm
The identification algorithm first estimates a Hankel-like future-from-past output map by least squares, then obtains a balanced state-space realization through rank-n factorization and structural recovery. The finite-sample analysis separately bounds regression error and studies realization robustness.
- Least-squares regression: The algorithm regresses future outputs on past outputs to estimate a Hankel-like matrix that factors into observability and controllability components.The regression uses finite past and future horizons p and f, with residual structure and truncation bias analyzed explicitly.
- Least-squares regression: The estimated Hankel matrix represents a truncated Kalman filter mapping past outputs directly to future outputs, so its estimate is data-driven.Persistence of excitation, expressed through invertibility of the past-output regressor matrix, is required to compute the least-squares estimate.
- Balanced realization: A balanced realization is formed by rank-n factorization of the estimated Hankel matrix using its singular value decomposition.The realization is one among potentially infinitely many state-space representations.
- Balanced realization: The recovered observability and controllability factors yield estimates of C and K, while the shift structure of observability determines A.The construction requires known order n and full-rank controllability factors; otherwise accurate observability recovery is impossible.
- Finite-sample analysis: The finite-sample analysis first bounds ∥G − Ĝ∥_2 in the regression step and then analyzes robustness of the balanced realization step.This two-part structure connects statistical regression guarantees to parameter-recovery guarantees.
4 Finite Sample Analysis of Regression
The regression analysis derives high-probability finite-sample bounds for estimating the Hankel-like matrix from one noisy output trajectory. It explains persistence of excitation, separates cross-term error from Kalman truncation bias, and obtains rates that remain valid for marginally stable systems.
- Regression error bound: Theorem 1 provides high-probability upper bounds for the Hankel-like matrix estimation error under sufficiently large sample sizes.The guarantee applies when N exceeds thresholds N0, N1, and N2, with probability at least 1 − δN − 6δ.
- Error decomposition: The regression error contains a cross-term error and a Kalman filter truncation bias term.Consistency requires the truncation term to vanish as N grows.
- Error decomposition: Choosing p = c log N makes the truncation bias decrease exponentially and at least as quickly as the cross-term error.With this choice, the cross-term becomes the dominant contribution to the bound.
- Statistical rates: For marginally stable systems, the finite-sample analysis provides a rate up to logarithmic factors, while asymptotically stable systems recover a corresponding logarithmic-factor rate.The marginally stable result addresses a setting for which previous subspace performance bounds were unavailable, and the asymptotically stable bound is consistent with prior asymptotic analysis.
- Noise trade-off: Noise creates a trade-off in stochastic identification: larger noise improves output excitation but worsens least-squares convergence.The bound captures both effects through its dependence on the noise-related terms.
- Persistence of excitation: The analysis proves finite-time persistence of excitation for past outputs and noises with high probability.This property is fundamental because subspace algorithms use past outputs as regressors; in the no-input setting, noise is the source of excitation.
5 Robustness of Balanced Realization
The balanced realization step converts the estimated Hankel-like matrix into estimates of A, C, and K through SVD-based factorization. Its robustness transfers Hankel estimation error to parameter estimation error, subject to a singular-value separation condition.
- Balanced realization: The balanced realization algorithm uses SVD to recover estimates of A, C, and K from the estimated Hankel-like matrix.The corresponding true and estimated realizations are compared after accounting for similarity transformation.
- Similarity transformation: The estimated matrices are evaluated against similar versions of the original system matrices because realization is identifiable only up to similarity transformation.The transformed matrices satisfy C̄ = CS, K̄ = S^-1K, and Ā = S^-1AS for an invertible S.
- Robustness guarantee: Theorem 4 establishes realization robustness when the true Hankel-like matrix has rank n and satisfies a robustness condition.Under these conditions, an orthonormal transformation relates the estimated realization to the true realization.
- Robustness limitation: SVD robustness can be restrictive when the smallest relevant singular value of G is small.The singular-value gap must separate signal singular vectors from those generated by estimation noise.
- Total bounds: All matrix estimation errors inherit the statistical rate of the Hankel-like matrix estimation error.The total bounds combine the regression guarantee with realization robustness, with errors depending linearly on ∥G − Ĝ∥2.
6 Discussion and Future Work
The discussion connects the paper’s SVD choice to broader stochastic subspace identification and identifies several extensions beyond the reported guarantees.
- Discussion: The paper’s SVD step applies decomposition directly to G, unlike other stochastic subspace methods that decompose W1GW2.The weighting matrices W1 and W2 may be full rank and data dependent.
- Discussion: Bounds on ∥G − Ĝ∥ and persistence of excitation are foundational for analyzing finite-sample properties of related algorithms.These results are presented as relevant beyond the specific algorithm studied.
- Future work: Finite-sample bounds could also be developed for the closed-loop matrix Ac = A − KC using estimated matrices or a direct estimate.The paper does not establish stability guarantees for either resulting closed-loop estimate.
- Future work: Future directions include analyzing non-steady-state Kalman filters and deriving lower bounds to assess the tightness of the upper bounds.The current analysis assumes the Kalman filter has reached steady state and considers only upper bounds.
A Proof of Theorem 3
The proof develops concentration tools for self-normalized martingales and matrix operations, then uses them to establish persistence of excitation for noise-related quantities.
- Martingale concentration: The proof invokes a self-normalized martingale bound for conditionally 1-sub-Gaussian scalar noise and predictable vector processes.The resulting statement holds uniformly over time with probability at least 1 − δ.
- Linear algebra tools: A block matrix norm lemma bounds the norm of a block product by the sum of block norms weighted by the corresponding vector-block norms.The proof follows from the triangle inequality, the matrix norm definition, and Cauchy–Schwarz.
- Persistence of excitation: Theorem 2’s proof establishes finite-sample persistence of excitation for past noises and outputs by controlling singular values and cross terms.The argument combines concentration events, union bounds, and thresholds N0 and N1 that grow through logarithmic terms.
- Persistence of excitation: Positive measurement-noise covariance ensures the relevant covariance matrix has strictly positive minimum singular value.Specifically, σE ≥ σmin(R), and Assumption 1 gives σmin(R) > 0.
Proof of Theorem 2
The proof of Theorem 2 establishes output persistence of excitation by combining noise excitation, small cross terms, and sufficiently large sample thresholds.
- Step 1: Noise PE: For N ≥ N0, the noise-persistence event holds with probability at least 1 − δN.This is the first event used in the output persistence-of-excitation argument.
- Step 2: Cross terms are small: The proof controls the cross terms between estimated past outputs and noises using sub-Gaussian concentration and upper bounds on auxiliary quantities.Combining the relevant events gives probability at least 1 − 2δ for the cross-term control.
- Step 3: Output PE: For sufficiently large N, the output Gram matrix satisfies a lower-bound condition derived from the noise singular-value bound and controlled cross terms.The proof introduces N1 and uses β ≥ σE/2 to establish the needed inequality.
C Proof of Theorem 1
Theorem 1’s proof bounds the main estimation terms by controlling output-noise interactions, cross terms, and Kalman truncation effects across high-probability events.
- Proof setup: The proof begins on the joint event where output and noise persistence properties hold, with probability at least 1 − δN − 2δ.This event supplies the basis for subsequent bounds on the estimation terms.
- Cross-term bound: Output-noise cross terms are bounded using matrix concentration and an upper bound on the normalized output Gram matrix.Conditioned on the joint persistence event, the cross-term controls hold with probability 1 − 2δ.
- Kalman truncation: The proof separately bounds the Kalman truncation term before combining all events with a union bound.The required threshold N2 is chosen so the truncation contribution is controlled with high probability.
- Final expression: The final expression is simplified using logarithmic inequalities involving κN, f, m, and p.This produces the stated form after the preceding probability bounds are combined.
D Proof of Theorem 4
The proof combines low-rank approximation, perturbation robustness, and matrix norm bounds to control the recovered system matrices. It then transfers these bounds to the estimated state matrix and Kalman gain using an orthogonal alignment.
- Low-rank approximation: The proof approximates the estimated matrix with a rank-n truncation and compares it with the rank-n population matrix.Optimality of the rank-n approximation bounds the truncation error through the estimated-to-population matrix difference.
- SVD robustness: SVD robustness provides an orthonormal transformation aligning the estimated and population factors.The Frobenius norm measures the resulting factor discrepancy, while rank considerations relate it to spectral-norm perturbations.
- Kalman gain: The same perturbation argument is applied to the factor associated with the Kalman gain.The proof explicitly states an analogous bound for K before combining the previous inequalities.
- State-matrix recovery: The recovered state matrix is formed as ˆA = ˆM† ˆN, while the aligned population counterpart is ¯A = ¯M† ¯N.Subsequent algebra transfers factor perturbation bounds to the state-matrix estimate.
- Final bound: Combining the preceding bounds yields the theorem's final estimation guarantee.The proof concludes by collecting the approximation, robustness, and factor-recovery inequalities.
E Bounds for system matrices
This section establishes how powers of the system matrix and related structured matrices behave under stability assumptions. Stable systems have uniformly bounded norms, whereas marginally stable systems incur at most polynomial growth in the horizon or truncation length.
- Powers of A: If ρ(A) < 1, the partial sum of powers S_t has uniformly bounded spectral norm: ∥S_t∥2 = O(1).The stable case follows by applying Gelfand's formula with a bound strictly below one.
- Powers of A: If ρ(A) = 1, then ∥S_t∥2 = O(t^κ), where κ is the largest Jordan block associated with a unit-circle eigenvalue.The polynomial exponent reflects the relevant Jordan-block size.
- System-matrix norms: For ρ(A) ≤ 1, the norms ∥O_k∥2, ∥T_k∥2, and ∥Γ_k∥2 grow at most polynomially in k; for asymptotically stable systems, they remain O(1).This corollary summarizes the stability-dependent behavior of the system matrices used later in the analysis.
- Singular values: The n-th singular values of O_p and G are increasing with p.These monotonicity lemmas support lower-bound arguments for the relevant observability and system matrices.