PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Linear Dynamical Systems with Semi-Parametric Least Squares

Max Simchowitz, Ross Boczar, Benjamin Recht

arXiv:1902.00768v1cs.LGmath.OCmath.STstat.MLstat.TH

TL;DR

Long-term correlations can inflate estimator variance, and it remains unclear whether strict stability is necessary for learning partially observed LTI systems. The paper analyzes prefiltered least squares and proves an oracle inequality; it reports rates without worst-case dependence on correlation-decay rates and consistency for marginally stable systems.

  • Problem

    Long-term correlations increase estimator variance, while the necessity of strict stability for partially observed LTI learning and the role of correlation-decay rates remain unresolved.

    Source: §1 · p. 1

  • Method

    PF-LS learns a linear prefilter from past-output features, subtracts its prediction from outputs, then regresses the filtered outputs on inputs.

    Source: §3 · p. 8

  • Results

    PF-LS provably mitigates variance from long-term dependencies and attains rates without worst-case dependence on their decay rate for partially observed linear systems.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The guarantees include consistency for marginally stable systems and cover both stochastic and worst-case noise.

    Source: §1 · p. 2

    Identifiability of the realization via Corollary 2.2 requires minimality; when it fails, the paper describes estimating an equivalent reduced system.

    Source: §2 · p. 6

Abstract

from arXiv · show

We analyze a simple prefiltered variation of the least squares estimator for the problem of estimation with biased, semi-parametric noise, an error model studied more broadly in causal statistics and active learning. We prove an oracle inequality which demonstrates that this procedure provably mitigates the variance introduced by long-term dependencies. We then demonstrate that prefiltered least squares yields, to our knowledge, the first algorithm that provably estimates the parameters of partially-observed linear systems that attains rates which do not not incur a worst-case dependence on the rate at which these dependencies decay. The algorithm is provably consistent even for systems which satisfy the weaker marginal stability condition obeyed by many classical models based on Newtonian mechanics. In this context, our semi-parametric framework yields guarantees for both stochastic and worst-case noise.

1 Introduction

The section frames long-term correlations as a source of inflated estimator variance and asks whether partially observed LTI systems can be learned without strict stability. It introduces prefiltered least squares (PF-LS) and an oracle inequality as its response.

1 Introduction

  • Long-term correlations can obscure design-variable effects and increase estimator variance, while the necessity of strict stability for partially observed LTI learning remains unknown.The appropriate role of correlation-decay rates in learning difficulty is also unresolved, even for strictly stable systems.Source: §1 · p. 1
  • PF-LS provably mitigates variance from long-term dependencies and achieves rates without worst-case dependence on their decay rate, including consistency for marginally stable systems.The framework provides guarantees for both stochastic and worst-case noise.Source: §1 · p. 2

1.1 Problem Statement

  • Many systems, including examples arising from Newtonian mechanics, can be marginally stable, while prior learning rates often depend on the stability gap.The paper argues that this dependence can be avoided in many cases and replaced by less conservative quantities.Source: §1.1 · p. 3

1.2 Prefiltered Least Squares (PF-LS)

  • PF-LS learns a coarse linear filter from past observations, subtracts its predictions from outputs, and regresses the filtered outputs on inputs.The system model allows process and sensor noises chosen semi-adversarially with a T-step delay, covering stochastic and worst-case oblivious noise.Source: §1.1 · p. 2, §1.2 · p. 3
  • The oracle inequality compares the chosen filter with the best filter’s data-dependent prediction error and accounts for prefilter overfitting.Its oracle term captures the actual error sequence rather than an a priori upper bound.Source: §1.2 · p. 4

1.3 Organization

  • The paper presents LTI-system oracle bounds and phase-rank results, derives marginal-stability consistency, then develops the estimator analysis and proof sketches.Complete proofs and additional material are organized in three appendix parts.Source: §1.3 · p. 4

2 Rates for Learning LTI Systems

Prefiltered least squares yields learning guarantees for marginally stable LTI systems, including parameter recovery under minimality. Phase rank provides bounds that need not worsen with the stability gap.

2 Rates for Learning LTI Systems

  • The PF-LS oracle inequality is developed for both stochastic and adversarial noise models.Source: §2 · p. 5
  • Opt_μ ∼ N^1/2 for marginally stable systems with sufficiently large L, and Opt_μ need not depend on the stability gap 1−ρ(A⋆).The paper states these bounds as consequences of its PF-LS analysis.Source: §2 · pp. 5–6
  • Combining PF-LS with Ho-Kalman gives consistent parameter estimates for marginally stable systems when the realization is minimal.Minimality is necessary for identifiability in the stated recovery guarantee.Source: §2 · p. 6

2.1 Learning without the stability gap

  • Phase rank bounds Opt_μ using eigenvalue phases near the unit-disk boundary, avoiding worst-case dependence on the stability radius.It groups eigenvalues with approximately the same phase and is used to bound the estimator’s learning rate.Source: §2.1 · pp. 6–7
  • For real diagonalizable systems, phase rank is at most 2 regardless of stability radius, and it is zero for sufficiently strictly stable systems.Source: §2.1 · p. 7
  • When eigendirections can be disentangled through C⋆, the phase-rank penalty can be reduced to the maximum phase rank of smaller spectral portions.The paper also gives refinements that use more granular properties of the spectrum.Source: §2.1 · p. 7

3 Oracle Inequality for Prefiltered Least Squares

PF-LS prefilters outputs to approximate the best filter for reducing regression error, with an oracle inequality controlling the resulting estimator. The analysis combines fixed-filter bounds with conditions ensuring well-conditioned inputs and orthogonal residuals.

3 Oracle Inequality for Prefiltered Least Squares

  • The analysis requires well-conditioned concatenated inputs and uses Neyman orthogonality, since the filtered residual remains Ft−T-adapted and E[ut|Ft−1] = 0.Source: §3 · p. 8
  • Proposition 3.2 bounds the least-squares estimator’s error for any fixed filter in terms of that filter’s associated residual.The later oracle inequality addresses the difficulty of selecting a good filter a priori, including for marginally stable systems.Source: §3 · p. 8, §3.1 · p. 9

3.1 Statement of the Oracle Inequality

  • Output prefiltering essentially achieves the goal of choosing a filter with small residual, and Optµ represents the best-filter error with regularization.The oracle inequality also includes an effective dimension covering the filter, inputs, and observations.Source: §3.1 · p. 9
  • The oracle inequality holds with probability 1−δ−δU when the sample size satisfies Lemma 3.1’s conditions.Source: §3.1 · p. 9
  • The κµ term inside a logarithm is described as a proof artifact and is unnecessary when σmin(K) is bounded below.Source: §3.1 · p. 10

4 Proof Sketch for Bounding Optµ

The proof bounds the error of candidate filters by separating prediction error from noise introduced by truncating the history. Phase rank helps construct small-norm filters that reduce the prediction error, while the stochastic bound requires finite control-system norms.

4 Proof Sketch for Bounding Optµ

  • The error separates into prediction error and additional noise from shutting off inputs and noise beyond the truncated history.The shut-off noise contribution covers only TL time steps, while prediction error can grow with the state under marginal stability.Source: §4 · p. 10
  • A minimal-polynomial filter can make prediction error zero, but may require length up to n and have exponentially large coefficients that amplify noise.Source: §4 · p. 10
  • The bounds connect Optµ to phase rank and the largest Jordan block size of A⋆.Source: §4 · pp. 10–11
  • Small phase rank permits small-norm filters with small prediction error by using polynomial roots aligned with eigenvalue phases to offset state magnitude.In the two-mode example, a length-one filter cancels the marginally unstable mode and downweights a nearby stable mode.Source: §4 · p. 11
  • The stochastic error bound requires finite H∞ and M∞ norms, which in turn requires canceling modulus-1 eigenvalue effects.The proposition’s stated sample-size condition is N ≥ Td max{m, log(1/δ)}.Source: §4 · p. 12

5 Related Work

Prior work establishes least squares as a central tool for LTI system identification, but analyses of prefiltering and debiasing often impose restrictive stability, noise, or asymptotic conditions. This work contrasts its use of SVD post-processing with subspace identification and identifies extending SVD-based guarantees to marginal stability as future work.

5 Related Work

  • Analyses of prefiltering and debiasing schemes are often asymptotic, restricted to strictly stable systems, or based on limited noise models.PF-LS is viewed as a prefiltered autoregressive model, such as ARX or ARMAX.Source: §5 · p. 12
  • Subspace identification applies SVD to raw data, whereas this work uses SVD as a post-processing step with the Ho-Kalman algorithm, following Oymak and Ozay (2018) and Kung (1978).The passage identifies adapting SVD-based algorithms for marginally stable systems as future work.Source: §5 · p. 12
  • Non-asymptotic guarantees for partially observed systems have often relied on strict stability; alternatives require growing numbers of independent trajectories or additional system conditions [Shah et al., 2012, Hardt et al., 2016, Oymak, 2018, Hazan et al., 2017, 2018].The phase-rank condition is inspired by the ℓ1-norm of the minimal phase polynomial in Hazan et al. [2018].Source: §5 · p. 12
  • PF-LS is related to instrumental variables, used more for debiasing than denoising, while variance reduction is also studied in reinforcement learning and tabular Markov decision processes [Viberg et al., 1997, Hansen and Singleton, 1982, Angrist et al., 1996, Weaver and Tao, 2001, Greensmith et al., 2004, Tucker et al., 2017, Sutton and Barto, 1998, Kakade et al., 2018, Sidford et al., 2018].The related work describes these as connections beyond linear systems.Source: §5 · pp. 12–13

Notation

The notation defines shared mathematical conventions, the semi-parametric estimation variables and adaptation conditions, and the state-space quantities used to describe LTI systems.

Notation

  • General conventions define ≲ as inequality up to a universal constant and specify norms, singular values, logarithms, and index notation.The section also defines the unit sphere and matrix operator and Frobenius norms.Source: Notation · p. 21
  • Semi-parametric notation names inputs, observations, prefiltering features, errors, and their associated data matrices and filtration conditions.The input sequence is Gaussian conditional on the preceding filtration, while features are adapted to an earlier filtration.Source: Notation · p. 21
  • The effective sample size is e_N = N − N1, Nmin is a stated sample-size threshold, and φ_rdg denotes the filter from (1.4).The notation also identifies the PF-LS, least-squares, and fixed-filter estimators.Source: Notation · p. 21
  • LTI notation specifies inputs, states, observations, process and sensor noise, and state-space parameters, then defines transfer functions and Markov-parameter matrices.Additional definitions include filtered-system quantities, block spectra, Jordan decomposition, and system-norm constants.Source: Notation · p. 22

A Examples of Phase Rank

Phase rank counts the selected phase witnesses needed to cover large eigenvalues with their multiplicities. The examples show how coverage changes with the parameters and spectrum.

A Examples of Phase Rank

  • Phase rank is the number of selected phase witnesses needed to cover each eigenvalue near the unit circle, counting repeated eigenvalues according to multiplicity.The definition uses eigenvalues with magnitude at least 1 − ((1 + α)T)^−1.Source: A Examples of Phase Rank · p. 22
  • For unit-circle spectra, each witness contributes T equally spaced spokes; the (1, 2) phase rank is 2, while the (1, 4) phase rank is 1.The examples are shown in Figure 1.Source: A Examples of Phase Rank · p. 23, Figure 1 · p. 23
  • Increasing α widens the covering regions enough to include two additional eigenvalues, giving a (2, 4) phase rank of 1.Figure 1’s example (b) illustrates the increased α.Source: A Examples of Phase Rank · pp. 23–24, Figure 1 · p. 23
  • For spectra away from the unit circle, witnesses may also lie inside the unit disk; example (c) has phase rank 2, and example (d) covers a repeated eigenvalue and others with phase rank 2.In example (c), red bumps cover eigenvalues not at the listed phases; example (d) accounts for multiplicity while covering additional eigenvalues.Source: A Examples of Phase Rank · p. 24

B.1 Parts (a) and (b)

These appendix sections establish bounds and conditions supporting PF-LS analysis, a Ho-Kalman recovery step, and a lower bound showing ordinary least squares fails for marginally stable systems. The lower-bound proof proceeds through Gramian estimates and a Gaussian quadratic-form argument.

B.1 Parts (a) and (b)

  • Under the proposition’s sample-size, horizon, spectral-radius, and Jordan-block assumptions, a high-probability stochastic-noise bound is expressed using the prescribed parameters and phase-rank-related quantities.The passage also bounds the relevant dimension parameter d by a constant times log(N) for N ≥ 2.Source: §B.1 · p. 24

B.2 Part (c)

  • For part (c), the Ho-Kalman recovery argument uses observable and controllable system assumptions and combines its robustness bound with the preceding section’s result.The resulting state-space realization is related to the original through a unitary matrix.Source: §B.2 · pp. 25–26

C Lower Bound for OLS for Marginally Stable Systems

  • With a unit-modulus Jordan block and a minimal system, ordinary least squares is inconsistent even with zero process and sensor noise.The authors state the zero-noise condition is for simplicity and that the lower bound also extends to Gaussian noise.Source: C Lower Bound for OLS for Marginally… · p. 26

C.1 Proof of Proposition C.2

  • The first lower-bound component uses a small-ball argument to relate least-squares error to Gramian matrices, with a Gaussian quadratic-form bound as a key tool.The proof invokes the small-ball lemma and obtains a probability bound for the resulting quantity.Source: C Lower Bound for OLS for Marginally… · p. 26, §C.1 · p. 27

C.2 Proof of Lemma C.3

  • The second component lower-bounds the Gramian sum; controllability and observability give positive singular-value bounds, while a unit-modulus Jordan block supplies the growth condition.These ingredients yield the lemma’s lower bound under the stated minimality and Jordan-block assumptions.Source: C Lower Bound for OLS for Marginally… · p. 26, §C.2 · pp. 29–30

C.1.1 Proof of Lemma C.4

  • The Gaussian quadratic-form lemma is proved by symmetrizing and diagonalizing the matrix, then combining concentration with Paley-Zygmund.The concentration step uses a chi-squared inequality for nonnegative coefficients.Source: §C.1.1 · p. 28

D General Statement and Analysis PF-LS

This appendix develops the analysis and proof machinery for the general PF-LS statement, including a uniform oracle bound and a bound on the ridge filter’s deviation from its regularized optimum. It uses semi-parametric regression bounds, chaining, covering, norm bounds, and martingale arguments to control correlated inputs and support the theorem proofs.

D General Statement and Analysis PF-LS

  • Theorem D.1 bounds PF-LS uniformly over filters with low-dimensional slices and controls the ridge filter by the regularized optimum plus a fitting term.Taking all filters recovers a bound for the unrestricted filter class.Source: D General Statement and Analysis PF-LS · p. 31

D.1 Proof of Uniform Bound: Theorem D.1, Part (a)

  • The uniform guarantee is obtained by extending a fixed-filter bound over nets and covering arguments to all filters in the class.The proof reduces each direction to a low-dimensional filter space before applying the uniform argument.Source: §D.1 · pp. 32–33

Lemma D.3 (Properties of the Ridge Estimator)

D.2 Proof of g Optµ bound, Theorem D.1, Part (b)

  • The ridge-filter argument addresses that PF-LS has access to Y rather than Δ, using auxiliary lemmas to establish the part (b) bound.The proof begins with ridge-estimator properties and then bounds the discrepancy caused by observing Y instead of Δ.Source: Lemma D.3 (Properties of the Ridge… · p. 34

E Semi-Parametric Regression

  • For semi-parametric regression with mean-zero, 1-subgaussian noise, Theorem E.1 provides bounds whose analysis accounts for dependencies in the concatenated sequence.The theorem’s bounds are used to derive Proposition 3.2; the appendix notes an additional factor of T on the m and log(1/δ) terms and uses chaining to avoid paying pT^2.Source: E Semi-Parametric Regression · pp. 36–37

E.1 Proof of Theorem E.1, Part (a)

  • The proof uses a data-dependent variance proxy for the regression error and adaptedness to apply a generalized martingale bound.The variance proxy is motivated by the covariance in a deterministic-input case and is used when both the inputs and errors are martingales.Source: §E.1 · p. 38
  • A chaining argument bounds the supremum by treating the proof’s random variables as subgaussian with a random offset.The argument introduces the Toeplitz operator norm as a metric and applies chaining to increments.Source: §E.1 · pp. 39–40

E.2 Proof of Theorem E.1, Part (b)

  • An epsilon-net and union bound extend the scalar estimate to an operator-norm bound, followed by an iterated-logarithm conversion.The proof uses a covering argument for the sphere and invokes Lemma E.6 for the final conversion.Source: §E.2 · p. 41

E.3 Proof of Lemma E.3

  • The Toeplitz operator norm used in the proof is bounded below by the vector’s Euclidean norm and above by an ℓ1 bound on its coefficient sequence.The lower bound follows from the first row of the Toeplitz matrix; the upper bound uses a norm-contraction inequality and a Toeplitz-matrix operator-norm bound.Source: §E.3 · p. 42

E.4 Proof of Lemma E.2

  • The self-normalized martingale lemma follows the proof of Theorem 3 in Abbasi-Adkori (2011), adapting it to matrix-valued variance and vector-valued noise.The proof verifies a supermartingale using the subgaussian noise condition and concludes with optional stopping.Source: §E.4 · p. 42

F Chaining for Self-Normalized Tail Inequalities

  • Theorem F.2 extends generic chaining to offset-subgaussian processes, with an additional bound stated for normed spaces.The section introduces the theorem as an extension of generic chaining for typical subgaussian processes; the supplied passage does not include the bounds’ full formulas.Source: F Chaining for Self-Normalized Tail… · p. 43

F.1 Proof of Proposition E.5

The proof refines generic chaining to remove sample-size dependence, using covering arguments tailored to the relevant norm. It also extends bounds to nonzero initial states under both stochastic and adversarial noise.

F.1 Proof of Proposition E.5

  • The proof modifies generic chaining to remove an otherwise arising dependence on the sample count N.It uses Dudley’s inequality and a key lemma to avoid a bound based on a set whose size grows with N.Source: §F.1 · p. 44

F.1.1 Proof of Lemma F.4

  • A finite set Z of at most 16π(Tp)^(3/2) vectors with infinity norm at most 1 controls the norm ∥v∥⊖ by its largest inner product with v.The set provides a finite representation for bounding the norm in the covering argument.Source: §F.1 · p. 44

F.2 Proof of Theorem F.2

  • The chaining partitions are chosen using distances in the metric space, not the process variances σ or offsets μ.This supports the extension of the chaining argument to processes with offsets.Source: §F.2 · p. 46

Part III Prefiltered Least Squares for Linear Dynamical Systems

  • For nonzero initial state x1, the paper gives high-probability bounds for prefiltered least squares under both stochastic and adversarial noise when N ≥ Td max{m, log(1/δ)}.The stochastic and adversarial cases are stated separately in Propositions G.1 and G.2.Source: Prefiltered Least Squares for Linear… · p. 48

G.1 Outline of the Proofs

The proof outline decomposes the prefiltered estimation error into contributions from inputs, noise, and the initial state. It bounds these terms using block-structured operators and chaining arguments.

G.1 Outline of the Proofs

  • The outline decomposes the error and treats input, process-noise, sensor-noise, and initial-state contributions separately.The proof bounds two principal terms first, then addresses process noise, output noise, and the initial state.Source: §G.1 · pp. 49–50

G.2 Bounding G(1)

  • For G(1), the proof uses block Toeplitz structure and chaining; direct chaining could replace a √m factor with a matrix stable-rank term.The authors note that their bound is loose in this respect.Source: §G.2 · pp. 50–51

G.3 Bounding G(2)

  • For G(2), shifted block Toeplitz structure and a Toeplitz-matrix norm bound support the error estimate.The rows of the relevant matrix can be embedded in a block Toeplitz matrix.Source: §G.3 · p. 52

G.4.1 Process noise

  • The process-noise contribution is handled using the stochastic martingale structure or a direct bound in the adversarial case.The stochastic argument applies the same calculations used for G(1) and G(2).Source: §G.4.1 · p. 53

G.4.2 Output noise

  • The output-noise analysis gives separate bounds for stochastic and adversarial noise.The stochastic case invokes Proposition G.3; the adversarial case is treated separately.Source: §G.4.2 · p. 53

G.4.3 Contribution of the initial state

  • The proof isolates the initial state’s nonzero contribution to Δφ as a separate term.This contribution is distinct from the input and noise contributions in the error decomposition.Source: §G.1 · p. 49, §G.4.3 · p. 53

H.1 Notation

  • The generalized constants account for nonzero x1 and reflect the conditioning of the chosen realization of G⋆.The definitions reduce to those in the main text when x1 = 0.Source: §H.1 · p. 54

H.2 Proof of Proposition 2.1

This section develops proof bounds for Proposition 2.1 and related linear-system quantities, including data-dependent selection of L and polynomial-approximation tools. It establishes bounds for a phase-rank-based filter and Jordan-normal systems, including worst-case bounds on K1 and K2 under specified spectral and rank conditions.

H.2 Proof of Proposition 2.1

  • On EU, Lemma H.2 bounds deff(Optµ + Ovfitµ, Lm, µ) by dg Opt, whose displayed terms begin ep + Lm log+(g Opt); combining with Lemma H.2 yields a result with probability at least 1 −δ −δU.Source: §H.2 · pp. 54–55

H.3 Proof of Lemma H.2

  • Lemma H.2 bounds effective dimension using terms involving the prediction error, Lm, g_Opt, N, and µ.The proof applies a generic bound with Opt set to Opt_µ + Ovfit_µ and L set to Lm.Source: §H.3 · p. 57

H.4 Selecting the parameter L

  • The section proposes a data-dependent proxy for Opt_µ + Ovfit_µ and uses structural risk minimization to select L.Proposition H.4 gives a high-probability guarantee under stated conditions, including a condition evaluable by the learner; Proposition H.5 gives an analogue for the selected L under ρ(A⋆) ≤ 1 and largest Jordan block size k.Source: §H.4 · pp. 58–59

H.4.1 Proof Sketch of Proposition H.4

  • For fixed v ∈ S^{m−1}, Lemma H.6 gives ∥(Y−Kφrdg)v∥₂ ≥ 1 with probability 1−δ for any j satisfying its condition, when N ≳ T(ep + m + Lmej + log(1/δ)).For m = 1, Lemma H.7 states a result for fixed φ when N ≳ T(ep + log(1/δ)), with probability at least 1−δ on EU.Source: §H.4.1 · p. 60

I Polynomial Approximations and Phase Rank

  • The polynomial-approximation section presents refined stochastic and adversarial bounds and results under a condition that system modes can be disentangled, including through C⋆.It introduces K1 for polynomial complexity in canceling large modes and K2 for growth of finite-length Markov parameter matrices.Source: I Polynomial Approximations and Phase… · pp. 61–62

I.1 Main Results

  • The main-results setup represents A⋆ through its Jordan decomposition and treats the spectrum of A⋆ and its Jordan form interchangeably.Source: §I.1 · p. 62

I.1.1 K1 and K2: Controlling Poles and Markov Operator Norms

  • K1(d, T, α, q) measures how well a length-d linear filter predicts observations of the Jordan-normal system with (α, T) phase rank d.Prediction is defined using the operator norm of M∞ for q = 2 and the H∞ norm for q = ∞.Source: §I.1.1 · p. 62
  • Taking q = ∞ corresponds to the H∞ norm, while q = 2 corresponds to the operator norm ∥M∞(·)∥op, associated with a transfer-function norm slightly sharper than standard H2.Source: §I.1.1 · p. 62
  • If A⋆ has (α, T)-phase rank d, a filter φ ∈ R^{m×dm} exists with 1 + ∥φ∥bop ≤ 2d.Source: §I.1.1 · p. 63
  • Analogous bounds for Fφ and Hφ replace ∥S−1B⋆∥op with ∥S−1Bw∥op and ∥S−1x1∥op, respectively.Source: §I.1.1 · p. 63
  • K2(N) describes the magnitude of an entire length-N trajectory generated by the Jordan-normal system J⋆, and a proposition bounds its Markov parameters for every n ≥ 1.Source: §I.1.1 · p. 63
  • Worst-case bounds on K1 and K2 are stated for A⋆ with ρ(A⋆) ≤ 1, largest Jordan block size k, and (α, T)-phase rank at most d ≥ k.Source: §I.1.1 · p. 63

I.1.2 Main Results: Stochastic Noise with Block-Scalar Filters

This section develops bounds for filtered least squares with block-scalar filters, including stochastic and adversarial settings and filters tailored to invariant subspaces. It supports these bounds with analysis of filtered transfer functions, spectral-block outputs, Jordan-block resolvents, and polynomial approximations subject to spectral root conditions and degree.

I.1.2 Main Results: Stochastic Noise with Block-Scalar Filters

  • Theorem I.4 and Proposition 2.3 give high-probability stochastic-noise bounds under phase-rank and sample-size conditions.The proof combines bounds on filtered transfer terms with finite-horizon terms and the filter norm.Source: §I.1.2 · p. 64, §I.3 · p. 70

I.1.3 Results for Adversarial Noise

  • Theorem I.5 and Corollary I.6 provide analogous bounds under the adversarial-noise model.The proof is described as essentially identical to the stochastic case.Source: §I.1.3 · pp. 64–65

I.1.4 Bounds for Disentangling Filters

  • When transformed observations separate invariant subspaces, disentangling filters yield stochastic bounds for systems whose partitioned blocks each have bounded phase rank.The construction uses an admissible spectral partition and a matrix that disentangles it.Source: §I.1.4 · pp. 65–66

I.2 Polynomial Approximations for Linear Dynamical Systems

  • Polynomial approximation quantifies pole cancellation: Proposition I.11 bounds a Jordan-block transfer norm, with a refined factor when polynomial degree is below block size.Poles on the unit circle may need cancellation for the relevant H2 or H∞ norms to be finite.Source: §I.2 · p. 67

I.2.1 Approximations Using Block-Scalar Filters: Proof of Proposition I.1

  • For block-scalar filters, polynomial coefficients define filters with controlled norm; bounded phase rank guarantees a suitable degree-d polynomial.The proof of Proposition I.13 uses roots witnessing phase rank and bounds the polynomial’s ℓ1-norm by 2d.Source: §I.2.1 · p. 68, §J.1.2 · p. 71

I.2.2 Approximations using Disentangling Filters

  • For a disentangled spectral partition, polynomial choices for each part yield a filter whose norm is controlled by the transformation’s condition number, partition size, degree, and coefficient bound.The result also has H2 analogues, replacing H∞ by H2.Source: §I.2.2 · p. 68

J.1.2 Proof of Proposition I.13

  • For |z−λ|≤1−|λ|, Lemma J.2 bounds F(z) by T^k 2^(d−k).The proof also treats eigenvalues near the unit circle using the phase-rank witnesses, separately from eigenvalues further inside the unit disk.Source: §J.1.2 · pp. 71–72

J.1.3 Proof of Theorem I.14

  • The Theorem I.14 proof partitions the output across spectral subsets and applies prior bounds to establish H∞ control; the H2 argument is similar.Each output block is supported on its corresponding spectral subset, and the proof invokes Proposition I.11 and Theorem I.12.Source: §J.1.3 · pp. 73–74

J.1.4 Proof of Proposition I.11

  • For block-diagonal transfer functions, the H∞ norm equals the largest block norm; the Jordan-block bound improves from k² to k(d+1) when d<k.The proof assumes f has a root of order at least k at each unit-modulus eigenvalue; when f has that multiplicity at a Jordan block, f(J)=0.Source: §J.1.4 · p. 75, Proof · pp. 75–76

Proof

  • Cauchy’s integral formula bounds the Jordan-block resolvent terms, yielding a bound over at most k(k∧(d+1)) terms.For a degree-d polynomial, derivatives above degree d vanish, which limits the terms in the bound.Source: Proof · pp. 76–77

J.2 Bounds on Finite System Norms: Proof of Proposition I.2

The appendix bounds finite-system norms using Jordan-block structure, then derives estimation bounds under strong observability for stochastic and adversarial noise. Strong observability supplies a stable state-reconstruction condition, with a minimal-polynomial alternative when it fails.

J.2 Bounds on Finite System Norms: Proof of Proposition I.2

  • The proof of Proposition I.2 reduces the operator-norm bound to a single Jordan block and treats stable eigenvalues before arbitrary ones.It bounds powers using the first-row ℓ1 norm and divides the resulting sums into three cases.Source: §J.2 · pp. 78–80

K Bounds under Strong Observability

  • Strong observability requires that d observations spaced T steps apart reconstruct the hidden state numerically stably, enabling bounds on Optµ.The bound also applies when strong observability fails if L exceeds the degree of A+’s minimal polynomial, with the stated complexity terms replaced by 2d+ and d+.Source: K Bounds under Strong Observability · pp. 80–81

K.1 Granular Bounds for Strong Observability

  • Strong observability yields high-probability estimation bounds for stochastic noise, with an analogous bound under adversarial noise.The stated sample-size condition is N ≥ Td max{m, log(1/δ)}.Source: §K.1 · p. 82

K.2 Proof of Theorem K.2

The proof constructs a filter that removes contributions from the strongly observable modes and bounds its norm. It then applies stochastic and adversarial error bounds to the remaining systems, with cancellation and operator-norm arguments supporting the estimates.

K.2 Proof of Theorem K.2

  • An observability-based filter can annihilate A+ while bounding its norm using the observability singular-value condition.When strong observability fails, a filter based on A+’s minimal polynomial instead has norm at most 2n+.Source: §K.2 · p. 83

K.3 Proof of Proposition K.3

  • When Cφ[A+] = 0, Lemma K.6 states that Propositions G.1 and G.2 hold with Gφ, Fφ, and Hφ replaced by specified systems; corresponding norm bounds use factor 1 + ∥φ∥bop.For example, ∥(Gφ)−∥H∞ ≤ (1 + ∥φ∥bop)∥G−∥H∞, with corresponding bounds for F and H.Source: §K.3 · p. 84

K.3.1 Proof of Lemma K.7

  • The H∞-norm argument treats it as the asymptotic limit of the operator norm of an associated Toeplitz operator.The passage cites Tilli (1998), Corollary 4.2.Source: §K.3.1 · p. 85

K.3.2 Proof of Lemma K.6

  • The invariant decomposition cancels the plus-mode term through products involving A−A+ or C−A+, leaving a term controlled analogously to Err(1).Source: §K.3.2 · p. 85
Loading 1902.00768v1…