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 | = p r for a suitable prime p . The two sampling 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 ) ) . [ABSTRACT FROM AUTHOR]