The optimal sampling bound conjecture for random subsets and RIP

Let $n$ and $s$ be positive integers, and let $\Omega\subset\{0,1,\ldots,n-1\}$ be a random subset whose average cardinality is $k$. The subset satisfies the restricted isometry property (RIP) if the associated Fourier measurement system preserves the Euclidean norm of every $s$-sparse signal up to a fixed multiplicative distortion.

Optimal sampling bound conjecture. A random subset $\Omega\subset\{0,1,\ldots,n-1\}$ of average cardinality

$$k=O(s\log n)$$

satisfies RIP with high probability.

This conjecture concerns the optimal order of the number of Fourier measurements needed for uniform recovery of sparse signals. The source contrasts it with the weaker bound proved earlier in the paper and with stronger results of Rudelson, Vershynin, and Rauhut; the conjectured $O(s\log n)$ sampling rate remains the target bound in this discussion.