Reconstruction of Fourier Sparse Signals over Elementary Abelian Groups

We consider functions f:G→C on a finite abelian group G that are Fourier sparse, i.e., the linear combination of t≪|G| characters. The challenge is to reconstruct f from a (preferably small) set of samples.For finite vector spaces G and t<|G|, we give an explicit, deterministic construction of a universal sampling set Γ that can be used to reconstruct any linear combination of at most t characters. Γ is obtained as a union of subspaces, and has cardinality O(t2log(|G|)k). We also describe an explicit reconstruction algorithm that exploits the structure of Γ, and discuss robust versions computing t-sparse approximations of arbitrary functions.