Near-Optimal and Tractable Estimation under Shift-Invariance

Abstract

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 ${\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-\hat{I}´)$-confidence ${\ell }_2$-ball, is nearly the same as for the class of $s$-sparse signals, namely $O\left(s\log (en)+\log (\hat{I}{´}^{-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 ${\mathbb{C}}^{\mathbb{Z}}$ as a reproducing filter with the smallest possible spectrum in all ${\ell }_p$-norms, $p\in [1,\infty ]$, at once.

28 pages. In the previous version (v2), our construction of the reproducing filter was erroneous. It is now replaced with an alternative construction using the Christoffel function. The only change from v3 is a typesetting correction in the abstract