Explicit Constructions of RIP Matrices And Related Problems by Bourgain et. al.

In the paper Explicit Constructions of RIP Matrices And Related Problems, the authors (among other things) explicitly construct a matrix that breaks the square-root barrier for constructions based on coherence. This blog tries to give a very coarse-level view of this interesting paper.

Fix a large even number $m$ and choose a sufficiently large $n$ ($n$ is going to be the row-size of the final constructed matrix). How large $n$ should be is given in the following paragrahs. From Bertrand's postulate a prime $p$ can be chosen such that $p \geq \frac{n}{2}$. Let $A, B \subset \mathbb{F}_p$ ($\mathbb{F}_p$ is the field of residues modulo $p$) and define the columns of the matrix as $u_{a,b} = \frac{1}{\sqrt{p}}e^{\frac{2\pi i (ax^2+bx)}{p}}$ where $x \in \mathbb{F}_p, a \in A, b \in B$. Denote this matrix by $\Phi_p$ (the size of this matrix is $p \times |A||B|$).

The paper describes which subsets $A,B$ of $\mathbb{F}_p$ to choose so that the resulting matrix has good RIP. First $A$ is defined in the following manner. Let $\alpha = \frac{1}{8m^2}, L=\lfloor{p^\alpha}\rfloor, U=L^{4m-1}$. Then $A = \{x^2 + Ux : 1 \leq x \leq L\}$. Note that all the operations here are w.r.t $\mathbb{F}_p$.

Now, definitely $|A|\leq L$. If $x^2 + Ux = y^2 + Uy$ then $(x-y)(x+y+U)=0$. Therefore, either $x-y=0\mod(p)$ or $x+y+U=0\mod(p)$. $x+y+U = 0\mod(p)$ is impossible because $x+y+U$ is much smaller than $p$. Therefore $x=y$ and hence $|A| = L$.

Let $\beta = \frac{\alpha}{2}, r= \lfloor \beta \log_2 p \rfloor, M = 2^{(1/\beta)-1}$. Then, $B$ is defined as $B = \{\sum_{j=1}^r x_j (2M)^{j-1} : x_1,\cdots, x_r \in \{0,\cdots,M-1\}\}$. Now, $M^r = 2^{r(\frac{1}{\beta}-1)} \asymp 2^{(\beta\log_2 p)(\frac{1}{\beta}-1)} \asymp p^{1-\beta}$. More precisely, $2^{(1-\frac{1}{\beta})} \leq \frac{M^r}{p^{1-\beta}} \leq 1$ And, any element in $B$ is atmost $\sum_{j=1}^r (M-1) (2M)^{j-1} \leq (M-1)\frac{(2M)^r - 1}{(2M)-1} \leq \frac{(2M)^r}{2} \leq \frac{p}{2}$. This last inequality can be taken as $<$ as $p$ is prime.

Again, we want to compute $|B|$. Clearly, $|B| \leq M^r$. Now, suppose $\sum_{j=1}^r x_j (2M)^{j-1} = \sum_{j=1}^r y_j (2M)^{j-1}$. As both these terms are less than $p/2$, the equality should hold in $\mathbb{R}$. Then, $\sum_{j=1}^r z_j (2M)^{j-1} = 0$ where $-(M-1) \leq z_j \leq (M-1)$ for all $1 \leq j \leq r$. We show by induction that this can be true only if $z_j=0$ for all $1 \leq j \leq r$. For $r=1$, the claim is clearly true. For $r=2$, we have $z_1 + z_2(2M) = 0$. If $z_2 \neq 0$, then $z_1=-z_2(2M)$ and hence $z_1 \notin \{-(M-1),\cdots,M-1\}$. Similarly, if $z_2+ z_3(2M)\neq 0$, then $z_1 = -(2M)(z_2+z_3(2M)) \notin \{-(M-1),\cdots,M-1\}$ and so on. Therefore, $|B| = M^r$ and so $|A||B| \asymp p^{1+\beta}$. For large enough $p$ (and hence $n$), we can take the column size of the matrix $\Phi_p$ to be $p^{1+\frac{\beta}{2}}$. (Basically, $p^{1+\frac{\beta}{2}} < 2^{(1-\frac{1}{\beta})} p^{1+\beta}$ for large enough $p$). By similar argument, we can have a matrix $\Phi_p$ of size $n^{1+\frac{\beta}{2}}$ (as $n^{1+\frac{\beta}{2}} \leq 2^{1+\frac{\beta}{2}} p^{1+\frac{\beta}{2}}\leq 2^{(1-\frac{1}{\beta})} p^{1+\beta}$ for large enough $p$).

Therefore, for $n \leq N \leq n^{1+\frac{\beta}{2}}$ we have matrix of size $p \times N$. For general size $n$, just pad the matrix with zero rows, this matrix is denoted as $\Phi$. Now, it remains to show (which is the majority of paper) that the matrix has good RIP. For this, the authors introduce a new concept called the Flat-RIP which is easier for analysis and then provide a lemma that shows equivalence between Flat-RIP and RIP. The definition of Flat-RIP can be found the paper.

If $k\geq 2^{10}$ and $\mu(D) \leq \frac{1}{k}$ (where $\mu$ is the mutual coherence) and $D$ satisfies Flat-RIP with $(k,\delta)$, then $D$ satisfies RIP with $(2sk,44s\sqrt{\delta}\log k)$. The main lemma in the paper (Lemma 2) proves that $\Phi$ constructed above indeed satisfies the Flat-RIP with $(\sqrt{p},p^{-\epsilon_1})$ where $\epsilon_1 > 0$ (for large enough $m$) is a given constant. Choose, $s=\lfloor p^{\epsilon_1/4}\rfloor$ and let $\epsilon_0 = \epsilon_1/5$. The matrix $\Phi$ satisfies RIP with order $2sk = 2\lfloor p^{\epsilon_1/4}\rfloor p^{1/2} \geq 2\lfloor (n/2)^{\epsilon_1/4}\rfloor (n/2)^{1/2} \geq 2\lfloor (n/2)^{\epsilon_1/4+1/2}\rfloor \geq \lfloor n^{\epsilon_0+\frac{1}{2}}\rfloor$. Also, $44s\sqrt{\delta}\log k = 44\lfloor p^{\epsilon_1/4}\rfloor\sqrt{p^{-\epsilon_1}}\log\sqrt{p} \leq 44p^{-\frac{\epsilon_1}{4}}\log\sqrt{p} \leq (2p)^{-\epsilon_0} (44*2^{\epsilon_0}p^{-\epsilon_1/20}\log\sqrt{p})$. Now, for large enough $p$, the term in the brackets is less than $1$. Hence, for large enough $n$, we get that $44s\sqrt{\delta}\log k \leq n^{-\epsilon_0}$.