DMS Statistics and Data Science Seminar

Speaker: Dmitrii Ostrovskii (Georgia Tech — Math and ISyE)

Title: Near-Optimal and Tractable Estimation under Shift-Invariance

Abstract: How hard is it to estimate a discrete-time signal \((x_1, \dots, 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}^{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(slog(en)+log(δ−1))⋅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 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. 

Host: Haotian Xu

SDS seminar’s website: https://auburn.edu/cosam/datascienceseminar/index.htm