PaperlayerView exact revision on arXiv

Source-linked AI summary

Near optimal finite time identification of arbitrary linear dynamical systems

Tuhin Sarkar, Alexander Rakhlin

arXiv:1812.01251v7eess.SY

TL;DR

The paper addresses finite-time estimation of general LTI dynamics from a single observed trajectory, where sharp guarantees are difficult across stable, marginally stable, and explosive regimes. It analyzes OLS using sample covariance and self-normalized martingale tools, obtaining near-optimal bounds across arbitrary eigenvalue distributions while identifying inconsistency under certain conditions.

  • Problem

    Sharp non-asymptotic error guarantees for OLS identification were limited when LTI eigenvalues span stable, marginally stable, and explosive regimes.

  • Method

    The paper jointly analyzes the sample covariance and a self-normalized martingale difference term for OLS estimation from one trajectory.

  • Results

    OLS admits nearly optimal finite-time rates for regular systems with arbitrary eigenvalue distributions, while the analysis provides regime-specific bounds and matching lower bounds in the explosive case.

  • Takeaways & Limitations

    Identification error behaves similarly across stable, marginally stable, and explosive components up to constants depending on A, despite differing covariate distributions.

  • Takeaways & Limitations

    OLS can be statistically inconsistent when A is not regular, and near-unit eigenvalue lower bounds are not tight in one stated regime.

Abstract

from arXiv · show

We derive finite time error bounds for estimating general linear time-invariant (LTI) systems from a single observed trajectory using the method of least squares. We provide the first analysis of the general case when eigenvalues of the LTI system are arbitrarily distributed in three regimes: stable, marginally stable, and explosive. Our analysis yields sharp upper bounds for each of these cases separately. We observe that although the underlying process behaves quite differently in each of these three regimes, the systematic analysis of a self--normalized martingale difference term helps bound identification error up to logarithmic factors of the lower bound. On the other hand, we demonstrate that the least squares solution may be statistically inconsistent under certain conditions even when the signal-to-noise ratio is high.

1 Introduction

The paper studies finite-time identification of unknown linear dynamical systems from observed trajectories using OLS, addressing sharp non-asymptotic error bounds across system regimes. Existing approaches face limitations near or beyond the stability boundary, while explosive systems create dependence patterns that undermine standard blocking techniques.

  • Problem: Finite-time system identification estimates unknown dynamical-system parameters from a finite output time series and matters across several applied fields.The paper focuses on learning A in Xt+1 = AXt + ηt+1 from observations of Xt.
  • Motivation: Sharp non-asymptotic identification-error characterizations for linear systems were relatively unknown despite their broad use.Linear systems appear in control, time-series analysis, econometrics, and approximations of nonlinear systems.
  • Existing limitations: Mixing-time bounds deteriorate as ρ(A) approaches 1 and cannot extend to systems with ρ(A) ≥1.Small-ball methods provide sharper bounds near the unit circle but are discussed only for a restricted spectral regime.
  • Explosive regime: For explosive systems, exponential scaling makes later states depend strongly on earlier noise, so standard approximately independent covariate blocks fail.This dependence complicates concentration and identification-error analysis.

2 Contributions

The paper develops a unified OLS analysis for arbitrary eigenvalue distributions, covering stable, marginally stable, and explosive components. Its central tools yield near-optimal regime-specific rates and expose conditions under which OLS becomes inconsistent.

  • Contributions: The analysis provides nearly optimal finite-time OLS identification rates without restricting the spectral radius of A.The result covers every regime of ρ(A).
  • Contributions: A coupled analysis of sample covariance and a self-normalized martingale difference term handles covariates that may grow exponentially over time.The approach avoids the overhead of choosing a block size.
  • Regime-specific results: For ρ(A) ≤1, the paper recovers previously derived optimal finite-time error rates.For fully explosive systems, anti-concentration and subgaussian inequalities sharpen prior bounds, and a matching lower bound establishes tightness.
  • General case: The paper analyzes arbitrary mixtures of stable, marginally stable, and explosive eigenvalues by tracking noise-covariate cross terms across components.It also shows that OLS can be statistically inconsistent without certain regularity conditions, even when signal-to-noise ratio is high.

3 Notation and Definitions

This section defines the LTI model, spectral classes, matrix notation, assumptions, and self-normalized-martingale framework used to analyze OLS identification. It distinguishes stable and explosive systems through eigenvalue magnitudes and introduces quantities needed for regime-dependent bounds.

  • Spectral classes: A stable LTI system has ρmax(A) < 1, whereas an explosive LTI system has ρmin(A) > 1.The eigenvalue magnitudes are ordered from ρmax(A) to ρmin(A).
  • Assumptions: The framework assumes X0 = 0 or a bounded initial vector, isotropic subgaussian noise, independent noise coordinates, and bounded noise-coordinate densities.The analysis restricts attention to regular systems, where eigenvalues outside the unit circle have geometric multiplicity one.
  • OLS notation: The OLS analysis uses data and noise matrices, the pseudoinverse-based estimator, and bounds on (X′X)+X′.These objects organize the estimation error through the observed trajectory's sample covariance.
  • Probability tools: The filtration Ft records the noise and covariate history, supporting a self-normalized martingale result for the identification analysis.The paper also defines A-dependent quantities, including ψ(A), for explosive-system error bounds.

4 Main Results

The paper develops finite-time OLS guarantees across stable, marginally stable, explosive, and mixed-eigenvalue LTI systems. It combines covariance invertibility analysis with self-normalized martingale bounds, while identifying regularity and conditioning as key boundaries for consistency.

  • Separate regimes: Theorem 1 provides non-asymptotic least-squares bounds separately for stable, marginally stable, and explosive regimes.The analysis treats the three regimes individually before addressing arbitrary eigenvalue distributions.
  • Proof strategy: The analysis bounds identification error by combining sample-covariance invertibility with a self-normalized martingale term.The proof strategy first characterizes the covariance matrix and then controls the noise-covariate term.
  • Separate regimes: For ρ(A) ≤1, the paper recovers optimal finite-time identification rates, while explosive systems require anti-concentration arguments rather than small-ball methods.The explosive analysis addresses covariates that grow exponentially in time.
  • Separate regimes: Explosive-system error depends on δ as 1/δ, unlike the log 1/δ dependence for stable and marginally stable systems.The paper argues this confidence dependence is unavoidable and sharpens earlier bounds in one parameter range.
  • General eigenvalue distributions: For mixed eigenvalue distributions, similarity-transform interactions require separate analysis, and the resulting error bounds are limited by the slowest component.The general-case theorem applies to regular matrices and retains nearly regime-specific behavior up to polynomial factors.

5 Inconsistency of OLS

The paper shows that OLS can be inconsistent for irregular explosive systems, even with high signal-to-noise ratio, because the sample covariance becomes singular or severely ill-conditioned.

  • The paper frames irregular matrices as systems that cannot be learned despite a high signal-to-noise ratio.This establishes irregularity as the relevant limitation in the presented setting.
  • OLS is inconsistent for the irregular matrix A_o despite Γ_T(A_o)=(1.1)^T I indicating a high signal-to-noise ratio.The estimate has a non-trivial bimodal distribution rather than converging to zero.
  • For the irregular example, the sample covariance matrix is singular, decoupling OLS consistency from the controllability Gramian.The paper states that this relation is tenuous for unstable systems.
  • The analysis uses a one-dimensional explosive process with a=1.1 and independent standard Gaussian noise to characterize the problematic covariance behavior.The stated regime includes the condition T^2 ≤ a^T.
  • OLS inconsistency occurs when the sample covariance condition number grows exponentially with T, as in the A_o example.Ill-conditioning magnifies noise-covariate cross terms, preventing identification error from decaying over time.

6 Discussion

The discussion concludes that regularity enables sharp finite-time OLS guarantees across stable, marginally stable, explosive, and mixed-eigenvalue systems, while irregularity can cause inconsistency.

  • For regular A, OLS has sharp finite-time rates across stable, marginally stable, and explosive regimes, with arbitrary eigenvalue distributions.The paper identifies these regimes as S0, S1, and S2.
  • A self-normalized martingale analysis supports error bounds despite substantial differences in covariate behavior across regimes.
  • The paper provides a tighter lower bound for explosive systems A∈S2, stated to hold with probability at least δ.
  • For a fixed error threshold ϵ, the required time scales at least as log(1/δ) across every regime, and the bound is described as tight.
  • The techniques extend in scope to settings with control inputs or heavy-tailed noise, according to the discussion.

7 Appendix

The appendix develops matrix and probabilistic tools for analyzing Jordan structures, sample covariance growth, singular values, and concentration bounds used in the finite-time identification results.

  • Jordan-block analysis: Jordan decomposition reduces the matrix analysis to blocks J_k(λ), whose nilpotent structure determines powers and inverse powers.A Jordan block is represented as λI+N with N^k=0.
  • Marginal stability: For eigenvalues within C/T of the unit circle, the appendix derives polynomial-in-T growth bounds for entries and singular values of relevant matrix products.
  • Jordan-block analysis: Unitary transformations remove eigenvalue phases without changing singular values, allowing analysis to focus on positive real eigenvalues.
  • Matrix bounds: The determinant and singular-value arguments yield bounds whose constants depend on Jordan-block size and dimension rather than on T.
  • Matrix bounds: The appendix notes that α(d) may be exponentially small in dimension, although α(A)=1 for examples such as orthogonal or diagonal matrices.

8 Probabilistic Inequailities

This section assembles concentration tools for subGaussian noise, dependent quadratic forms, self-normalized martingales, and anti-concentration events needed for system-identification bounds.

  • Concentration inequalities: Hanson–Wright inequalities provide concentration for quadratic forms of independent subGaussian coordinates.
  • Self-normalized martingales: The section applies self-normalized martingale tools to sums of state variables multiplied by projected noise.
  • Self-normalized martingales: The martingale setup assumes adapted processes, conditionally subGaussian noise, and a positive definite regularization matrix.
  • Concentration inequalities: Linear transformations with full row rank preserve a non-trivial subGaussian structure, enabling dependent Hanson–Wright bounds.
  • Applications: The resulting propositions provide high-probability bounds for subGaussian matrix and process terms under independent-noise assumptions.
  • Anti-concentration: Anti-concentration bounds control small-ball probabilities when the state density has bounded essential supremum.

9 Lower Bound for YT when A ∈S0 ∪S1

This section develops lower-bound analysis for Y_T in the stable and marginally stable regimes under independent subGaussian noise and full-row-rank noise loading. The argument controls high-probability events and relates the bounds to the growth of tr(Γ_T − I).

  • The analysis assumes η_t=L\barη_t with independent noise components and full-row-rank L, with σ_min(LL′)=R^2>0.
  • The goal is to control the relevant quantity associated with Y_T through high-probability bounds.
  • The main probability calculation establishes P(E_1(δ) ∩ E_2(δ)) ≥ 1−2δ.
  • Eq. (52) is satisfied whenever tr(Γ_T − I) grows at most polynomially in T, including cases with ρ(A) ≤ 1+c.

10 Sharpened bounds when 1 −c

This section sharpens the upper bound for Y_T in the near-unit-root regime by enforcing the relevant condition across all t ≥ T. The refinement yields linear growth in T under a logarithmic correction term.

  • The bound for Y_T is sharpened by requiring the controlling inequality to hold for every t ≥ T.
  • The sufficient condition is obtained by comparing the left-hand side at t=T/2 with the right-hand side at t=T.
  • The refinement produces a recursion whose coefficients form a non-increasing sequence β_k.
  • When T ≥ 64e c(A,δ), subsequent coefficients satisfy β_k < 1/2.
  • The resulting bound grows linearly with T, as stated in Proposition 7.5.

11 Invertibility of YT in explosive systems

This section analyzes invertibility-related quantities in explosive systems using scaled state decompositions and concentration inequalities. The proof combines independence-based Hanson–Wright bounds with Markov-type controls.

  • The construction exploits the statistical independence of z(t) and z(T)−z(t).
  • The analysis decomposes cross terms into products of independent components so that Hanson–Wright bounds can be applied.
  • Markov’s inequality supplies a high-probability bound for the trace-controlled matrix quantity.
  • The state decomposition uses the scaled quantity ẑ(T,t)=A^−T−1z(T,t).
  • Intersecting the relevant events yields a bound holding with probability at least 1−4δ.

12 Regularity and Invertibility

This section connects invertibility of Y_T in explosive systems to regularity of A. It establishes high-probability rank and invertibility results for regular matrices while identifying nonregularity as a source of inconsistency.

  • Unless a matrix is regular, parameter estimation may be asymptotically inconsistent.
  • The analysis assumes isotropic independent subGaussian noise and full-row-rank L, with σ_min(LL′)=R^2>0.
  • Invertibility of F_T is ensured by assuming A is regular, meaning unstable eigenvalues have geometric multiplicity one.
  • For regular A, F_T has rank d with probability at least 1−2δ.
  • The proof represents F_T as S_T S′ and uses anti-concentration-related lower bounds involving φ_min(A).

13 Composite Result

The analysis transforms arbitrary linear systems into explosive, marginally stable, and stable components, then controls their composite invertibility and identification error with high probability. The resulting bounds accommodate exponentially growing covariates, general noise extensions, and optional control inputs, while retaining dependence on unknown conditioning factors.

  • System decomposition: Any system matrix is partitioned into explosive, marginally stable, and stable components through a Jordan-form transformation used for analysis.The transformation is analytical because the associated matrix is unknown.
  • Composite invertibility: Composite invertibility is established by combining high-probability invertibility of stable and marginally stable blocks with Schur-complement arguments.The proof separately controls block positivity, cross terms, and the resulting full matrix.
  • Cross-term control: The cross-term analysis uses normalized gramians and carefully selected block lengths to control interactions between explosive and marginally stable components.The normalized gramian has spectral radius at most polynomial in T^β0(δ), with β0(δ) approximately logarithmic in T.
  • Finite-time bounds: The resulting upper bounds hold with high probability once the required time conditions are met, including stable–explosive and marginally stable–explosive regimes.The relevant time sets are eventually satisfied and are polylogarithmic in δ because the explosive decay term is exponentially small.
  • Original-coordinate error: Translating transformed-system error back to the original coordinates introduces unknown factors involving σmin(˜P) and σmin(˜P−1), although these depend on d rather than T.This is the main conditioning-related scope boundary in the stated original-error bound.
  • Extensions: The framework extends to controlled systems and bounded sub-Weibull noise, with the latter incurring only an extra logarithmic factor.Independent Gaussian control inputs are used in the control-input extension, while truncation converts the heavy-tailed noise to a bounded subGaussian process.
Loading 1812.01251v7…