## A useless non-RIP Gaussian matrix

Recently, for some unrelated reasons, I discovered that it is actually very easy to generate a Gaussian matrix $\Phi$ that does not respect the restricted isometry property (RIP) . I recall that such a matrix is RIP if  there exists a (restricted isometry) constant $0<\delta<1$ such that, for any $K$-sparse vector $w\in \mathbb R^N$, $(1-\delta)\|w\|^2\leq \|\Phi w\|^2 \leq (1+\delta)\|w\|^2$.

This is maybe obvious and it probably serves to nothing but here is anyway the argument.

Take a $K$-sparse vector $x$ in $\mathbb R$ and generate randomly two Gaussian matrices $U$ and $V$ in $\mathbb R^{M\times N}$ with i.i.d. entries drawn from $\mathcal N(0,1)$. From the vectors $a=Ux$ and $b=Vx$, you can form two new vectors $c$ and $s$ such that $c_i = a_i / \sqrt{a_i^2 + b_i^2}$ and $s_i = b_i / \sqrt{a_i^2 + b_i^2}$.

Then, it is easy to show that matrix $\Phi = {\rm diag}(c) V - {\rm diag}(s)U\qquad(1)$

is actually Gaussian except in the direction of $x$ (where it vanishes to 0).

This can be seen more clearly in the case where $x = (1,0,\,\cdots,0)^T$. Then the first column of $\Phi$ is $0$ and the rest of the matrix is independent of ${\rm diag}(c)$ and ${\rm diag}(s)$. Conditionally to the value of these two diagonal matrices, this part of $\Phi$ is therefore Gaussian with each $ij$ entry ( $j\geq 2$) of variance $c_i^2 + s_i^2 = 1$. Then, the condition can be removed by expectation rule to lead to the cdf of $\Phi$, and then to the pdf by differentiation, recovering the Gaussian distribution in the orthogonal space of $x$.

However, $\Phi$ cannot be RIP. First, obviously since $\Phi x = 0$ which shows, by construction, that at least one $K$-sparse vector (that is, $x$) is in the null space of $\Phi$. Second, by taking vectors in $x + \Sigma_K = x + \{u: \|u\|_0 \leq K \}$, we clearly have $\|\Phi (x + u)\| = \|\Phi u\|$ for any $u \in \Sigma_K$. Therefore, we can alway take the norm of $u$ sufficiently small so that $\|\Phi (x + u)\|$ is far from $\|x + u\|$.

Of course, for the space of $K$-sparse vectors orthogonal to $x$, the matrix is still RIP. It is easy to follow the argument above for proving that $\Phi$ is Gaussian in this space and then to use classical RIP proof .

All this is also very close from the “Cancel-then-Recover” strategy developed in . The only purpose of this post to prove the (useless) result that combining two Gaussian matrices as in (1) leads to a non-RIP matrix.

References:

 Candes, Emmanuel J., and Terence Tao. “Decoding by linear programming.” Information Theory, IEEE Transactions on 51.12 (2005): 4203-4215.

 Baraniuk, Richard, et al. “A simple proof of the restricted isometry property for random matrices.” Constructive Approximation 28.3 (2008): 253-263.

 Davenport, Mark A., et al. “Signal processing with compressive measurements.” Selected Topics in Signal Processing, IEEE Journal of 4.2 (2010): 445-460.

Advertisements
This entry was posted in Compressed Sensing, General. Bookmark the permalink.