Explicit universal sampling sets in finite vector spaces

Abstract

In this paper we construct explicit sampling sets and present reconstruction algorithms for Fourier signals on finite vector spaces $G$, with $|G|=p^r$ for a suitable prime $p$. The two sets have sizes of order $O(p{t}^2{r}^2)$ and $O(p{t}^2{r}^3\log (p))$ respectively, where $t$ is the number of large coefficients in the Fourier transform. The algorithms approximate the function up to a small constant of the best possible approximation with $t$ non-zero Fourier coefficients. The fastest of the algorithms has complexity $O(p^2{t}^2{r}^3\log (p))$.