Online Spectral Identification of Dynamical Systems

Recently, a number of researchers have proposed spectral algorithms for learning models of nonlinear dynamical systems—for example, Hidden Markov Models (HMMs) [1, 2], Partially Observable Markov Decision Processes (POMDPs) [3], and Predictive State Representations (PSRs) [4, 3, 5]. These algorithms are attractive since they are statistically consistent and not subject to local optima. However, they are batch methods: they need to store their entire training data set in memory at once and operate on it as a large matrix, and so they cannot scale to extremely large data sets (either many examples or many features per example). In turn, this restriction limits their ability to learn accurate models of complex systems.