Spectral Filtering for General Linear Dynamical Systems
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.
Summary ------- This paper presents an algorithm for predicting the (one-step ahead) output of an unknown linear time-invariant dynamical system (LDS). They key benefits of the proposed algorithm are as follows: - the regret (difference between the prediction error of the algorithm, and the prediction error of best LDS) is bounded by sqrt(T) (ignoring logarithmic factors), where T is the length of the data sequence over which predictions are made. - the regret bound does not depend on the spectral radius of the transition matrix of the system (in the case that data is generated by a LDS). - the algorithm runtime is polynomial in the 'natural parameters' of the problem.  The algorithm is based on a recently proposed 'spectral filtering' technique [HSZ17]. In previous work, this method was only applicable to systems with a symmetric transition matrix (i.e. real poles). The present paper extends the method to general LDSs (i.e. non-symmetric transition matrices, or equivalently, complex poles).  The performance of the proposed algorithm is illustrated via numerical simulations, and is compared with popular existing methods including expectation maximization (EM) and subspace identification.   Quality ------- In my view, the paper is of very high quality. The technical claims are well-substantiated by thorough proofs in the supplementary material, and the numerical experiments (though brief) are compelling and relevant (i.e. comparisons are made to methods that are routinely used in practice).   Clarity ------- In my view, the paper is well-written and does a good job of balancing technical rigor with higher-level explanations of the key concepts. Overall, it is quite clear. I do have a few comments/queries:  In my opinion, the supplementary material is quite crucial to the paper; not just in the obvious sense (the supplementary material contains the proofs of the technical results), but personally, I found some of the sections quite difficult to follow without first reading the supplementary material, e.g. Section 4.1. I very much like the idea of giving a high-level overview and providing intuition for a result/proof, but to be honest, I found it quite difficult to follow these high-level discussion without first reading through the proofs. This is probably the result of a combination of a few factors: i) the results are quite technical, ii) these ideas (spectral-filtering) are quite new/not yet well known, iii) my own limitations. This is not necessarily a problem, as the supplementary material is well written.  Regarding the presentation of some of the technical details:  Should \Theta be \hat{\Theta} in Line 188 and equation (5)?  In the supplementary material, the reference to (equation?) (2) doesn't seem to make sense, e.g., line 33 but also elsewhere. Do you mean Definition 2?  In Line 18, do you mean \sum_{j=0}^\tau\beta_jA^{i-j} = A^{i-\tau}p(A) = 0?  In equation (10), is there an extra C?  It's not a big deal, but i is used as both sqrt(-1) (e.g. (29)) and as an index, which can be a little confusing at first.  Below (28), should M'_\omega be M'_l? Furthermore, should M'_l be complex, not real?  If M'_l is real, then where does (31) come from? (I would understand if M'_l was complex).  Are the r's in (38) and below missing an l subscript?     Concerning reproducibility of numerical results:  I would imagine that the numerical results are a little difficult to reproduce. For instance, the details on the EM algorithm (initialization method?) and SSID (number of lags used in the Hankel matrix?) are not given.   Perhaps Line 174 'the parameter choices that give the best asymptotic theoretical guarantees are given in the appendix' could be a bit more specific (the appendices are quite large). Also, Unless I missed it, in Sec 5 k is not specified, nor is it clear why W = 100 is chosen.    Originality ----------- The paper builds upon the previous work of [HSZ17] which considers the same one-step ahead prediction problem for LDS. The novelty is in extending this approach to a more general setting; specifically, handling the case of linear systems with asymmetric state transition matrices. In my view, this represents a sufficiently novel/original contribution.   Significance  ------------ The problem of time-series prediction is highly relevant to a number of fields and application areas, and the paper does a good job of motivating this in Section 1.    Minor corrections & comments ----------------------------  Full stop after the equation between lines 32-33.  Line 39, 'assumed to be [proportional to] a small constant'?  It's a little strange to put Algorithm 1 and Theorem 1 before Definition 2, given that Definition 2 is necessary to understand the algorithm (and to some extent the theorem).   Line 185 'Consider a noiseless LDS'.