A variant of compressed sensing

This paper is motivated by some recent advances on what is now called “compressed sensing”. Let us begin with a theorem by Terence Tao. Let p be a prime number and Fp be the finite field with p elements. We denote by #E the cardinality of E ⊂ Fp. The Fourier transform of a complex valued function f defined on Fp is denoted by f . Let Mq be the collection of all f : Fp 7→ C such that the cardinality of the support of f does not exceed q. Then Terence Tao proved that for q < p/2 and for any set Ω of frequencies such that #Ω ≥ 2q, the mapping Φ : Mq 7→ l(Ω) defined by f 7→ 1Ωf is injective. Here and in what follows, 1E will denote the indicator function of the set E. This theorem is wrong if Fp is replaced by Z/NZ and if N is not a prime.