3.4 Matrices that satisfy the rip

We now turn to the question of how to construct matrices that satisfy the restricted isometry property (RIP). It is possible to deterministically construct matrices of size $M\times N$ that satisfy the RIP of order $K$ , but such constructions also require $M$ to be relatively large  [link] , [link] . For example, the construction in  [link] requires $M=O(K^{2}logN)$ while the construction in  [link] requires $M=O\left(K{N}^{\alpha }\right)$ for some constant $\alpha$ . In many real-world settings, these results would lead to an unacceptably large requirement on $M$ .

Fortunately, these limitations can be overcome by randomizing the matrix construction. We will construct our random matrices as follows: given $M$ and $N$ , generate random matrices $\Phi$ by choosing the entries ${\phi }_{ij}$ as independent realizations from some probability distribution. 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. 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$ . Thus, we focus on the problem of achieving the RIP of order $2K$ for a specified constant ${\delta }_{2K}$ . Our treatment is based on the simple approach first described in  [link] and later generalized to a larger class of random matrices in  [link] .

To ensure that the matrix will satisfy the RIP, we will impose two conditions on the random distribution. First, we require that the distribution will yield a matrix that is norm-preserving, which will require that

and hence the variance of the distribution is $1/M$ . Second, we require that the distribution is a sub-Gaussian distribution , meaning that there exists a constant $c>0$ such that

for all $t\in \mathbb{R}$ . This says that the moment-generating function of our distribution is dominated by that of a Gaussian distribution, which is also equivalent to requiring that tails of our distribution decay at least as fast as the tails of a Gaussian distribution. Examples of sub-Gaussian distributions include the Gaussian distribution, the Bernoulli distribution taking values $\pm 1/\sqrt{M}$ , and more generally any distribution with bounded support. See "Sub-Gaussian random variables" for more details.

For the moment, we will actually assume a bit more than sub-Gaussianity. Specifically, we will assume that the entries of $\Phi$ are strictly sub-Gaussian, which means that they satisfy [link] with $c^2=\mathbb{E}\left({\phi }_{ij}^2\right)=\frac{1}{M}$ . Similar results to the following would hold for general sub-Gaussian distributions, but to simplify the constants we restrict our present attention to the strictly sub-Gaussian $\Phi$ . In this case we have the following useful result, which is proven in "Concentration of measure for sub-Gaussian random variables" .

Suppose that $\Phi$ is an $M\times N$ matrix whose entries ${\phi }_{ij}$ are i.i.d. with ${\phi }_{ij}$ drawn according to a strictly sub-Gaussian distribution with $c^2=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$ .

This tells us that the norm of a sub-Gaussian random vector strongly concentrates about its mean. Using this result, in "Proof of the RIP for sub-Gaussian matrices" we provide a simple proof based on that in  [link] that sub-Gaussian matrices satisfy the RIP.

Fix $\delta \in (0,1)$ . Let $\Phi$ be an $M\times N$ random matrix whose entries ${\phi }_{ij}$ are i.i.d. with ${\phi }_{ij}$ drawn according to a strictly sub-Gaussian distribution with $c^2=1/M$ . If

then $\Phi$ satisfies the RIP of order $K$ with the prescribed $\delta$ with probability exceeding $1-2e^{-{\kappa }_{2}M}$ , where ${\kappa }_1$ is arbitrary and ${\kappa }_2={\delta }^2/2{\kappa }^{*}-log(42e/\delta )/{\kappa }_1$ .

Note that in light of the measurement bounds in "The restricted isometry property" we see that [link] achieves the optimal number of measurements (up to a constant).

Using random matrices to construct $\Phi$ has a number of additional benefits. To illustrate these, we will focus on the RIP. First, one can show that for random constructions the measurements are democratic , meaning that it is possible to recover a signal using any sufficiently large subset of the measurements  [link] , [link] . Thus, by using random $\Phi$ one can be robust to the loss or corruption of a small fraction of the measurements. Second, and perhaps more significantly, in practice we are often more interested in the setting where $x$ is sparse with respect to some basis $\Psi$ . In this case what we actually require is that the product $\Phi \Psi$ satisfies the RIP. If we were to use a deterministic construction then we would need to explicitly take $\Psi$ into account in our construction of $\Phi$ , but when $\Phi$ is chosen randomly we can avoid this consideration. For example, if $\Phi$ is chosen according to a Gaussian distribution and $\Psi$ is an orthonormal basis then one can easily show that $\Phi \Psi$ will also have a Gaussian distribution, and so provided that $M$ is sufficiently high $\Phi \Psi$ will satisfy the RIP with high probability, just as before. Although less obvious, similar results hold for sub-Gaussian distributions as well  [link] . This property, sometimes referred to as universality , constitutes a significant advantage of using random matrices to construct $\Phi$ .

Finally, we note that since the fully random matrix approach is sometimes impractical to build in hardware, several hardware architectures have been implemented and/or proposed that enable random measurements to be acquired in practical settings. Examples include the random demodulator   [link] , random filtering  [link] , the modulated wideband converter  [link] , random convolution  [link] , [link] , and the compressive multiplexer  [link] . These architectures typically use a reduced amount of randomness and are modeled via matrices $\Phi$ that have significantly more structure than a fully random matrix. Perhaps somewhat surprisingly, while it is typically not quite as easy as in the fully random case, one can prove that many of these constructions also satisfy the RIP.