Spectral Filtering for General Linear Dynamical Systems

By Elad Hazan, Holden Lee, Karan Singh, Cyril Zhang, Yi Zhang. 2018

109 citations recorded by the source corpus.

We give a polynomial-time algorithm for learning latent-state linear dynamical systems without system identification, and without assumptions on the spectral radius of the system's transition matrix. The algorithm extends the recently introduced technique of spectral filtering, previously applied only to systems with a symmetric transition matrix, using a novel convex relaxation to allow for the efficient identification of phases.

Subfields: Artificial Intelligence, Control and Systems Engineering, Management Science and Operations Research, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Control and Systems Engineering

In Management Science and Operations Research

In Signal Processing

Citations in the corpus

A Convergence Theory for Deep Learning via Over-Parameterization (2018, neutral): “Recent works in this line of research include [1, 9, 17, 18, 28–30, 41, 44, 50].”
On the Convergence Rate of Training Recurrent Neural Networks (2018, background): “Followups in this line of research include [27, 28].”
On the Sample Complexity of the Linear Quadratic Regulator (2017, background): “the Bellman rank is bounded by n2. While this result is appealing from an information-theoretic standpoint, the proposed algorithm is computationally intractable for continuous problems. Hazan et al. [28, 29] study the problem of prediction in a linear dynamical system via a novel spectral ltering a”
Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator (2018, background): “(Hazan et al., 2017; Arora et al., 2018) are restricted to systems with symmetric dynamics (symmetric A matrix), while (Hazan et al., 2018) handles a more general setting.”
Robust Spectral Filtering and Anomaly Detection (2018, methodology): “We note that the new hypothesis class Ĥ arising from the over-parametrization [18] has been shown by [18] to approximately contain the class of LDS satisfying Assumption 1, which makes it possible to derive regret bounds considering the convexification:”