Recently, for some unrelated reasons, I discovered that it is actually very easy to generate a Gaussian matrix that **does not** respect the *restricted isometry property* (RIP) [1]. I recall that such a matrix is RIP if there exists a (restricted isometry) constant such that, for any -sparse vector ,

.

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

Take a -sparse vector in and generate randomly two Gaussian matrices and in with i.i.d. entries drawn from . From the vectors and , you can form two new vectors and such that and .

Then, it is easy to show that matrix

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

This can be seen more clearly in the case where . Then the first column of is and the rest of the matrix is independent of and . Conditionally to the value of these two diagonal matrices, this part of is therefore Gaussian with each entry () of variance . Then, the condition can be removed by expectation rule to lead to the cdf of , and then to the pdf by differentiation, recovering the Gaussian distribution in the orthogonal space of .

However, cannot be RIP. First, obviously since which shows, by construction, that at least one -sparse vector (that is, ) is in the null space of . Second, by taking vectors in , we clearly have for any . Therefore, we can alway take the norm of sufficiently small so that is far from .

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

All this is also very close from the “Cancel-then-Recover” strategy developed in [3]. 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*:

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

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

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

### Like this:

Like Loading...

*Related*