Source-linked AI summary
Finite Time Identification in Unstable Linear Systems
Mohamad Kazem Shirani Faradonbeh, Ambuj Tewari, George Michailidis
TL;DR
Finite-time identification of unstable linear systems lacks the classical guarantees available for stable systems, despite applications in control, econometrics, and finance. The paper derives least-squares bounds under heavy-tailed noise across stable, explosive, and general regimes, showing near-standard accuracy and failure-probability scaling except for a measure-zero pathological case. The results leave unit-root and other null-measure cases for future work.
Problem
Finite-time identification of unstable linear systems is insufficiently developed, while classical least-squares approaches do not apply and such systems arise in control, econometrics, and finance.
Method
The paper derives least-squares identification bounds for stable, explosive, and general transition matrices under a broad sub-Weibull noise framework, using concentration tools for random matrices and martingale differences.
Results
Apart from a measure-zero pathological case, high-probability identification requires sample length scaling quadratically with inverse error and logarithmically with inverse failure probability.
Takeaways & Limitations
The bounds relate identification time to accuracy, failure probability, system dimension, transition-matrix characteristics, and noise characteristics for general linear dynamical systems.
Takeaways & Limitations
Unit-root transition matrices and other practically interesting null-measure cases remain topics for future investigation.
Abstract
from arXiv · showhide
Identification of the parameters of stable linear dynamical systems is a well-studied problem in the literature, both in the low and high-dimensional settings. However, there are hardly any results for the unstable case, especially regarding finite time bounds. For this setting, classical results on least-squares estimation of the dynamics parameters are not applicable and therefore new concepts and technical approaches need to be developed to address the issue. Unstable linear systems arise in key real applications in control theory, econometrics, and finance. This study establishes finite time bounds for the identification error of the least-squares estimates for a fairly large class of heavy-tailed noise distributions, and transition matrices of such systems. The results relate the time length (samples) required for estimation to a function of the problem dimension and key characteristics of the true underlying transition matrix and the noise distribution. To establish them, appropriate concentration inequalities for random matrices and for sequences of martingale differences are leveraged.
1 Introduction
The paper addresses the underdeveloped problem of finite-time identification for unstable linear systems, whose states can grow exponentially and invalidate classical least-squares approaches. It develops bounds covering heavy-tailed disturbances and relates required samples to dimension and system characteristics.
- Unstable-system identification remains inadequately studied despite applications in adaptive control, econometrics, and finance.
- The paper establishes finite-time ℓ2 identification bounds for least-squares estimates of transition matrices under general heavy-tailed noise.
- When transition matrices have eigenvalues both inside and outside the unit circle, the state Gram matrix has linearly growing smallest eigenvalue but exponentially growing largest eigenvalue.
- Accurate identification is necessary for stabilizing unknown systems and designing control policies within a short time period.
- Finite-time guarantees are needed because asymptotic results do not specify the sample size required for precise inference about unstable dynamics.
2 Problem Formulation and Preliminaries
The paper formulates least-squares identification for a possibly unstable VAR system and develops assumptions covering feedback control, heavy-tailed noise, reachability, and finite observations. Its formulation includes a high-probability accuracy guarantee for the estimated transition matrix, while highlighting sensitivity in stabilization applications.
- The system evolves as a VAR model with unknown transition matrix A0, arbitrary deterministic or stochastic initial state, and noise that need not be restricted to stable dynamics.
- Linear feedback produces the closed-loop matrix A0 = Ax + AuL, whose accurate estimation is needed to design stabilizing policies.
- A 3% relative error in one system entry can totally destabilize the closed-loop system in the illustrated stabilization example.
- The noise framework allows sub-Weibull coordinates, including heavy-tailed cases with α < 1 that need not have a moment-generating function.
- Reachability links non-degenerate state randomness to accurate estimation and holds for every A0 when the noise covariance C is positive definite.
3 Main results
The paper develops finite-time least-squares identification guarantees across stable, explosive, and general linear systems under heavy-tailed noise. Sample requirements depend on accuracy, failure probability, dimension, transition-matrix structure, and noise characteristics, with separate behavior in stable and explosive regimes.
- Main results: The results characterize the samples required for high-probability accuracy of the least-squares estimate across stable, explosive, and mixed regimes.The general result excludes regularity failures and eigenvalues on the unit circle.
- Stable systems: Under sub-Weibull noise, the stable-case bounds extend beyond the customary sub-Gaussian setting.The stable analysis uses an empirical covariance matrix with approximately deterministic asymptotic behavior.
- Explosive systems: In explosive systems, the empirical covariance grows exponentially and is approximated after normalization by a random matrix, requiring quantities φ(A0) and ψ(A0, δ) to control its eigenvalues.Regularity is equivalent to φ(A0)>0, while reachability implies positivity of ψ(A0, δ).
- Explosive systems: Explosive-system identification achieves exponentially decaying accuracy and failure probability, with failure probability having the common exponential order under linear ψ(A0, δ) scaling.The explosive bounds require regularity and reachability.
- Explosive systems: The explosive sample requirements n1 and n2 scale logarithmically with the system dimension p, with universal constants available under spectral separation conditions.The constants depend on the relevant spectral margins and, through the assumptions, on noise parameters.
- General systems: The framework does not cover transition matrices with unit eigenvalues, although such matrices occur in resonating mechanical, macroeconomic, and financial applications.Unit-root identification is identified as a direction for future work.
4 Concluding Remarks
The paper establishes finite-time bounds for least-squares identification in general linear dynamical systems, including systems whose transition matrix is not stable. Its conclusions identify scope for extensions while marking high-dimensional, structured, and measure-zero cases as future work.
- The paper studies finite-time bounds for least-squares estimates when the transition matrix need not be stable.
- The results relate identification time, accuracy, failure probability, transition and noise matrices, and system dimension.
- The analysis excludes a pathological case of zero Lebesgue measure while establishing high-probability identification results.
- The finite-time results may help develop analogous results for temporally dependent models such as nonlinear systems.
- High-dimensional sparse, low-rank, and other structured settings, along with practically relevant null-measure cases, remain future research directions.
A.1 Proof of Lemma 1
The proof of Lemma 1 combines propositions controlling stable-system quantities on a high-probability event to obtain the desired finite-time bound. Its argument uses Lyapunov-equation structure and probability bounds for the constituent terms.
- The proof defines an event through Proposition 3 and works on that event to combine several intermediate bounds.
- For stable A0, Proposition 4 supplies bounds for the state-related quantity over times t = 1, 2, · · · , n.
- Proposition 6 provides a bound for a noise-state cross term involving A0x(i)w(i + 1)′ and its transpose.
- The proof uses the Lyapunov equation and its solution to control the stable-system covariance contribution.
- Combining the bounds yields the desired result with probability at least 1−δ.
A.2 Proof of Corollary 1
The proof of Corollary 1 controls the random matrix term through propositions and combines the resulting bounds under reachability to establish the stated stable-system result.
- The proof combines assumptions and intermediate inequalities to establish a bound on the event W.
- Reachability ensures that the controllability Gramian K(C) has a strictly positive minimum eigenvalue.
- The matrix transformation Φ is used to express the spectral norm of H through the largest eigenvalue of the symmetric matrix Φ(H).
- Applying the matrix concentration proposition to Φ(Xt) controls the relevant random cross term.
- The resulting probability bound is at least 1−δ after incorporating the auxiliary bound on Un.
A.3 Proof of Lemma 2
The proof of Lemma 2 analyzes an explosive transition matrix through its Jordan decomposition and separates upper- and lower-eigenvalue controls. It combines high-probability events to obtain the desired result.
- The proof assumes an explosive A0 and uses its Jordan decomposition to define the relevant event.
- An auxiliary event V is shown to have probability at least 1−δ.
- The proof defines a transformed process z with z(0)=x(0) and analyzes its quadratic state terms over time.
- The upper-eigenvalue analysis yields a bound involving ξ(A0)(−log δ)2/α.
- The smallest-eigenvalue argument uses conditions indexed by N2(ϵ,δ) and obtains a probability of at least 1−4δ.
- Combining the intermediate inequalities on W ∩ V produces the desired result with probability at least 1−2δ.
A.4 Proof of Corollary 2
The proof combines intermediate implications on a high-probability event and concludes that the target bound is at most ϵ with probability at least 1−2δ.
- (A.22) and (A.23) are obtained from condition (5), then used on the event W ∩ V.
- Propositions 1 and 2 provide regularity-related ingredients used with Propositions 3 and 7 on W ∩ V.
- Substituting (A.24) and (A.26) into (A.25), and using (2), yields the final inequality.
- The resulting quantity is at most ϵ with probability at least 1−2δ on W ∩ V.
A.5 Proof of Theorem 1
The proof decomposes the system into two block components, establishes reachability and high-probability events, and uses regularity of the stable matrix to derive the theorem’s bound.
- System decomposition: The original system is split into two parts with transition matrices A1 and A2, while block diagonality separates their processes.
- System decomposition: Both separated processes inherit reachability, formalized by Proposition 12 for the pairs [A1, C11] and [A2, C22].
- Parameter conditions: The proof introduces parameters involving the Jordan decomposition A2 = P −1Λ2P and imposes conditions (A.27)–(A.35).
- High-probability event: Lemma 1 and Lemma 2 imply P(E) > 1−5δ, after which the proof proceeds on event E.
- Conclusion: The proof concludes from inequalities (A.38)–(A.42) on E with probability at least 1−δ.
- Regularity: Regularity is characterized through polynomial nonvanishing on Jordan blocks, with repeated eigenvalues producing the contradiction used for the nonregular case.
B.2 Proof of Proposition 2
The proof develops density and matrix-concentration arguments for the system’s random components, including a measure-zero result for irregular matrices and bounds on matrix powers.
- Noise and density arguments: The argument uses martingale-difference structure, invertibility of P, and nondegeneracy of transformed noise coordinates.
- Noise and density arguments: Bounded noise densities are propagated through linear combinations and sums, yielding bounded densities for v′z(∞) and related coordinates.
- Irregular matrices: Irregular matrices are shown to occupy a lower-dimensional set, hence a set of zero Lebesgue measure in R^p×p.
- Irregular matrices: For fixed Y, at most p−1 values of λ satisfy the relevant dependence condition, using a determinant polynomial of degree p−1.
- Jordan structure: Jordan decomposition determines the growth behavior of powers of the transition matrix through the norms of its Jordan blocks.
- Concentration bounds: The proof invokes Matrix Bernstein and Matrix Azuma inequalities to control independent symmetric matrices and symmetric martingale differences.
B.10 Proof of Proposition 9
The proof establishes lower bounds for transformed random-state coordinates and verifies reachability of the decomposed subsystems using positive-definiteness and the Cayley–Hamilton theorem.
- Probability bounds: On the relevant event, the proof derives intermediate bounds with probability at least 1−δ.
- Lower-bound argument: When φ(A0) > 0, a row of the transformed matrix has exactly one nonzero entry, whose magnitude is bounded below using φ(A0).
- Lower-bound argument: All coordinates of Pz(∞) are at least ψ(A0, δ) in magnitude with probability at least 1−δ.
- Lower-bound argument: Combining the matrix-row and coordinate bounds gives a nonzero-coordinate lower bound for the transformed vector.
- Reachability: Reachability of [A1, C11] follows by restricting a vector to the first subsystem and applying the Cayley–Hamilton theorem.
B.16 Proof of Proposition 15
The proof constructs a filtration-based martingale argument, uses positive semidefiniteness and referenced propositions to derive intermediate inequalities, and concludes with a high-probability bound. The resulting estimate includes a term involving ρ^4νn+1(δ), n, μ(A2), and |λmin(A2)|.
- Proof setup: The proof defines sigma-fields Ft = σ(w(1), · · · , w(t)) and uses martingale difference sequences with respect to this filtration.The argument introduces both symmetric-matrix and general martingale difference sequences relative to {Ft}n.
- Matrix inequalities: Several matrices are established as positive semidefinite using Propositions 4 and 18 before applying subsequent inequalities.The proof invokes Proposition 18 together with (A.34), and notes that the last inequality follows from the definition of Σn.
- Intermediate bounds: The proof applies Proposition 7 to bound |||Hn|||2 using equation (2) and preceding results.The argument separately notes measurability of Σn and x(2)(m) with respect to Fm before establishing the bound.
- Final estimate: ≤ρ4νn+1 (δ) nµ(A2)−1/2 |λmin (A2)|−2n/3 .This displayed bound is the stated quantitative estimate in the supplied proof passage.
- Conclusion: The concluding implication holds with probability at least 1 −δ and, together with (B.12), yields (A.41).The proof then closes with Q.E.D.