Near-Optimal and Tractable Estimation under Shift-Invariance

How hard is it to estimate a discrete-time signal (x_{1}, ..., x_{n}) \in \mathbb{C}^n satisfying an unknown linear recurrence relation of order s and observed in i.i.d. complex Gaussian noise? The class of all such signals is parametric but extremely rich: it contains all exponential polynomials over \mathbb{C} with total degree s, including harmonic oscillations with s arbitrary frequencies. Geometrically, this class corresponds to the projection onto \mathbb{C}^{n} of the union of all shift-invariant subspaces of \smash{\mathbb{C}^\mathbb{Z}} of dimension s. We show that the statistical complexity of this class, as measured by the squared minimax radius of the (1-δ)-confidence \ell_2-ball, is nearly the same as for the class of s-sparse signals, namely \smash{O\left(s\log(en) + \log(δ^{-1})\right) \cdot \log^2(es) \cdot \log(en/s).} Moreover, the corresponding near-minimax estimator is tractable, and it can be used to build a test statistic with a near-minimax detection threshold in the associated detection problem. These statistical results rely upon a simple analytic observation: the interpretation of the Fourier coefficients of the Christoffel function of any shift-invariant subspace of \smash{\mathbb{C}^\mathbb{Z}} as a reproducing filter with the smallest possible spectrum in all \ell_p-norms, p \in [1,\infty], at once.