Restricted Isometry Property for Discrete Fourier Transform Matrix

Question

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$.

Answer 1

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.