PaperlayerView exact revision on arXiv

Source-linked AI summary

Non-asymptotic Identification of LTI Systems from a Single Trajectory

Samet Oymak, Necmiye Ozay

arXiv:1806.05722v2cs.LGeess.SYmath.OCstat.ML

TL;DR

The paper asks how to identify an LTI system from only one input/output trajectory with finite data. It estimates Markov parameters, converts them into a balanced realization through Ho-Kalman, and derives high-probability data requirements for a desired accuracy.

  • Problem

    Finite-sample identification from input/output data has been less developed than asymptotic analysis, especially without state measurements or multiple independent trajectories.

  • Method

    The paper uses least squares to estimate Markov parameters from one trajectory, then applies a stability analysis of Ho-Kalman to obtain a balanced realization.

  • Results

    The analysis gives high-probability sample requirements for learning a balanced realization to a desired accuracy and for approximating the system’s Hankel operator.

  • Takeaways & Limitations

    Single-trajectory input/output data can be used to approximate the Hankel operator and recover a balanced realization without state measurements or multiple independent trajectories.

  • Takeaways & Limitations

    The analysis assumes stable systems with ρ(A) < 1 and includes sample-size logarithmic factors that may be spurious.

Abstract

from arXiv · show

We consider the problem of learning a realization for a linear time-invariant (LTI) dynamical system from input/output data. Given a single input/output trajectory, we provide finite time analysis for learning the system's Markov parameters, from which a balanced realization is obtained using the classical Ho-Kalman algorithm. By proving a stability result for the Ho-Kalman algorithm and combining it with the sample complexity results for Markov parameters, we show how much data is needed to learn a balanced realization of the system up to a desired accuracy with high probability.

1 Introduction

The paper addresses finite-sample identification of LTI systems from a single input/output trajectory, where prior guarantees were largely asymptotic or conservative. It estimates Markov parameters and uses Ho-Kalman to obtain an accurate balanced realization with high probability.

  • Finite-sample complexity for system identification has been rarely discussed, while earlier results are conservative.
  • The paper studies learning an LTI realization from a single input/output trajectory, a more challenging setting than multiple independent state trajectories.
  • Least-squares estimation learns the system’s Markov parameters, which are useful for system identification and control design.
  • The Ho-Kalman algorithm constructs a balanced realization from the singular value decomposition of the Markov-parameter Hankel matrix.
  • A stability result for Ho-Kalman combined with Markov-parameter sample complexity quantifies the data needed to achieve a desired realization accuracy with high probability.

2 Problem Setup

The problem is to estimate an LTI system’s Markov parameters from one dependent input/output trajectory using least squares. These estimates support prediction and state-space recovery up to similarity transformation, with error controlled by sample size and noise.

  • Problem Setup: The system is characterized by observable and controllable matrices A, B, C, and D and evolves as a linear state-space model.
  • Problem Setup: The first Markov parameter is D, followed by matrices {CA^iB}, and learning them provides finite-sample estimation guarantees.
  • Problem Setup: Learned Markov parameters can support future-output prediction and identify A, B, C, and D up to a similarity transformation.
  • Data and Estimation: The method uses finite, dependent data from a single trajectory rather than infinitely many independent input-output pairs.
  • Data and Estimation: Recursive output expansion treats process, measurement, and residual state effects as additive noise in a regression for the Markov-parameter matrix G.
  • Least-Squares Procedure: Least squares estimates G from label matrix Y and input matrix U, with error bounded as a function of sample size N and noise levels σw and σz.

3 Results on Learning Markov Parameters

The results provide finite-sample bounds for estimating Markov parameters from a single dependent trajectory, with stability controlling unknown-state effects. The main theorem operates in the challenging regime N ≳ Tp and separates contributions from measurement noise, process noise, and truncation error.

  • Error decomposition: The estimation error separately accounts for measurement noise σz, process noise σw∥F∥, and unknown-state effects σe.The unknown-state term includes a ∥CA^(T−1)∥ multiplier, so increasing T reduces that component while increasing the Markov-parameter matrix size.
  • Error decomposition: Ignoring logarithmic factors, the required sample size grows proportionally to Tp, matching the minimum observation period implied by mTp unknown parameters and m measurements per timestamp.The resulting Tp/N behavior is similar to independent linear regression, despite dependent covariates and noise.
  • Main theorem: Stable systems with ρ(A) < 1 admit high-probability Markov-parameter estimation from a single trajectory under finite sample sizes.Theorem 3.2 assumes N ≥ cTp log^2(2Tp)log^2(2Np) and observes the trajectory through time N + T − 1.
  • Main theorem: Theorem 3.2 works in the regime Tp ≲ N ≲ T(p + n + m), beyond the regime requiring N proportional to T(p + n + m).This reaches the regime where the input data matrix is tall while hidden state dimension may exceed input and sensor dimensions.
  • Limitations: The stated sample-size bounds may contain spurious logarithmic factors, and the dependence in equation (3.1) may be overestimated.The authors identify these as directions for improving Theorem 3.2.

4 Markov Parameters to Hankel Matrix: Low Order Approximation of Stable Systems

The section uses stability to approximate a stable system’s infinite impulse and Hankel behavior from finitely many estimated Markov parameters. The resulting bounds treat the system as having an effectively logarithmic order.

  • Stable-system approximation: Stability makes the unlearned impulse-response tail controllable, enabling finite-horizon estimates to approximate the system’s overall behavior.The tail terms can be upper bounded, allowing the finite impulse approximation horizon to increase toward infinity.
  • Stable-system approximation: Theorem 4.1 combines Markov-parameter estimation with a stability condition to bound the infinite impulse-response and Hankel operators.It assumes spectral radius ρ(A) < 1 and, for notational simplicity, no process noise.
  • Effective order: The effective system order is T ∼ O(−1/log(ρ(A))), because stability causes the Markov parameters to decay exponentially.Thus the relevant horizon depends logarithmically on spectral radius and target precision.
  • Approximation bounds: ∥G(∞) − ˆG(∞)∥ ≤ δ and ∥H(∞) − ˆH(∞)∥ ≤ O(−δ log(ρ(A))).These bounds quantify approximation of the infinite Markov and Hankel operators.
  • Sample complexity: The sample size is independent of state dimension n and grows linearly with p, requiring only logarithmically more than the O(p) minimum.The stated scaling is N ≈ −O(p) log(ρ(A)) for estimating the infinite Hankel matrix.

5 Non-Asymptotic System Identification via Ho-Kalman

The Ho-Kalman algorithm converts estimated Markov parameters into a balanced realization through Hankel-matrix factorization. Its perturbation analysis yields non-asymptotic identification guarantees, with robustness governed by the weakest system mode.

  • Algorithm and scope: Ho-Kalman generates A, B, C, and D from the Markov parameter matrix and applies to arbitrary, possibly unstable, systems.The section does not assume stability for the realization procedure.
  • Identification ambiguities: Similarity transformations produce equivalent state-space realizations, so identification of A, B, and C is considered up to trivial ambiguities.D is directly estimated as a submatrix of G.
  • System identification algorithm: The algorithm forms a Hankel matrix from ˆG, computes a rank-n approximation by SVD, and extracts observability and controllability factors.The factors are used to obtain ˆC and ˆB from their first block rows or columns.
  • System identification algorithm: When ˆG = G, Ho-Kalman returns the true balanced realization; with noisy parameters, the output degrades continuously with perturbation size.The method can use balanced Hankel dimensions mT1 ≈ pT2 for improved noise robustness.
  • Robustness: If σmin(L) is sufficiently large, singular-value thresholding can estimate the true system order n non-asymptotically from noisy Markov parameters.Corollary 5.4 bounds realization-factor errors, and together with Theorem 3.1 yields an end-to-end guarantee.
  • Robustness: The perturbation bounds are controlled by σmin(L), typically corresponding to the weakest system mode.For sufficiently large T2, σmin(L) ≈ σmin(H) because the discarded Hankel block is exponentially small.
  • Limitation: The robustness proof controls singular vectors in Frobenius norm rather than spectral norm, leaving sharper spectral-norm control as a future improvement.This is the stated limitation of the perturbation analysis.

6 Numerical Experiments

The experiments evaluate least-squares Markov-parameter estimation and Ho-Kalman realization recovery from single trajectories under varying horizons, sample sizes, and noise levels. Larger data and lower noise generally improve estimation, while shorter horizons can be advantageous in noisy or data-limited regimes.

  • Experimental setup: The experiments use MIMO systems with m = 2 sensors, n = 5 hidden states, and input dimension p = 3.The state matrix is diagonal with eigenvalues uniformly sampled from [0,0.9], ensuring stable systems.
  • Experimental setup: Each configuration generates a single rollout, estimates G by least squares, and applies Ho-Kalman for horizons T ∈ {6,12,18}.Curves average outcomes over 20 independent single-trajectory realizations.
  • Markov-parameter estimation: Estimation accuracy drastically improves with longer observation periods and more data, while errors decay gracefully as noise levels increase.For large T, unknown-initial-condition effects are fairly negligible, yielding near-zero error in the zero-noise regime.
  • Ho-Kalman realization: Relative system errors in Figure 2 are evaluated using the H∞ norm after Ho-Kalman recovery, with matrix-error control inherited from G − ˆG.The experiments also report similar behavior for Frobenius, H2, and related matrix-error metrics.
  • Ho-Kalman realization: In zero noise, T = 18 outperforms the other horizons; under noise, the horizons perform similarly, with T = 6 showing less sensitivity to increasing σw, σz.For very small N, T = 6 converges faster because it has fewer unknowns and requires minimal N on the order of Tp.

7 Conclusions

The paper concludes that finite-sample LTI identification is possible from inputs and outputs of a single trajectory without independent trajectories or non-overlapping data splits. Its analysis supports near-optimal Hankel-operator approximation and stability of balanced-realization recovery.

  • Conclusions: The analysis uses a single input/output trajectory without requiring multiple independent trajectories or splitting data into non-overlapping intervals.It also does not require state measurements.
  • Conclusions: The analysis shows that the system’s Hankel operator can be approximated using a near-optimal number of samples.The conclusions also establish stability properties for finding a balanced realization.
  • Conclusions: The method analyzes linear-system identification sample complexity directly from input/output data.The proof setup represents the observations through the data matrix U, Markov parameters G, and noise-related terms.
  • Proof strategy: The proof bounds estimation-error components separately using random-circulant, Gaussian-concentration, and martingale-based arguments.These components control terms involving U, W, Z, and E.

A.1 Proof of Theorem 3.2

The proof of Theorem 3.2 decomposes least-squares error into contributions from initial-state, process-noise, and measurement-noise terms. It controls these contributions using conditioning of the data matrix, Gaussian concentration, random-circulant results, and martingale bounds.

  • Sample-size condition: The proof assumes N is sufficiently large, with a principal sample-size condition of the form N ≥ cTpΘ.The logarithmic factor Θ depends on T, p, and N.
  • Measurement noise: The measurement-noise term U*Z is controlled through Gaussian concentration after establishing norm bounds for U.Corollary A.2 provides a high-probability bound when N ≥ cTpΘ.
  • Process and initial-state effects: Random-circulant matrix properties control conditioning of U and the interaction U*W with process noise.The proof uses these bounds together with independence of U and Z and a martingale argument for E.
  • Hankel approximation: For stable A, truncation and Hankel-tail terms are bounded geometrically, while finite Markov-parameter errors are transferred to the Hankel operator.The proof decomposes H(∞) into Hmain and Htail, with the estimated tail set to zero.

B Proof of the Ho-Kalman Stability

The Ho-Kalman stability proof relates perturbations in estimated Markov parameters to perturbations of Hankel factors and the recovered state-space matrices. Singular-value and subspace perturbation bounds yield closeness up to a unitary transformation under a suitable spectral-gap condition.

  • Setup: The proof assumes observability and controllability, ensuring the relevant Hankel factor L has rank n.It compares realizations generated from G and ˆG as a function of ∥G − ˆG∥.
  • Perturbation transfer: Hankel and factor perturbations are bounded by the Markov-parameter perturbation because Hankel rows and columns are submatrices of G.This gives bounds relating H − ˆH and L − ˆL to G − ˆG.
  • Unitary alignment: The SVD perturbation result provides a unitary matrix T aligning the left and right singular-vector subspaces of L and ˆL.This simultaneous alignment is used to compare balanced observability and controllability factors.
  • Singular-subspace stability: If σmin(L) ≥ 2∥L − ˆL∥, singular-value perturbation preserves rank-related conditioning and bounds σmin(ˆL) below by σmin(L)/2.The same condition also controls the norm of ˆL.
  • State-space recovery: The recovered B and C factors inherit the perturbation bound, while the A-matrix comparison is decomposed into factor, pseudoinverse, and H+ perturbations.The proof uses equations (B.1) and (B.2), triangle inequalities, and pseudoinverse bounds.
  • State-space recovery: The resulting realization is close up to the unitary transformation T when the Hankel perturbation is sufficiently small relative to σmin(L).In particular, ∥H − ˆH∥ ≤ σmin(L)/4 implies the conditions required by Theorem 5.3.
  • Supporting concentration tools: Random-circulant restricted-isometry results support the least-squares analysis by controlling conditioning of U and the interaction U*W.The paper notes that some logarithmic factors may be redundant because only one submatrix is needed.

C.1 Conditioning of the Data Matrix

The analysis conditions the input-related data matrices by embedding them into circulant matrices and applying a probabilistic matrix bound. This yields high-probability control of both U and the cross-term U*W.

  • Conditioning U: Lemma C.2 requires N ≥ cTp log^2(2Tp) log^2(2N̄p) for a high-probability conditioning bound on U.The input data matrix U is represented as a submatrix of a larger circulant matrix.
  • Conditioning U: The input data matrix U is embedded in the rightmost Tp columns of a circulant matrix using regularly selected rows.This embedding permits application of the circulant-matrix theorem to U.
  • Conditioning M: Lemma C.3 applies the same construction to M, with q = p+n and N0 = cTq log^2(2Tq) log^2(2N̄q).The matrices U and W occupy complementary column blocks of M, making U*W an off-diagonal submatrix of M*M.
  • Conditioning M: The cross-term satisfies ∥U*W∥ ≤ σwσu max{√(N0N), N0} under the stated high-probability event.The bound follows by controlling the corresponding circulant matrix and then restricting to its off-diagonal submatrix.

D Bounding the Error due to the Unknown State

This section bounds the estimation error caused by the unknown-state term in a finite impulse-response approximation. The main difficulty is dependence between the unknown-state errors and the truncated input vectors.

  • Error source: The finite impulse-response approximation introduces e_t = CA^(T−1)x_(t−T+1), and the analysis seeks to bound ∥U*E∥.Here E collects unknown-state errors while U collects truncated input vectors.
  • Dependence: The products forming U*E are dependent because each e_t contains an earlier input component also present in the input sequence.The theorem is designed to handle this dependence rather than treating the observations as independent.
  • Probabilistic bound: Theorem D.1 bounds the resulting error with probability at least 1 − T(exp(−100Tp) + 2exp(−100m)) under N ≥ T.The bound depends on the system factor γ and the stability term 1−ρ(A)^T.
  • Decomposition: The proof decomposes U*E into T smaller products by grouping indices into sequences separated by T time steps.Each sequence has length between floor(N/T) and floor(N/T)+1.

D.1 Upper Bounding the Components of the Unknown State Decomposition

The analysis controls each decomposed unknown-state product using time-separated sequences, independence from filtrations, martingale concentration, and covering arguments. It then combines these bounds into a spectral-norm estimate.

  • Independence structure: Time-separated subsequences make each error term measurable before the corresponding input vector, while that input vector remains independent of the preceding filtration.This supports treating the relevant products with martingale concentration.
  • Final bound: Corollary D.3 gives a high-probability bound for ∥U*E∥ when N ≥ T, scaling with max{N, mT/(1−ρ(A)^T)} max{p,m/T} γ.The result holds with probability at least 1−exp(−100Tp)−2exp(−100m).
  • Concentration tools: The analysis uses a martingale concentration lemma whose products behave like inner products between deterministic coefficients and independent subgaussian variables.The general bound scales with min{m,n}.
  • Concentration tools: The proof applies a 1/4-covering argument over unit vectors to convert scalar inner-product bounds into a spectral-norm bound.The covering sets have logarithmic sizes bounded by 3Tp and 3min{m,n}.
  • Gaussian concentration: The unknown-state matrices are analyzed through Gaussian quadratic forms, with Hanson–Wright concentration applied after bounding their Frobenius and spectral norms.The bounds exploit covariance domination by Γ∞ and decay governed by ρ(A).

E Proof of Theorem C.1

The proof of Theorem C.1 adapts a Gaussian matrix concentration result to fixed submatrices. It handles separate regimes according to whether the isometry constant is at most one.

  • Concentration theorem: The proof uses a variation of Krahmer et al.’s theorem for Gaussian vectors and matrix families measured in Frobenius and spectral norm.The fixed-submatrix setting reduces the relevant matrix family relative to the broader theorem.
  • Submatrix reduction: The argument analyzes a fixed m × s submatrix among all s-column submatrices restricted to fixed m rows.This structure allows the prior theorem’s estimates to serve as upper bounds.
  • Regime analysis: The proof splits into cases δ ≤ 1 and δ > 1, choosing constants large enough to compensate for the concentration estimates.The sample threshold is m0 = c0s log^2(2s) log^2(2d).
  • Probability guarantee: The resulting success probability is exp(−log^2(2d) log^2(2s)) under the selected parameter conditions.The conclusion follows after satisfying the required inequalities in both cases.
Loading 1806.05722v2…