Explicit universal sampling sets in finite vector spaces

In this paper we construct explicit sampling sets and present reconstruction algorithms for Fourier signals on finite vector spaces G, with |G|=pr for a suitable prime p. The two sampling sets have sizes of order O(pt2r2) and O(pt2r3log⁡(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(p2t2r3log⁡(p)).