3.3 The restricted isometry property

We say that an $n\times N$ matrix $\Phi$ has the restricted isometry property (RIP) for $k$ if for each $T\subseteq \{1,\dots ,N\}$ such that , ${\Phi }_T$ (the matrix formed by choosing the columns of $\Phi$ whose indices are in $T$ ) has the property

where . This useful definition is by Candes and Tao. The idea is that the embedding of a $k$ -dimensional space in $M$ -dimensional space almost preserves norm – like an isometry. Another way of looking at it is to consider the matrix ${\Phi }_T^t{\Phi }_T$ , of size $k\times k$ . This matrix is symmetric, positive definite, and it’s eigen-values are between $1-{\delta }_k$ and $1+{\delta }_k$ .

I prefer the following modified condition (dubbed the MIRP), which is more convenient for mathematical analysis:

We can now state the following theorem.

If $\Phi$ satisfies MRIP for $2k$ then $\exists \Delta$ s.t. $(\Phi ,\Delta )$ is instance optimal for ${\ell }_1^N$ for $K$ .

This shows that whenever we have a matrix $\Phi$ satisfying the MRIP for $2k$ then it will perform well on encoding vectors (at least in the sense of ${\ell }_1^N$ accuracy). The question is how can we construct measurement matrices with this property? We can construct $\Phi$ using Gaussian entries and then normalizing the columns.

$\exists$ constant $c>0$ s.t. if then with high probability $\Phi$ satisfies RIP and MRIP for $k$ .

Given $N$ and $n$ , the range of $k$ in the above results reflects how accurately we can recover data. There is another constant $c^{\prime }$ that serves as a converse bound for Theorem 3. This converse can be derived using Gluskin widths.

The following generic problem is of great interest: Consider the class of matrices $ℳ=\{\Phi M\times N,\mathrm{\Phi }\text{has some prescribed property(eg. Toeplitz, circulant, etc.)}\}$ . What is the largest $k$ for which such a matrix can have the MRIP.