I was wondering if the Restricted Isometry Property holds for Discrete Fourier Transform. In particular, I am interested in whether a subsampled DFT matrix has such property. Let$W \in \mathbb{C}^{d\times d}$ be an DCT matrix whose elements are given by $$ W_{jk} = 1/\sqrt{d} \cdot \exp (2\pi i\cdot jk/ d) .$$ Let $A \in \mathbb{C}^{n \times d}$ be a subsampled matrix whose $n$ rows are sampled from the $d$ rows of $W$ (randomly or deterministically). I was wondering if there is an sampling strategy such that $s$-RIP condition holds for $A$ with $n \ll d$? That is, for any $s$-sparse vector $x \in \mathbb{C}^d$, there exists a constant $\delta_s <1$ such that $$ (1- \delta _s ) \| x\|_2^2 \leq \| A x \|_2^2 \leq (1 + \delta _s ) \| x\|_2^2. $$

This problem is of interest to the theory of compressed sensing, where one observes a corrupted Fourier transform of the sparse signal: $$ y = A x + \epsilon. $$ Given $A$ and $y$, the problem is to find the $s$-sparse vector $x$. Typically, the relationship between $n, d$, and $s$ is $n \asymp s \log d$.