Restricted Isometry Property for Discrete Fourier Transform Matrix 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$.
 A: This is a solved problem, see for instance
http://www.mathc.rwth-aachen.de/~rauhut/files/LinzRauhut.pdf .
See for instance theorem 4.3 for non uniform recovery results. 
For more general estimations of RIP, see Theorem 8.1:
Let $A \in \mathbb{C}^{n \times d}$ be the sampling matrix from a Bounded Orthonormal System (see definition 4.4 from the paper) that satisfies the boundedness condition
\begin{equation}
\|\psi_j\|_\infty \leq K, \quad \text{ for all } j \in \{1,\cdots, N\}
\end{equation}
for some constant $K \geq 1$. Assume that the random sampling points $t_1, \cdots, t_m$ are chosen independently at random according to the orthogonalization measure $\nu$. Suppose, for some $\varepsilon \in (0,1)$ and $\delta \in (0,1/2]$, that
\begin{equation}
\frac{n}{\log(10n)} \geq D K^2 \delta^{-2}s \log^2(100s)\log(4N)\log(7\varepsilon^{-1})
\end{equation}
where the constant $D \leq 243 150$, then with probability at least $1 - \varepsilon$ the restricted isometry constant of the renormalized matrix $\frac{1}{\sqrt{n}}A$ satisfies $\delta_s \leq \delta$. 
In particular noting that $N \leq m$ and $N \leq m$, we have the condition (omitting some constants) 
\begin{equation}
m \geq C s \log^4(N).
\end{equation}
Note that the estimates described here are not the best available, and recently two papers have shown much stronger results:
1) Haviv, Regev, ''The resitricted isometry property of subsampled Fourier matrices'', the condition is there $n \geq s \log^2(s) \log(N)$. (I can't remember the dependence on the probability $\varepsilon$ nor on the $\delta$)
2) Bourgain, ''An improved estimate in the restricted isometry problem''. There I think the dependence on the $\delta$ is $\delta^{-6}$, which is not great. 
Hope this helps. 
