Near-Optimal and Tractable Estimation under Shift-Invariance

Abstract

How hard is it to estimate a discrete-time signal (x_1, ..., x_n) 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 C with total degree s, including harmonic oscillations with s arbitrary frequencies. Geometrically, this class corresponds to the projection onto C^n of the union of all shift-invariant subspaces of C^Z 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 O(s(en) + (^-1)) ^2(es) (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 rest upon an approximation-theoretic one: we show that finite-dimensional shift-invariant subspaces admit compactly supported reproducing kernels whose Fourier spectra have nearly the smallest possible _p-norms, for all p [1,+] at once.

Tasks

Reproductions