Georgia Institute of Technology College of Sciences

How hard is it to estimate a sequence of length N, satisfying some *unknown* linear recurrence relation of order S and observed in additive Gaussian noise? The class of all such sequences is extremely rich: it is formed by arbitrary (complex) exponential polynomials with total degree S. This includes the case of stationary sequences, a.k.a. harmonic oscillations, a.k.a. sequences with discrete​ Fourier spectra supported on S *arbitrary* frequencies. Strikingly, it turns out that one can estimate such sequences with almost the same statistical error as if the recurrence relation was known (and a simple least-squares estimator could be used). In particular, stationary sequences can be estimated with mean-squared error of order O(S/N) up to a polylogarithmic factor, without any assumption of spectral separation—despite what one might learn in a high-dimensional statistics class. Moreover, these methods are computationally tractable. 

In this talk, I will highlight some mathematics underlying this result, putting emphasis on analytical, rather than statistical, side of things. In particular, I will show how to invert a polynomial while ensuring that the result is a polynomial—rather than a reciprocal of a polynomial—and what this has to do with reproducing kernels. Then, I will pitch some accessible open problems in this area.