Explicit RIP matrices: an update (Q2681274)

An \(n\times N\) matrix \(\Phi\) is said to satisfy the Restricted Isometry Property (RIP) of order \(k\) with constant \(\delta\) if for all \(k\)-sparse vectors \(\boldsymbol x\) we have \((1-\delta)\Vert \boldsymbol x\Vert_2^2\le\Vert \Phi\boldsymbol x\Vert_2^2\le(1+\delta)\Vert \boldsymbol x\Vert_2^2\). In this paper, by improving the values of \(\epsilon\), depending on two constants in additive combinatorics, the following statement is proved. For \(\epsilon=3.26\cdot 10^{-7}\), there exist \(\epsilon'>0\) and effective numbers \(k_0,c>0\) such that for any positive integers \(k\ge k_0\) and \(k^{2-\epsilon}\le N\le k^{2+\epsilon}\), there is an explicit \(n\times N\) RIP matrix of order \(k\) with \(k\ge c n^{1/2+\epsilon/4}\) and constant \(\delta=k^{-\epsilon'}\).