7.2 Proof of the rip for sub-gaussian matrices  (Page 4/2)

We now show how to exploit the concentration of measure properties of sub-Gaussian distributions to provide a simple proof that sub-Gaussian matrices satisfy the restricted isometry property (RIP). Specifically, we wish to show that by constructing an $M\times N$ matrix $\Phi$ at random with $M$ sufficiently large, then with high probability there exists a ${\delta }_K\in (0,1)$ such that

holds for all $x\in {\Sigma }_K$ (where ${\Sigma }_K$ denotes the set of all signals $x$ with at most $K$ nonzeros).

We begin by observing that if all we require is that ${\delta }_{2K}>0$ , then we may set $M=2K$ and draw a $\Phi$ according to a Gaussian distribution, or indeed any continuous univariate distribution. In this case, with probability 1, any subset of $2K$ columns will be linearly independent, and hence all subsets of $2K$ columns will be bounded below by $1-{\delta }_{2K}$ where ${\delta }_{2K}>0$ . However, suppose we wish to know the constant ${\delta }_{2K}$ . In order to find the value of the constant we must consider all possible $\left(\genfrac{}{}{0pt}{}{N}{K}\right)$ $K$ -dimensional subspaces of ${\mathbb{R}}^N$ . From a computational perspective, this is impossible for any realistic values of $N$ and $K$ . Moreover, in light of the lower bounds we described earlier in this course, the actual value of ${\delta }_{2K}$ in this case is likely to be very close to 1. Thus, we focus instead on the problem of achieving the RIP of order $2K$ for a specified constant ${\delta }_{2K}$ .

To ensure that the matrix will satisfy the RIP, we will impose two conditions on the random distribution. First, we require that the distribution is sub-Gaussian. In order to simplify our argument, we will use the simpler results stated in Corollary 2 from "Concentration of measure for sub-Gaussian random variables" , which we briefly recall.

Suppose that $\Phi$ is an $M\times N$ matrix whose entries ${\phi }_{ij}$ are i.i.d. with ${\phi }_{ij}\sim \mathrm{SSub}(1/M)$ . Let $Y=\Phi x$ for $x\in {\mathbb{R}}^N$ . Then for any $ϵ>0$ , and any $x\in {\mathbb{R}}^N$ ,

and

with ${\kappa }^{*}=2/(1-log\left(2\right))\approx 6.52$ .

By exploiting this theorem, we assume that the distribution used to construct $\Phi$ is strictly sub-Gaussian. This is done simply to yield more concrete constants. The argument could easily be modified to establish a similar result for general sub-Gaussian distributions by instead using Theorem 2 from "Concentration of measure for sub-Gaussian random variables" .

Our second condition is that we require that the distribution yield a matrix that is approximately norm-preserving, which will require that

and hence the variance is $1/M$ .

We shall now show how the concentration of measure inequality in [link] can be used together with covering arguments to prove the RIP for sub-Gaussian random matrices. Our general approach will be to construct nets of points in each $K$ -dimensional subspace, apply [link] to all of these points through a union bound, and then extend the result from our finite set of points to all possible $K$ -dimensional signals. Thus, in order to prove the result, we will require the following upper bound on the number of points required to construct the nets of points. (For an overview of results similar to [link] and of various related concentration of measure results, we refer the reader to the excellent introduction of  [link] .)