Return to Answer

The restricted isometry property, or RIP (formerly known as the uniform uncertainty principle, or UUP, as per your suspicion that uncertainty principles should be relevant) for random Fourier measurements prohibits $\varepsilon$ from being smaller than about $\log^{-4} |G|$; this property was first proven (for $G$ a cyclic group, and with exponent 6 instead of 4) by Candes and myself, and then (for arbitrary abelian $G$, and with exponent 4) by Rudelson and Vershynin. If one takes $S$ to be a random subset of $G$ of density $1/2$, then for any sufficiently sparse $f$ (of sparsity less than $c |G|/\log^4 |G|$ for some small $c$), the Fourier energy of $\hat f$ will be split more or less equally between $S$ and its complement thanks to the RIP, and so the situation described in your post will not occur.

If one takes gaussian measurements instead of Fourier ones, one only needs to oversample by a constant factor (see Lemma 4.1 of the previously mentioned paper of Candes and myself and the remark at the end of the proof), so it is conceivable that one can obtain an analogous result in the Fourier setting and give a negative answer to your question for some sufficiently small $\varepsilon$ independent of the size of the group. But unfortunately this is probably outside of reach of the technology described in the above papers. (But there has been a number of advances in that area since then, which I have not followed as closely. For instance, there has been a slight improvement to the Rudelson-Vershynin bound obtained recently by Cheraghchi, Guruswami, and Velingker, although for the problem at hand, it does not appear to lower the exponent $4$ further.)

The restricted isometry property, or RIP (formerly known as the uniform uncertainty principle, or UUP, as per your suspicion that uncertainty principles should be relevant) for random Fourier measurements prohibits $\varepsilon$ from being smaller than about $\log^{-4} |G|$; this property was first proven (for $G$ a cyclic group, and with exponent 6 instead of 4) by Candes and myself, and then (for arbitrary abelian $G$, and with exponent 4) by Rudelson and Vershynin. If one takes $S$ to be a random subset of $G$ of density $1/2$, then for any sufficiently sparse $f$ (of sparsity less than $c |G|/\log^4 |G|$ for some small $c$), the Fourier energy of $\hat f$ will be split more or less equally between $S$ and its complement thanks to the RIP, and so the situation described in your post will not occur.

If one takes gaussian measurements instead of Fourier ones, one only needs to oversample by a constant factor (see Lemma 4.1 of the previously mentioned paper of Candes and myself and the remark at the end of the proof), so it is conceivable that one can obtain an analogous result in the Fourier setting and give a negative answer to your question for some sufficiently small $\varepsilon$ independent of the size of the group. But unfortunately this is probably outside of reach of the technology described in the above papers. (But there has been a number of advances in that area since then, which I have not followed as closely. For instance, there has been a slight improvement to the Rudelson-Vershynin bound obtained recently by Cheraghchi, Guruswami, and Velingker, although for the problem at hand, it does not appear to lower the exponent $4$ further.)

ADDED LATER: Actually, on thinking about it a bit more, the RIP is probably too strong a property for this purpose (it creates a set S that becomes a counterexample for all sparse T, whereas for your problem it would suffice to find a different counterexample S for each sparse T). The situation is then a bit closer to my original paper with Candes and Romberg which only needed an oversampling of order $\log |G|$ or so, though we didn't phrase our analysis in an easily portable form and one would have to look through the argument in detail to check if the bounds there indeed give a negative answer to your question for $\varepsilon < c/\log |G|$. I still don't know how to get rid of the final logarithm, though.

The restricted isometry property, or RIP (formerly known as the uniform uncertainty principle, or UUP, as per your suspicion that uncertainty principles should be relevant) for random Fourier measurements prohibits $\varepsilon$ from being smaller than about $\log^{-4} |G|$; this property was first proven (for $G$ a cyclic group, and with exponent 6 instead of 4) by Candes and myself, and then (for arbitrary abelian $G$, and with exponent 4) by Rudelson and Vershynin. If one takes $S$ to be a random subset of $G$ of density $1/2$, then for any sufficiently sparse $f$ (of sparsity less than $c |G|/\log^4 |G|$ for some small $c$), the Fourier energy of $\hat f$ will be split more or less equally between $S$ and its complement thanks to the RIP, and so the situation described in your post will not occur.

If one takes gaussian measurements instead of Fourier ones, one only needs to oversample by a constant factor (see Lemma 4.1 of the previously mentioned paper of Candes and myself and the remark at the end of the proof), so it is conceivable that one can give a negative answer to your question for some sufficiently small $\varepsilon$ independent of the size of the group. But unfortunately this is probably outside of reach of the technology described in the above papers. (But there has been a number of advances in that area since then, which I have not followed as closely. For instance, there has been a slight improvement to the Rudelson-Vershynin bound obtained recently by Cheraghchi, Guruswami, and Velingker, although for the problem at hand, it does not appear to lower the exponent $4$ further.)

The restricted isometry property, or RIP (formerly known as the uniform uncertainty principle, or UUP, as per your suspicion that uncertainty principles should be relevant) for random Fourier measurements prohibits $\varepsilon$ from being smaller than about $\log^{-4} |G|$; this property was first proven (for $G$ a cyclic group, and with exponent 6 instead of 4) by Candes and myself, and then (for arbitrary abelian $G$, and with exponent 4) by Rudelson and Vershynin. If one takes $S$ to be a random subset of $G$ of density $1/2$, then for any sufficiently sparse $f$ (of sparsity less than $c |G|/\log^4 |G|$ for some small $c$), the Fourier energy of $\hat f$ will be split more or less equally between $S$ and its complement thanks to the RIP, and so the situation described in your post will not occur.

If one takes gaussian measurements instead of Fourier ones, one only needs to oversample by a constant factor (see Lemma 4.1 of the previously mentioned paper of Candes and myself and the remark at the end of the proof), so it is conceivable that one can obtain an analogous result in the Fourier setting and give a negative answer to your question for some sufficiently small $\varepsilon$ independent of the size of the group. But unfortunately this is probably outside of reach of the technology described in the above papers. (But there has been a number of advances in that area since then, which I have not followed as closely. For instance, there has been a slight improvement to the Rudelson-Vershynin bound obtained recently by Cheraghchi, Guruswami, and Velingker, although for the problem at hand, it does not appear to lower the exponent $4$ further.)

The restricted isometry property (formerly known as the uniform uncertainty principle) for random Fourier measurements prohibits $\varepsilon$ from being smaller than about $\log^{-6} N$ in the case that $G = {\bf Z}/N{\bf Z}$ is a cyclic group; see Lemma 4.3 and Definition 1.2 of this paper of Candes and myself. Indeed, if one takes $S$ to be a random subset of $G$ of density $1/2$, then for any sufficiently sparse $f$ (less than $c N/\log^6 N$ for some small $c$), the Fourier energy of $\hat f$ will be split more or less equally between $S$ and its complement thanks to the RIP. It is likely that the methods of proof also work for other abelian groups than the cyclic groups, but we did not pursue this explicitly in that paper.

The oversampling factor of $\log^6 N$ is probably not best possible; the work of Rudelson and Vershynin, in particular, suggests an improvement to $\log^4 N$ is possible. If one takes gaussian measurements instead of Fourier ones, one only needs to oversample by a constant factor (see Lemma 4.1 of the previously mentioned paper of Candes and myself and the remark at the end of the proof), so it is conceivable that one can give a negative answer to your question for some sufficiently small $\varepsilon$ independent of the size of the group. But unfortunately this is probably outside of reach of the technology described in the above papers. (But there has been a number of advances in that area since then, which I have not followed as closely.)

The restricted isometry property, or RIP (formerly known as the uniform uncertainty principle, or UUP, as per your suspicion that uncertainty principles should be relevant) for random Fourier measurements prohibits $\varepsilon$ from being smaller than about $\log^{-4} |G|$; this property was first proven (for $G$ a cyclic group, and with exponent 6 instead of 4) by Candes and myself, and then (for arbitrary abelian $G$, and with exponent 4) by Rudelson and Vershynin. If one takes $S$ to be a random subset of $G$ of density $1/2$, then for any sufficiently sparse $f$ (of sparsity less than $c |G|/\log^4 |G|$ for some small $c$), the Fourier energy of $\hat f$ will be split more or less equally between $S$ and its complement thanks to the RIP, and so the situation described in your post will not occur.

If one takes gaussian measurements instead of Fourier ones, one only needs to oversample by a constant factor (see Lemma 4.1 of the previously mentioned paper of Candes and myself and the remark at the end of the proof), so it is conceivable that one can give a negative answer to your question for some sufficiently small $\varepsilon$ independent of the size of the group. But unfortunately this is probably outside of reach of the technology described in the above papers. (But there has been a number of advances in that area since then, which I have not followed as closely. For instance, there has been a slight improvement to the Rudelson-Vershynin bound obtained recently by Cheraghchi, Guruswami, and Velingker, although for the problem at hand, it does not appear to lower the exponent $4$ further.)