Near-Optimal and Tractable Estimation under Shift-Invariance

How hard is it to estimate a discrete-time signal (x1, ..., xn) ∈ mathbbCn 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 mathbbC with total degree s, including harmonic oscillations with s arbitrary frequencies. Geometrically, this class corresponds to the projection onto mathbbCn of the union of all shift-invariant subspaces of smashmathbbC^mathbbZ of dimension s. We show that the statistical complexity of this class, as measured by the squared minimax radius of the (1-δ)-confidence ℓ2-ball, is nearly the same as for the class of s-sparse signals, namely smashOleft(slog(en) + log(δ-1)right) · log2(es) · 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 smashmathbbC^mathbbZ as a reproducing filter with the smallest possible spectrum in all ℓp-norms, p ∈ [1,∞], at once.