3.2 The restricted isometry property  (Page 3/3)

Thus, suppose we construct the set $X$ by iteratively choosing points that satisfy [link] . After adding $j$ points to the set, there are at least

points left to pick from. Thus, we can construct a set of size $\left|X\right|$ provided that

Next, observe that

where the inequality follows from the fact that $(n-K+i)/(K/2+i)$ is decreasing as a function of $i$ . Thus, if we set $\left|X\right|={(N/K)}^{K/2}$ then we have

Hence, [link] holds for $\left|X\right|={(N/K)}^{K/2}$ , which establishes the lemma.

Using this lemma, we can establish the following bound on the required number of measurements to satisfy the RIP.

Let $\Phi$ be an $M\times N$ matrix that satisfies the RIP of order $2K$ with constant $\delta \in (0,\frac{1}{2}]$ . Then

where $C=1/2log(\sqrt{24}+1)\approx 0.28$ .

We first note that since $\Phi$ satisfies the RIP, then for the set of points $X$ in [link] we have,

for all $x,z\in X$ , since $x-z\in {\Sigma }_{2K}$ and $\delta \le \frac{1}{2}$ . Similarly, we also have

for all $x\in X$ .

From the lower bound we can say that for any pair of points $x,z\in X$ , if we center balls of radius $\sqrt{K/4}/2=\sqrt{K/16}$ at $\Phi x$ and $\Phi z$ , then these balls will be disjoint. In turn, the upper bound tells us that the entire set of balls is itself contained within a larger ball of radius $\sqrt{3K/2}+\sqrt{K/16}$ . If we let $B^M\left(r\right)=\{x\in {\mathbb{R}}^M:{∥x∥}_2\le r\}$ , this implies that

The theorem follows by applying the bound for $\left|X\right|$ from  [link] .

Note that the restriction to $\delta \le \frac{1}{2}$ is arbitrary and is made merely for convenience — minor modifications to the argument establish bounds for $\delta \le {\delta }_{\max }$ for any ${\delta }_{\max }<1$ . Moreover, although we have made no effort to optimize the constants, it is worth noting that they are already quite reasonable.

Although the proof is somewhat less direct, one can establish a similar result (in the dependence on $N$ and $K$ ) by examining the Gelfand width of the ${\ell }_1$ ball  [link] . However, both this result and [link] fail to capture the precise dependence of $M$ on the desired RIP constant $\delta$ . In order to quantify this dependence, we can exploit recent results concerning the Johnson-Lindenstrauss lemma , which concerns embeddings of finite sets of points in low-dimensional spaces  [link] . Specifically, it is shown in  [link] that if we are given a point cloud with $p$ points and wish to embed these points in ${\mathbb{R}}^M$ such that the squared ${\ell }_2$ distance between any pair of points is preserved up to a factor of $1\pm ϵ$ , then we must have that

where $c_0>0$ is a constant.

The Johnson-Lindenstrauss lemma is closely related to the RIP. We will see in "Matrices that satisfy the RIP" that any procedure that can be used for generating a linear, distance-preserving embedding for a point cloud can also be used to construct a matrix that satisfies the RIP. Moreover, in  [link] it is shown that if a matrix $\Phi$ satisfies the RIP of order $K=c_{1}log\left(p\right)$ with constant $\delta$ , then $\Phi$ can be used to construct a distance-preserving embedding for $p$ points with $ϵ=\delta /4$ . Combining these we obtain

Thus, for small $\delta$ the number of measurements required to ensure that $\Phi$ satisfies the RIP of order $K$ will be proportional to $K/{\delta }^2$ , which may be significantly higher than $Klog(N/K)$ . See  [link] for further details.