3.2 The restricted isometry property  (Page 24/3)

The null space property (NSP) is both necessary and sufficient for establishing guarantees of the form

but these guarantees do not account for noise . When the measurements are contaminated with noise or have been corrupted by some error such as quantization, it will be useful to consider somewhat stronger conditions. In  [link] , Candès and Tao introduced the following isometry condition on matrices $\Phi$ and established its important role in compressive sensing (CS).

A matrix $\Phi$ satisfies the restricted isometry property (RIP) of order $K$ if there exists a ${\delta }_K\in (0,1)$ such that

$$(1-{\delta }_K){∥x∥}_2^2\le {∥\Phi ,x∥}_2^2\le (1+{\delta }_K){∥x∥}_2^2,$$

holds for all $x\in {\Sigma }_K=\left\{x,:,{∥x∥}_0,\le ,K\right\}$ .

If a matrix $\Phi$ satisfies the RIP of order $2K$ , then we can interpret [link] as saying that $\Phi$ approximately preserves the distance between any pair of $K$ -sparse vectors. This will clearly have fundamental implications concerning robustness to noise.

It is important to note that in our definition of the RIP we assume bounds that are symmetric about 1, but this is merely for notational convenience. In practice, one could instead consider arbitrary bounds

where $0<\alpha \le \beta <\infty$ . Given any such bounds, one can always scale $\Phi$ so that it satisfies the symmetric bound about 1 in [link] . Specifically, multiplying $\Phi$ by $\sqrt{2/(\beta +\alpha )}$ will result in an $\tilde{\Phi }$ that satisfies [link] with constant ${\delta }_K=(\beta -\alpha )/(\beta +\alpha )$ . We will not explicitly show this, but one can check that all of the theorems in this course based on the assumption that $\Phi$ satisfies the RIP actually hold as long as there exists some scaling of $\Phi$ that satisfies the RIP. Thus, since we can always scale $\Phi$ to satisfy [link] , we lose nothing by restricting our attention to this simpler bound.

Note also that if $\Phi$ satisfies the RIP of order $K$ with constant ${\delta }_K$ , then for any $K^{\text{'}}<K$ we automatically have that $\Phi$ satisfies the RIP of order $K^{\text{'}}$ with constant ${\delta }_{K^{\text{'}}}\le {\delta }_K$ . Moreover, in  [link] it is shown that if $\Phi$ satisfies the RIP of order $K$ with a sufficiently small constant, then it will also automatically satisfy the RIP of order $\gamma K$ for certain $\gamma$ , albeit with a somewhat worse constant.

(corollary 3.4 of [link] )

Suppose that $\Phi$ satisfies the RIP of order $K$ with constant ${\delta }_K$ . Let $\gamma$ be a positive integer. Then $\Phi$ satisfies the RIP of order $K^{\text{'}}=\gamma ⌊\frac{K}{2}⌋$ with constant ${\delta }_{K^{\text{'}}}<\gamma ·{\delta }_K$ , where $\lfloor ·\rfloor$ denotes the floor operator.

This lemma is trivial for $\gamma =1,2$ , but for $\gamma \ge 3$ (and $K\ge 4$ ) this allows us to extend from RIP of order $K$ to higher orders. Note however, that ${\delta }_K$ must be sufficiently small in order for the resulting bound to be useful.

The rip and stability

We will see later in this course that if a matrix $\Phi$ satisfies the RIP, then this is sufficient for a variety of algorithms to be able to successfully recover a sparse signal from noisy measurements. First, however, we will take a closer look at whether the RIP is actually necessary. It should be clear that the lower bound in the RIP is a necessary condition if we wish to be able to recover all sparse signals $x$ from the measurements $\Phi x$ for the same reasons that the NSP is necessary. We can say even more about the necessity of the RIP by considering the following notion of stability.