PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Linear Dynamical Systems via Spectral Filtering

Elad Hazan, Karan Singh, Cyril Zhang

arXiv:1711.00946v1cs.LGcs.SYeess.SYmath.OCstat.ML

TL;DR

System identification seeks LDS parameters that predict unseen data, but direct optimization is non-convex. The paper uses a convex relaxation with spectral filtering and reports near-optimal regret alongside experimental gains in prediction quality and runtime.

  • Problem

    System identification seeks LDS parameters from sample trajectories that generalize to unseen data, while direct optimization is non-convex.

    Source: §1 · p. 1

  • Method

    The approach overparameterizes predictors by a polylogarithmic factor to obtain a convex online program, using wave filters based on Hankel-matrix spectral structure.

    Source: §1 · p. 1, §4.1 · p. 7

  • Results

    The algorithm attains near-optimal regret and experimentally outperforms traditional system identification in prediction quality and running time.

    Source: §6 · p. 10

  • Takeaways & Limitations

    The authors present spectral filtering as a tool that may extend to more general cases and other non-convex learning problems.

    Source: §6 · p. 10

    Theoretical regret guarantees apply to symmetric transition matrices, although experiments suggest success on some non-symmetric and nonlinear systems.

    Source: §5.2 · p. 10

Abstract

from arXiv · show

We present an efficient and practical algorithm for the online prediction of discrete-time linear dynamical systems with a symmetric transition matrix. We circumvent the non-convex optimization problem using improper learning: carefully overparameterize the class of LDSs by a polylogarithmic factor, in exchange for convexity of the loss functions. From this arises a polynomial-time algorithm with a near-optimal regret guarantee, with an analogous sample complexity bound for agnostic learning. Our algorithm is based on a novel filtering technique, which may be of independent interest: we convolve the time series with the eigenvectors of a certain Hankel matrix.

1 Introduction

The paper reframes LDS system identification as online learning and uses a carefully overparameterized convex relaxation. It gives regret and sample-complexity guarantees, with experiments reporting practical prediction and runtime benefits.

1 Introduction

  • System identification seeks LDS parameters from sample trajectories that generalize to unseen data; expectation-maximization can find poor local optima.Source: §1 · p. 1
  • Overparameterizing the predictor class by only a polylogarithmic factor makes the online loss convex and amenable to efficient regret minimization.The approach does not assume that data or predictions arise from an LDS.Source: §1 · p. 1
  • Experiments on toy data and a physical simulation report competitive predictive performance, greater stability, and significantly faster runtime than existing algorithms.Source: §1 · p. 1

1.1 Our contributions

  • The algorithm achieves nearly optimal convergence to the lowest MSE realizable by a symmetric LDS, with polynomial-time online predictions compared against the best symmetric LDS.Source: §1.1 · p. 2
  • The batch algorithm provides an analogous sample-complexity bound for agnostic learning from arbitrary training-sequence distributions.The signal need not be generated by an LDS.Source: §1.1 · p. 2

1.2 Related work

  • Prior gradient-descent guarantees [HMR16] are essentially SISO, depend on spectral gap, and require LDS-generated signals, unlike this paper’s MIMO and arbitrary-signal setting.Source: §1.2 · p. 3

2 Preliminaries

The preliminaries frame LDS prediction as online system identification and motivate replacing non-convex parameter learning with a convex relaxation. They establish the symmetric stable-system setting and introduce Hankel-matrix spectral decay as a tool for constructing the relaxation.

2.1 Linear dynamical systems

  • The model covers discrete time-invariant MIMO systems with finite-dimensional hidden states, assuming a stable, symmetric positive-semidefinite transition matrix.The stability assumption permits ∥A∥2 = 1; the method does not require the stronger condition that ∥A∥ be bounded away from 1.Source: §2.1 · p. 3

2.2 Sequence prediction as online regret minimization

  • Polynomial-time prediction achieves essentially the optimal regret bound otherwise available through an exponential-sized discretization of LDS parameters.The online learner is evaluated against the best LDS in hindsight, under bounded inputs and Lipschitz outputs.Source: §2.2 · p. 4

2.3 The power of convex relaxations

  • Improper learning enlarges the predictor class so losses become convex while the best predictor remains nearly as good as the best LDS.The overparameterization has approximation factor independent of ∥A∥ and sample complexity scaling as ˜O(polylog(T, 1/ε)).Source: §2.3 · pp. 4–5

2.4 Low approximate rank of Hankel matrices

  • The analysis uses exponential spectral decay of positive-semidefinite Hankel matrices, whose entries are constant along anti-diagonals.The Hilbert matrix is given as an example of this matrix family.Source: §2.4 · p. 5

3 The wave-filtering algorithm

Wave-filtering builds features by convolving the input history with top eigenvectors of a Hankel matrix, then learns a linear map over those features using online projected gradient descent. The resulting hypothesis class approximately contains LDS predictors while using only polylogarithmically many filters.

3 The wave-filtering algorithm

  • Online projected gradient descent updates a matrix mapping the featurized inputs to predictions using squared loss.The features include filter convolutions and the current and previous inputs and previous output.Source: §3 · p. 5
  • The feature vector combines input-history convolutions with a bank of k filters and the values x_(t−1), x_t, and y_(t−1), where k is polylogarithmic in T.The filters are selected from the top eigenvectors of the Hankel matrix Z_T.Source: §3 · p. 5
  • The learned matrices represent a hypothesis class of dimension ˜O(poly(m, n, d, log T)) that approximately contains the original LDS parameter class.The original class has dimension O((m + n + d)^2).Source: §3 · p. 5
  • The filters resemble vibrational modes of an inhomogeneous spring, and numerical ODE solutions can provide high-order filters that are difficult to obtain by eigenvector computation.Figure 1 compares a computed filter with an ODE solution and notes the difficulty of obtaining some high-order filters by eigenvector computations.Source: §3 · p. 6, Figure 1 · p. 6

4 Analysis

The analysis establishes a convex relaxation that approximates symmetric LDS predictions, then uses online regret minimization to compete with the best LDS in hindsight. Its guarantees rely on wave filters that approximate the system’s response to past inputs.

4.1 Approximate convex relaxation via wave filters

  • With k = Ω(log T log(RΘRxLynT/ε)) filters, the relaxation provides an ε-approximation for predictions of any symmetric LDS.The theorem constructs a matrix in the relaxed hypothesis class corresponding to the LDS.Source: §4.1 · p. 7
  • The past-input response vectors µ(α) are approximated by linear combinations of wave filters, leaving residuals exponentially small in k/log T.The residuals arise from discarding a subspace of dimension T − k.Source: §4.1 · pp. 7–8

4.2 From approximate relaxation to low regret

  • Algorithm 1 uses online gradient descent on quadratic, convex losses over a bounded matrix set to obtain the regret guarantee.The analysis controls the set diameter and gradient norm, including convolutions of inputs by ℓ2-unit vectors.Source: §4.2 · p. 8
  • Algorithm 1’s regret analysis transfers the convex learner’s guarantee to the best LDS in hindsight through an arbitrarily close comparator.The analysis bounds the decision-set diameter and gradient to complete the regret argument.Source: §4 · p. 6, §4.2 · p. 8
  • Allowing the comparator a nonzero initial hidden state increases online regret by at most an additive ˜O(log^2 T).The analysis first assumes h0 = 0 and then removes that assumption.Source: §4.1 · p. 6, §4.2 · p. 8

5 Experiments

Experiments compare wave-filtering with traditional system-identification methods on difficult synthetic systems and a forced pendulum. The method matches the best LDS in one synthetic case, while its guarantees remain limited to symmetric transition matrices.

5.1 Synthetic systems: two hard cases for EM and SSID

  • The traditional identification pipeline runs more than 1000 times slower than the proposed method.The pipeline runs EM or SSID followed by Kalman filtering.Source: §5.1 · p. 9
  • For the ill-conditioned SISO system (n=m=1, d=2), EM and SSID reach local optima while our method predicts as well as the best possible LDS; in the high-dimensional non-convex problem, EM and SSID consistently fail to converge.A=diag(0.999, 0.5).Source: §5.1 · pp. 9–10

5.2 The forced pendulum: a nonlinear, non-symmetric system

  • The method appears experimentally to learn a forced pendulum despite its nonlinear, non-symmetric dynamics, but regret guarantees cover only symmetric transition matrices.The pendulum experiment uses Gaussian noise and random block impulses.Source: §5.2 · p. 10

6 Conclusion

The paper concludes that online wave-filtering achieves near-optimal regret in theory and outperforms traditional system identification in prediction quality and running time in experiments. It also outlines batch formulations and an offline least-squares analogue for learning response differences.

6 Conclusion

  • Online wave-filtering attains near-optimal regret in theory and experimentally outperforms traditional system identification in prediction quality and running time.The spectral filtering technique convolves the time series with eigenvectors of a Hankel matrix.Source: §6 · p. 10

Guide to the Appendix

  • The appendices cover batch sample-complexity results, algorithm variants and implementation, relaxation and regret proofs, and Hankel spectral-decay bounds.The spectral-decay results are adapted from [BT16].Source: Guide to the Appendix · p. 12

A Batch variants of the algorithm

  • The batch setting treats each length-T rollout as one sample because outputs within a trajectory are correlated and cannot be assumed independent.The two formulations use N samples of concatenated inputs and responses.Source: A Batch variants of the algorithm · p. 12

A.1 Learning the derivative: the direct analogue

  • The direct batch analogue learns response differences from input features using least squares, yielding an improper agnostic learning guarantee.The features use the online algorithm’s featurization; the relaxation uses k = Ω(log T log(RΘRxLynT/ε)).Source: §A.1 · pp. 12–13

A.1.1 Generalization bound

The batch analysis derives a generalization bound for empirical-MSE minimization in a relaxed hypothesis class, then treats pure-batch prediction and extensions for nonzero or distinguishable initial states.

A.1.1 Generalization bound

  • Theorem 2 gives a sample-complexity guarantee for Algorithm 2’s empirical-MSE minimizer in the relaxed class, under the stated LDS parameter constraints and choice of k.The argument combines a Rademacher-complexity generalization bound with the approximation result.Source: §A.1.1 · pp. 13–14

A.2 The pure batch setting

  • In pure-batch prediction, integrating derivative predictions with MSE ε can accumulate error to Tε, and the agnostic guarantee costs a factor of T^2 in sample complexity.A low-noise approximation result is also given for noiseless LDS outputs.Source: §A.2 · p. 14

A.2.1 Filters from the Hilbert matrix

  • Hilbert-matrix eigenvector filters work well in practice, but their approximation guarantee is insufficient for the paper’s strong regret and agnostic-learning bounds.The Hilbert matrix has the same spectral decay as Z_T; its filters are considered as an alternative in the realizable setting.Source: §A.2.1 · p. 15

A.3 Learning the initial hidden state via hints

  • In batch learning at fixed T, the initial-state contribution does not vanish as the sample count grows, leaving an approximation-error floor that more filters cannot remove.The paper proposes an augmented setting that supplies a transformed initial-state hint, requiring the transformation to be well-conditioned.Source: §A.3 · p. 15

A.3.1 Initializations with finite support

  • With finitely many distinguishable initial states, augmenting each sample with its one-hot initialization lets the stated theorems apply with hidden dimension increased by the number of states.The proposition assumes d′∥h0∥≤RΘ.Source: §A.3.1 · p. 15

B Implementation and variants

The appendix gives practical guidance for constructing and using the filters, along with proof details for the spectral approximation underlying the relaxation theorem.

B.1 Computing the filters via Sturm-Liouville ODEs

  • The Hankel-derived filters are difficult to compute directly, so the authors use a Sturm–Liouville ODE approximation as a practical construction recipe, without quantified theoretical bounds.They report that performance is insensitive to the precise eigenvalues and ODE boundary conditions.Source: §B.1 · p. 16

B.2 Alternative low-regret algorithms

  • Online gradient descent can be replaced by other low-regret updates, including AdaGrad; for low-noise realizable data, follow-the-leader reduces the update to linear regression.The regression can be solved iteratively, with the previous predictor used as a warm start.Source: §B.2 · p. 16

B.3 Accelerating convolutions

  • When inputs are known in advance, FFT-based convolution computes all features in O(nkT log T) time, avoiding quadratic dependence on T.The convolutions are computed by pointwise multiplication in the Fourier domain.Source: §B.3 · p. 17

C.1 Proof of Lemma 4.1

  • The relaxation proof bounds average reconstruction error through the Hankel matrix’s spectral tail, then extends the bound to every α using the residual’s Lipschitz property.The proof applies the spectral estimate to the original setting to obtain the low-rank approximation result.Source: §C.1 · pp. 17–18

C.2 Proof of Theorem 3

The proof concludes that each symmetric LDS predictor for the discrete derivative can be approximated by a filter-based predictor, with error decreasing exponentially as the number of filters grows.

C.2 Proof of Theorem 3

  • Increasing the number of filters k drives the pointwise prediction residual for every system exponentially lower, establishing the relaxation approximation.The proof bounds the original setting by applying the spectral reconstruction result to input-coordinate sequences.Source: §C.2 · p. 18

D Proof of the main regret bound

The appendix assembles comparator-size and gradient bounds into the regret analysis, and shows that allowing a nonzero initial hidden state does not worsen the asymptotic online regret bound.

D.1 Diameter bound: controlling the comparator matrix

  • The relaxed comparator matrix has controlled Frobenius norm, yielding a bounded-diameter comparator class for regret analysis.The associated prediction bound applies when the matrix norm is O(R^2 k).Source: §D.1 · p. 19

D.2 Gradient bound and final details

  • Although filter convolutions can produce large feature vectors, the scaled convolution coordinates are bounded by O(Rx log T), enabling a gradient bound.The feature vector contains nk such coordinates together with the current and previous inputs.Source: §D.2 · p. 20

D.3 Assembling the regret bound

  • The assembled online-gradient-descent regret bound uses a constant relaxation approximation error, since that error is not the online regret bottleneck.The analysis collects comparator-diameter and gradient bounds before stating the regret bound.Source: §D.3 · p. 20

D.4 Diminishing effect of the initial hidden state

  • Allowing a nonzero initial hidden state increases regret additively by at most the stated bound and does not improve the asymptotic regret rate.The analysis attributes the diminishing effect to decay in the initial state’s influence on the derivative of the impulse response.Source: §D.4 · p. 21

E Properties of the Hankel matrix ZT

  • The appendix defines the Hankel matrix Z_T through entries depending on the sum of the row and column indices.The supplied expression is Z_ij = 2/(i+j)^3 − (i+j), as printed in the passage.Source: E Properties of the Hankel matrix ZT · p. 21

E.1 Spectral tail bounds

The appendix bounds the Hankel matrix’s spectral tail and gaps, then controls reconstruction coefficients and filter norms used in the analysis.

E.1 Spectral tail bounds

  • For T ≥ 10, the Hankel matrix spectrum has an exponential tail, with c = e^(π^2/4) ≈ 11.79.The stated bound includes σ_j < 235200 · c^(-j/log T).Source: §E.1 · p. 22
  • For T ≥ 60, the sum of four consecutive singular values is less than 400 log T times σ_j.The passage writes this sum as σ′_j = β_j + β_(j+1) + β_(j+2) + β_(j+3).Source: §E.1 · pp. 22–23

E.2 Decaying reconstruction coefficients

  • For uniformly sampled α, the squared projection coefficient is bounded in expectation using the 3-Lipschitzness of ∥μ(α)∥₂.Projection onto the one-dimensional span of φ_j is contractive, so the squared coefficient inherits the Lipschitz property.Source: §E.2 · p. 23

E.3 Controlling the ℓ1 norms of filters √

  • The ℓ₂ → ℓ₁ subordinate norm of Z^(1/4) is bounded by 2 + 2 log₂ T.The proof obtains the logarithmic bound by iterating a matrix-doubling argument.Source: §E.3 · pp. 23–24

F Properties of µ(α)

The appendix establishes elementary bounds for μ(α) and uses them to bound the Lipschitz constant of a true LDS under stated assumptions.

F Properties of μ(α)

F.1 The Lipschitzness of a true LDS

  • When 0 ≼ A ≼ I and the LDS parameters satisfy the stated norm bounds, its Lipschitz constant is bounded by ∥B∥F ∥C∥F R_x.The appendix also establishes that μ(α) has small ℓ1 and ℓ2 norms, with the ℓ2 norm Lipschitz in α.Source: §F.1 · p. 25, F Properties of µ(α) · p. 25

Related papers

Loading 1711.00946v1…