18.8. Restricted Isometry Property

This section dwells deep into the implications of restricted isometry property.

Definition 18.31 (Restricted isometry property)

A matrix $\mathrm{\Phi }\in {\mathbb{C}}^{M\times N}$ is said to satisfy the RIP (restricted isometry property) of order $K$ with a constant $\delta \in (0,1)$ if the following holds:

(18.43)$$(1-\delta )\Vert \mathbf{x}{\Vert }_2^2\le \Vert \mathrm{\Phi }\mathbf{x}{\Vert }_2^2\le (1+\delta )\Vert \mathbf{x}{\Vert }_2^2$$

for every $\mathbf{x}\in {\mathrm{\Sigma }}_K$ where

$${\mathrm{\Sigma }}_K=\{\mathbf{x}\in {\mathbb{C}}^N:\Vert \mathbf{x}{\Vert }_0\le K\}$$

is the set of all $K$-sparse vectors in ${\mathbb{C}}^N$.

Definition 18.32 (Restricted isometry constant)

If a matrix $\mathrm{\Phi }\in {\mathbb{C}}^{M\times N}$ satisfies RIP of order $K$ then the smallest value of $\delta$ (denoted as ${\delta }_K$) for which the following holds

(18.44)$$(1-\delta )\Vert \mathbf{x}{\Vert }_2^2\le \Vert \mathrm{\Phi }\mathbf{x}{\Vert }_2^2\le (1+\delta )\Vert \mathbf{x}{\Vert }_2^2\mathrm{\forall }\mathbf{x}\in {\mathrm{\Sigma }}_K$$

is known as the $K$-th restricted isometry constant for $\mathrm{\Phi }$. It is also written in short as $K$-th RIP constant. We write the bounds as in terms of ${\delta }_K$ as

(18.45)$$(1-{\delta }_K)\Vert \mathbf{x}{\Vert }_2^2\le \Vert \mathrm{\Phi }\mathbf{x}{\Vert }_2^2\le (1+{\delta }_K)\Vert \mathbf{x}{\Vert }_2^2\mathrm{\forall }\mathbf{x}\in {\mathrm{\Sigma }}_K.$$

Some remarks are in order.

• $\mathrm{\Phi }$ maps a vector $\mathbf{x}\in {\mathrm{\Sigma }}_K\subseteq {\mathbb{C}}^N$ into ${\mathbb{C}}^M$ as a vector $\mathrm{\Phi }\mathbf{x}$ (usually $M<N$).

• We will call $\mathrm{\Phi }\mathbf{x}\in {\mathbb{C}}^M$ as an embedding of $\mathbf{x}\in {\mathbb{C}}^N$ into ${\mathbb{C}}^M$.

• RIP quantifies the idea as to how much the squared length of a sparse signal changes during this embedding process.

• We can compare matrices satisfying RIP with orthonormal bases.

• An orthonormal basis or the corresponding unitary matrix preserves the length of a vector exactly.

• A matrix $\mathrm{\Phi }$ satisfying RIP of order $K$ is able to preserve the length of $K$ sparse signals approximately (the approximation range given by ${\delta }_K$).

• In this sense we can say that $\mathrm{\Phi }$ implements a restricted almost orthonormal system [19].

• By restricted we mean that orthonormality is limited to $K$-sparse signals.

• By almost we mean that the squared length is not preserved exactly. Rather it is preserved approximately.

• An arbitrary matrix $\mathrm{\Phi }$ need not satisfy RIP of any order at all.

• If $\mathrm{\Phi }$ satisfies RIP of order $K$ then it is easy to see that $\mathrm{\Phi }$ satisfies RIP of any order $L<K$ (since ${\mathrm{\Sigma }}_L\subset {\mathrm{\Sigma }}_K$ whenever $L<K$).

• If $\mathrm{\Phi }$ satisfies RIP of order $K$, then it may or many not satisfy RIP of order $L>K$.

• Restricted isometry constant is a function of sparsity level $K$ of the signal $\mathbf{x}\in {\mathbb{C}}^N$.

Example 18.37 (Restricted isometry constant)

As a running example in this section we will use following matrix

$$\begin{array}{r}\mathrm{\Phi }=\frac{1}{2}\left[\begin{array}{cccccccc}1& -1& 1& 1& 1& -1& 1& 1\\ -1& -1& 1& 1& -1& 1& 1& -1\\ -1& -1& -1& 1& -1& -1& -1& 1\\ -1& 1& 1& 1& 1& -1& -1& -1\end{array}\right]\in {\mathbb{R}}^{4\times 8}.\end{array}$$

Consider

$$\mathbf{x}=\left(\begin{array}{cccccccc}-2& 0& 0& 0& 0& -3& -1& 0\end{array}\right)$$

which is a $3$-sparse vector in ${\mathbb{R}}^8$. We have

$$\mathbf{y}=\mathrm{\Phi }\mathbf{x}=\left(\begin{array}{cccc}0& -1& 3& 3\end{array}\right)$$

Now

$$\Vert \mathbf{x}{\Vert }_2^2=14,\Vert \mathbf{x}{\Vert }_2=3.7417$$

and

$$\Vert \mathbf{y}{\Vert }_2^2=19,\Vert \mathbf{y}{\Vert }_2=4.3589.$$

We note that

$$\frac{\Vert \mathbf{y}{\Vert }_2^2}{\Vert \mathbf{x}{\Vert }_2^2}=1.3571.$$

With this much information, all we can say that ${\delta }_3\ge .3571$ for this matrix $\mathrm{\Phi }$ if $\mathrm{\Phi }$ satisfies RIP of order $3$ since we haven’t examined all possible $3$-sparse vectors.

Still what is comforting to note is that for this particular example, the distance hasn’t increased by a large factor.

For a given $K$-sparse vector $\mathbf{x}$, let $J$ denote the support of $\mathbf{x}$; i.e.,

$$J=\{1\le i\le N|x_i\ne 0\}.$$

In the running example

$$J=\{1,6,7\}.$$

We define ${\mathbf{x}}_J\in {\mathbb{C}}^K$ to be the vector formed by keeping the elements in $\mathbf{x}$ indexed by $J$ and dropping of other elements (the zero elements). Note that the order of elements is preserved. In the running example,

$${\mathbf{x}}_J=\left(\begin{array}{ccc}-2& -3& -1\end{array}\right).$$

Let ${\mathrm{\Phi }}_J$ be the corresponding sub-matrix by choosing columns from $\mathrm{\Phi }$ indexed by the set $J$. Note that the order of columns is preserved. In the running example

$$\begin{array}{r}{\mathrm{\Phi }}_J=\frac{1}{2}\left[\begin{array}{ccc}1& -1& 1\\ -1& 1& 1\\ -1& -1& -1\\ -1& -1& -1\end{array}\right]\in {\mathbb{R}}^{4\times 3}.\end{array}$$

It is easy to see that

$$\mathbf{y}=\mathrm{\Phi }\mathbf{x}={\mathrm{\Phi }}_J{\mathbf{x}}_J.$$

There are $(\genfrac{}{}{0ex}{}{N}{K})$ ways of choosing a $K$-sparse support for $\mathbf{x}$. Thus we have to consider $(\genfrac{}{}{0ex}{}{N}{K})$ corresponding submatrices ${\mathrm{\Phi }}_J$.

For each such submatrix ${\mathrm{\Phi }}_J$, the RIP bounds can be rewritten as

(18.46)$$(1-{\delta }_K)\Vert \mathbf{x}{\Vert }_2^2\le \Vert {\mathrm{\Phi }}_J\mathbf{x}{\Vert }_2^2\le (1+{\delta }_K)\Vert \mathbf{x}{\Vert }_2^2$$

for every $\mathbf{x}\in {\mathbb{C}}^K$. Note that

$$\Vert {\mathrm{\Phi }}_J\mathbf{x}{\Vert }_2^2=({\mathrm{\Phi }}_J\mathbf{x}{)}^H({\mathrm{\Phi }}_J\mathbf{x})={\mathbf{x}}^H{\mathrm{\Phi }}_J^H{\mathrm{\Phi }}_J\mathbf{x}.$$

Theorem 18.44

An $M\times N$ matrix $\mathrm{\Phi }$ cannot satisfy RIP of order $K>M$.

Proof. This comes from the fact that for a wide matrix $\mathrm{rank}\mathrm{\Phi }\le M$.

1. Since every ${\varphi }_j\in {\mathbb{C}}^M$ hence any set of $M+1$ columns in $\mathrm{\Phi }$ is linearly dependent.

2. Thus there exists a nonzero $M+1$ sparse signal $\mathbf{x}\in {\mathbb{C}}^N$ such that $\mathrm{\Phi }\mathbf{x}=\mathbf{0}$ (it belongs to the null space of the chosen $M+1$ columns).

3. RIP (18.43) requires that a nonzero vector be embedded as a nonzero vector.

4. Thus $\mathrm{\Phi }$ cannot satisfy RIP of order $M+1$.

5. The argument can be easily extended for any $K>M$.

Theorem 18.45

If $\mathrm{\Phi }$ satisfies RIP of order $l$ then it satisfies RIP of order $k$ where $k<l$.

Proof. Every $k$ sparse signal is also $l$ sparse signal. Thus if $\mathrm{\Phi }$ satisfies RIP of order $l$ then it automatically satisfies RIP of order $k<l$.

Theorem 18.46

Let $\mathrm{\Phi }$ satisfy RIP of order $k$ and $l$ where $k<l$. Then ${\delta }_k\le {\delta }_l$. In other words, restricted isometry constants are non-decreasing.

Proof. Since every $k$ sparse signal is also $l$ sparse signal, hence for every $\mathbf{x}\in {\mathrm{\Sigma }}_k$ following must be satisfied

$$(1-{\delta }_k)\Vert \mathbf{x}{\Vert }_2^2\le \Vert \mathrm{\Phi }\mathbf{x}{\Vert }_2^2\le (1+{\delta }_k)\Vert \mathbf{x}{\Vert }_2^2$$

and

$$(1-{\delta }_l)\Vert \mathbf{x}{\Vert }_2^2\le \Vert \mathrm{\Phi }\mathbf{x}{\Vert }_2^2\le (1+{\delta }_l)\Vert \mathbf{x}{\Vert }_2^2.$$

Since ${\delta }_k$ is smallest such value for which these inequalities are satisfied hence ${\delta }_l$ cannot be smaller than ${\delta }_k$.

18.8.1. The First Restricted Isometry Constant

We consider the simplest case where $K=1$. We can write $\mathrm{\Phi }$ in terms of its column vectors

$$\mathrm{\Phi }=\left[\begin{array}{ccc}{\varphi }_1& \dots & {\varphi }_N\end{array}\right].$$

1. Now a $1$-sparse vector $\mathbf{x}$ consists of only one nonzero entry.

2. Say that $\mathbf{x}$ is nonzero at index $j$.

3. Then $\mathrm{\Phi }\mathbf{x}$ is nothing but $x_j{\varphi }_j$.

4. With this the restricted isometry inequality can be written as

   $$(1-{\delta }_1)|x_j{|}^2\le \Vert x_j{\varphi }_j{\Vert }_2^2\le (1+{\delta }_1)|x_j{|}^2.$$

5. Dividing by $|x_j{|}^2$ we get

   $$(1-{\delta }_1)\le \Vert {\varphi }_j{\Vert }_2^2\le (1+{\delta }_1).$$

Let us formalize this in the following theorem.

Theorem 18.47 (Restricted isometry constants of order 1)

If a matrix $\mathrm{\Phi }$ satisfies RIP of order $K\ge 1$ then the squared lengths of columns of $\mathrm{\Phi }$ satisfy the following bounds

(18.47)$$1-{\delta }_1\le \Vert {\varphi }_j{\Vert }_2^2\le 1+{\delta }_1\mathrm{\forall }1\le j\le N.$$

When ${\delta }_1=0$ then all columns of $\mathrm{\Phi }$ are unit norm. Now if columns of $\mathrm{\Phi }$ span ${\mathbb{C}}^M$ then $\mathrm{\Phi }$ can also be considered as a dictionary for ${\mathbb{C}}^M$ (see Definition 18.4).

Remark 18.8

A dictionary (Definition 18.4) satisfies RIP of order 1 with ${\delta }_1=0$.

18.8.2. Sums and Differences of Sparse Vectors

Theorem 18.48

Let $\mathbf{x},\mathbf{y}\in {\mathbb{C}}^N$ with $\mathbf{x}\in {\mathrm{\Sigma }}_k$ and $\mathbf{y}\in {\mathrm{\Sigma }}_l$; i.e., $\Vert \mathbf{x}{\Vert }_0\le k$ and $\Vert \mathbf{y}{\Vert }_0\le l$. Then

$$(1-{\delta }_{k+l})\Vert \mathbf{x}\pm \mathbf{y}{\Vert }_2^2\le \Vert \mathrm{\Phi }\mathbf{x}\pm \mathrm{\Phi }\mathbf{y}{\Vert }_2^2\le (1+{\delta }_{k+l})\Vert \mathbf{x}\pm \mathbf{y}{\Vert }_2^2$$

as long as $\mathrm{\Phi }$ satisfies RIP of order $k+l$.

Proof. We know that

$$\Vert \mathbf{x}\pm \mathbf{y}{\Vert }_0\le \Vert \mathbf{x}{\Vert }_0+\Vert \mathbf{y}{\Vert }_0\le k+l.$$

Thus $\mathbf{x}\pm \mathbf{y}\in {\mathrm{\Sigma }}_{k+l}$. The result follows.

18.8.3. Distance Between Sparse Vectors

Let $\mathbf{x},\mathbf{y}\in {\mathrm{\Sigma }}_K$. Then clearly $\mathbf{x}-\mathbf{y}\in {\mathrm{\Sigma }}_{2K}$.

The ${\ell }_2$ distance between vectors is given by

$$d(\mathbf{x},\mathbf{y})=\Vert \mathbf{x}-\mathbf{y}{\Vert }_2=\sqrt{(\mathbf{x}-\mathbf{y}{)}^H(\mathbf{x}-\mathbf{y})}.$$

Now if $\mathrm{\Phi }$ satisfies RIP of order $2K$ then we can see that it approximately preserves ${\ell }_2$ distances between $K$-sparse vectors.

Theorem 18.49 (Approximation preservation of distances)

Let $\mathbf{x},\mathbf{y}\in {\mathrm{\Sigma }}_K\subset {\mathbb{C}}^N$. Let $\mathrm{\Phi }\mathbf{x},\mathrm{\Phi }\mathbf{y}\in {\mathbb{C}}^M$ be corresponding embeddings. If $\mathrm{\Phi }$ satisfies RIP of order $2K$, then

$$(1-{\delta }_{2K})d^2(\mathbf{x},\mathbf{y})\le d^2(\mathrm{\Phi }\mathbf{x},\mathrm{\Phi }\mathbf{y})\le (1+{\delta }_{2K})d^2(\mathbf{x},\mathbf{y}).$$

Proof. Since $\mathrm{\Phi }$ satisfies RIP of order $2K$ hence for every vector $\mathbf{v}\in {\mathrm{\Sigma }}_{2K}$ we have

$$(1-{\delta }_{2K})\Vert \mathbf{v}{\Vert }_2^2\le \Vert \mathrm{\Phi }\mathbf{v}{\Vert }_2^2\le (1+{\delta }_{2K})\Vert \mathbf{v}{\Vert }_2^2.$$

But then $\mathbf{x}-\mathbf{y}\in {\mathrm{\Sigma }}_{2K}$ for every $\mathbf{x},\mathbf{y}\in {\mathrm{\Sigma }}_K$ and

$$d^2(\mathbf{x},\mathbf{y})=\Vert \mathbf{x}-\mathbf{y}{\Vert }_2^2$$

and

$$d^2(\mathrm{\Phi }\mathbf{x},\mathrm{\Phi }\mathbf{y})=\Vert \mathrm{\Phi }\mathbf{x}-\mathrm{\Phi }\mathbf{y}{\Vert }_2^2=\Vert \mathrm{\Phi }(\mathbf{x}-\mathbf{y}){\Vert }_2^2.$$

Thus we have the result.

18.8.4. RIP with Unit Length Sparse Vectors

Sometimes it is convenient to state RIP in terms of unit length sparse vectors.

Theorem 18.50 (RIP for unit length sparse vectors)

Let $\mathbf{x}$ be some arbitrary unit length (i.e., $\Vert \mathbf{x}{\Vert }_2=1$) vector belonging to ${\mathrm{\Sigma }}_K$. A matrix $\mathrm{\Phi }$ is said to satisfy RIP of order $K$ if and only if the following holds

(18.48)$$(1-{\delta }_K)\le \Vert \mathrm{\Phi }\mathbf{x}{\Vert }_2^2\le (1+{\delta }_K)$$

for every $\mathbf{x}\in {\mathrm{\Sigma }}_K$ with $\Vert \mathbf{x}{\Vert }_2=1$.

Proof. If $\mathrm{\Phi }$ satisfies RIP of order $K$ then by putting $\Vert \mathbf{x}{\Vert }_2=1$ in (18.43) we get (18.48).

Now the converse.

1. We assume (18.48) holds for all unit norm vectors $\mathbf{x}\in {\mathrm{\Sigma }}_K$.

2. We need to show that (18.43) holds for all $\mathbf{x}\in {\mathrm{\Sigma }}_K$.

3. For $\mathbf{x}=\mathbf{0}$ the bounds in (18.43) are trivially satisfied.

4. Let $\mathbf{x}\in {\mathrm{\Sigma }}_K$ be some nonzero vector.

5. Let $\hat{\mathbf{x}}=\frac{\mathbf{x}}{\Vert \mathbf{x}{\Vert }_2}$.

6. Clearly $\hat{\mathbf{x}}$ is unit length. Hence

   $$\begin{array}{rl}& (1-{\delta }_K)\le \Vert \mathrm{\Phi }\hat{\mathbf{x}}{\Vert }_2^2\le (1+{\delta }_K)\\ ⟹& (1-{\delta }_K)\le {\Vert \mathrm{\Phi }\frac{\mathbf{x}}{\Vert \mathbf{x}{\Vert }_2}\Vert }_2^2\le (1+{\delta }_K)\\ ⟹& (1-{\delta }_K)\Vert \mathbf{x}{\Vert }_2^2\le \Vert \mathrm{\Phi }\mathbf{x}{\Vert }_2^2\le (1+{\delta }_K)\Vert \mathbf{x}{\Vert }_2^2.\end{array}$$

7. Thus $\mathrm{\Phi }$ satisfies RIP of order $K$.

18.8.5. Singular and Eigen Values of $K$-Submatrices

Consider any index set $J\subset \{1,\dots ,N\}$ with $|J|=K$. Let ${\mathrm{\Phi }}_J$ be a sub matrix of $\mathrm{\Phi }$ consisting of columns indexed by $J$. Assume $K\le M$. We define

$$\mathbf{G}\triangleq {\mathrm{\Phi }}_J^H{\mathrm{\Phi }}_J\in {\mathbb{C}}^{K\times K}$$

as the Gram matrix for columns of ${\mathrm{\Phi }}_J$ (see Gram Matrices).

We consider the eigen values of $\mathbf{G}$ given by

$$\mathbf{G}\mathbf{x}=\lambda \mathbf{x}$$

for some $\mathbf{x}\in {\mathbb{C}}^K$ and $\mathbf{x}\ne \mathbf{0}$. We will show that eigen values of $\mathbf{G}$ are bounded by RIP constant.

In the running example

$$\begin{array}{r}\mathbf{G}=\left[\begin{array}{ccc}1& 0& 0.5\\ 0& 1& 0.5\\ 0.5& 0.5& 1\end{array}\right].\end{array}$$

Eigen values of G are $(0.2929,1,1.7071)$.

Theorem 18.51

Let $\mathrm{\Phi }$ satisfy the RIP of order $K$ where $K\le M$. Let ${\mathrm{\Phi }}_J$ be any sub matrix of $\mathrm{\Phi }$ with $K$ columns. Then the eigen values of $\mathbf{G}={\mathrm{\Phi }}_J^H{\mathrm{\Phi }}_J$ lie in the range $[1-{\delta }_K,1+{\delta }_K]$.

Proof. We note that $\mathbf{G}\in {\mathbb{C}}^{K\times K}$.

1. Let $\lambda$ be some eigen value of $\mathbf{G}$.

2. Let $\mathbf{x}\in {\mathbb{C}}^K$ be a corresponding (nonzero) eigenvector.

3. Then

   $$\begin{array}{rl}& \mathbf{G}\mathbf{x}=\lambda \mathbf{x}\\ ⟹& {\mathbf{x}}^H\mathbf{G}\mathbf{x}={\mathbf{x}}^H\lambda \mathbf{x}\\ ⟹& {\mathbf{x}}^H{\mathrm{\Phi }}_J^H{\mathrm{\Phi }}_J\mathbf{x}=\lambda \Vert \mathbf{x}{\Vert }_2^2\\ ⟹& \Vert {\mathrm{\Phi }}_J\mathbf{x}{\Vert }_2^2=\lambda \Vert \mathbf{x}{\Vert }_2^2.\end{array}$$

4. From (18.46) we recall that ${\delta }_K$ RIP bounds apply for each vector in $\mathbf{x}\in {\mathbb{C}}^K$ for a $K$-column submatrix ${\mathrm{\Phi }}_J$ given by

   $$(1-{\delta }_K)\Vert \mathbf{x}{\Vert }_2^2\le \Vert {\mathrm{\Phi }}_J\mathbf{x}{\Vert }_2^2\le (1+{\delta }_K)\Vert \mathbf{x}{\Vert }_2^2.$$

5. Thus

   $$\begin{array}{rl}& (1-{\delta }_K)\Vert \mathbf{x}{\Vert }_2^2\le \lambda \Vert \mathbf{x}{\Vert }_2^2\le (1+{\delta }_K)\Vert \mathbf{x}{\Vert }_2^2\\ ⟹& (1-{\delta }_K)\le \lambda \le (1+{\delta }_K)\end{array}$$

   since $\mathbf{x}\ne \mathbf{0}$.

Corollary 18.3

Let $\mathrm{\Phi }$ satisfy the RIP of order $K$ where $K\le M$. Let ${\mathrm{\Phi }}_J$ be any submatrix of $\mathrm{\Phi }$ with $K$ columns. Then the Gram matrix $\mathbf{G}={\mathrm{\Phi }}_J^H{\mathrm{\Phi }}_J$ is full rank and invertible. Moreover $\mathbf{G}$ is positive definite.

Proof. From Theorem 18.51, the eigen values are in range $[1-{\delta }_K,1+{\delta }_K]$.

1. Since $\mathrm{\Phi }$ satisfies RIP of order $K$, hence ${\delta }_K<1$.

2. Hence all eigenvalues of $\mathbf{G}$ are positive.

3. Hence $\mathbf{G}$ is positive definite.

4. Hence their product is positive.

5. Thus $det(\mathbf{G})$ is nonzero.

6. Hence $\mathbf{G}$ is invertible.

Theorem 18.52

Let $\mathrm{\Phi }$ satisfy the RIP of order $K$ where $K\le M$. Let ${\mathrm{\Phi }}_J$ be any submatrix of $\mathrm{\Phi }$ with $K$ columns. Then all singular values of ${\mathrm{\Phi }}_J$ are nonzero and they are in the range given by

$$\sqrt{1-{\delta }_K}\le \sigma \le \sqrt{1+{\delta }_K}$$

where $\sigma$ is a singular value of ${\mathrm{\Phi }}_J$.

Proof. This is straight forward application of Lemma 4.74 and Theorem 18.51. Eigen values of ${\mathrm{\Phi }}_J^H{\mathrm{\Phi }}_J$ are nothing but squares of the singular values of ${\mathrm{\Phi }}_J$.

Corollary 18.4

Let $\mathrm{\Phi }$ satisfy the RIP of order $K$ where $K\le M$. Let ${\mathrm{\Phi }}_J$ be any submatrix of $\mathrm{\Phi }$ with $k$ columns where $k\le K$. Then the singular values of ${\mathrm{\Phi }}_J$ are nonzero and they are in the range given by

$$\sqrt{1-{\delta }_K}\le \sigma \le \sqrt{1+{\delta }_K}$$

where $\sigma$ is a singular value of ${\mathrm{\Phi }}_J$.

Proof. Let $\sigma$ be a singular value of ${\mathrm{\Phi }}_J$.

1. Since $\mathrm{\Phi }$ satisfies RIP of order $K$, it also satisfies RIP of order $k\le K$.

2. From Theorem 18.52 we have

   $$\sqrt{1-{\delta }_k}\le \sigma \le \sqrt{1+{\delta }_k}.$$

3. From Theorem 18.46 we have ${\delta }_k\le {\delta }_K$.

4. Thus

   $$1-{\delta }_K\le 1-{\delta }_k,1+{\delta }_k\le 1+{\delta }_K.$$

5. Thus

   $$\sqrt{1-{\delta }_K}\le \sigma \le \sqrt{1+{\delta }_K}.$$

Theorem 18.53

Let $\mathrm{\Phi }$ satisfy the RIP of order $K$ where $K\le M$. Let ${\mathrm{\Phi }}_J$ be any submatrix of $\mathrm{\Phi }$ with $k$ columns where $k\le K$. Then the eigen values of ${\mathrm{\Phi }}_J^H{\mathrm{\Phi }}_J+r\mathbf{I}$ lie in the range

$$[1-{\delta }_K+r,1+{\delta }_K+r].$$

Moreover consider $\mathrm{\Delta }={\mathrm{\Phi }}_J^H{\mathrm{\Phi }}_J-\mathbf{I}$. Then

$$\Vert \mathrm{\Delta }{\Vert }_2\le {\delta }_K.$$

Proof. .

1. From Theorem 18.51 eigen values of ${\mathrm{\Phi }}_J^H{\mathrm{\Phi }}_J$ lie in the range $[1-{\delta }_K,1+{\delta }_K]$.

2. From Lemma 4.69 $\lambda$ is an eigen value of ${\mathrm{\Phi }}_J^H{\mathrm{\Phi }}_J$ if and only if $\lambda +r$ is an eigen value of ${\mathrm{\Phi }}_J^H{\mathrm{\Phi }}_J+r\mathbf{I}$.

3. Hence the result.

Now for $\mathrm{\Delta }={\mathrm{\Phi }}_J^H{\mathrm{\Phi }}_J-\mathbf{I}$

1. The eigen values lie in the range $[-{\delta }_K,{\delta }_K]$.

2. Thus for every eigen value of $\mathrm{\Delta }$ we have $|\lambda |\le {\delta }_K$.

3. Since $\mathrm{\Delta }$ is Hermitian, its spectral norm is nothing but its largest eigen value.

4. Hence

   $$\Vert \mathrm{\Delta }{\Vert }_2\le {\delta }_K.$$

From previous few results we see that bound over eigen values of ${\mathrm{\Phi }}_J^H{\mathrm{\Phi }}_J$ given by $(1-{\delta }_K)\le \lambda \le (1+{\delta }_K)$ is a necessary condition for $\mathrm{\Phi }$ to satisfy RIP of order $K$. We now show that this is also a sufficient condition.

Theorem 18.54

Let $\mathrm{\Phi }$ be an $M\times N$ matrix with $M\le N$. Let $J\subset \{1,\dots ,N\}$ be any index set with $|J|=K\le M$. Let ${\mathrm{\Phi }}_J$ be the $K$-column sub-matrix of $\mathrm{\Phi }$ indexed by $J$. Let $\mathbf{G}={\mathrm{\Phi }}_J^H{\mathrm{\Phi }}_J$ be the Gram matrix of columns of ${\mathrm{\Phi }}_J$. Let the eigen values of $\mathbf{G}$ be $\lambda$. If there exists a number $\delta \in (0,1)$ such that

$$1-\delta \le \lambda \le 1+\delta$$

for every eigen value of $\mathbf{G}$ for every $K$ column submatrix of $\mathrm{\Phi }$, then $\mathrm{\Phi }$ satisfies RIP of order $K$.

Alternatively, let $\mathrm{\Delta }=\mathbf{G}-\mathbf{I}$. If

$$\Vert \mathrm{\Delta }{\Vert }_2\le \delta <1$$

for every $K$ column submatrix of $\mathrm{\Phi }$ then $\mathrm{\Phi }$ satisfies RIP of order $K$.

Alternatively, if singular values of ${\mathrm{\Phi }}_J$ satisfy

$$\sqrt{1-\delta }\le \sigma \le \sqrt{1+\delta }$$

for every ${\mathrm{\Phi }}_J$ then $\mathrm{\Phi }$ satisfies RIP of order $K$.

Proof. Equivalence of sufficient conditions

1. We note that eigen values of $\mathbf{G}$ are related to eigen values of $\mathrm{\Delta }$ by the relation (see Lemma 4.69)

   $${\lambda }_G-1={\lambda }_{\mathrm{\Delta }}⟺{\mathrm{\Lambda }}_G=1+{\lambda }_{\mathrm{\Delta }}.$$

2. Hence

   $$\Vert \mathrm{\Delta }{\Vert }_2\le \delta ⟺-\delta \le {\lambda }_{\mathrm{\Delta }}\le \delta ⟺1-\delta \le {\lambda }_G\le 1+\delta .$$

3. Thus the first two sufficient conditions are equivalent.

4. Lastly the eigen values of $\mathbf{G}$ are squares of singular values of ${\mathrm{\Phi }}_J$.

5. Thus all sufficient conditions are equivalent.

Proof of sufficient condition

1. Now let $\mathbf{x}\in {\mathrm{\Sigma }}_K$ be an arbitrary vector.

2. Let $J=\mathrm{supp}(\mathbf{x})$.

3. Clearly $|J|\le K$. If $|J|<K$ then augment $J$ by adding some indices arbitrarily till we get $|J|=K$.

4. Clearly ${\mathbf{x}}_J$ is an arbitrary vector in ${\mathbb{C}}^K$ and $\mathrm{\Phi }\mathbf{x}={\mathrm{\Phi }}_J{\mathbf{x}}_J$.

5. Now let ${\lambda }_1$ be the largest and ${\lambda }_k$ be the smallest eigen value of $\mathbf{G}={\mathrm{\Phi }}_J^H{\mathrm{\Phi }}_J$.

6. $\mathbf{G}$ is Hermitian and all its eigen values are positive, hence it is positive definite.

7. From Lemma 4.68 we get

   $${\lambda }_k\Vert \mathbf{x}{\Vert }_2^2\le {\mathbf{x}}^H\mathbf{G}\mathbf{x}\le {\lambda }_1\Vert \mathbf{x}{\Vert }_2^2\mathrm{\forall }\mathbf{x}\in {\mathbb{C}}^K.$$

8. Applying the limits on the eigen values and using ${\mathbf{x}}^H\mathbf{G}\mathbf{x}=\Vert {\mathrm{\Phi }}_J\mathbf{x}{\Vert }_2^2$, we get

   $$(1-\delta )\Vert \mathbf{x}{\Vert }_2^2\le \Vert {\mathrm{\Phi }}_J\mathbf{x}{\Vert }_2^2\le (1+\delta )\Vert \mathbf{x}{\Vert }_2^2\mathrm{\forall }\mathbf{x}\in {\mathbb{C}}^K.$$

9. Since this holds for every index set $J$ with $|J|=K$ hence an equivalent statement is

   $$(1-\delta )\Vert \mathbf{x}{\Vert }_2^2\le \Vert \mathrm{\Phi }\mathbf{x}{\Vert }_2^2\le (1+\delta )\Vert \mathbf{x}{\Vert }_2^2\mathrm{\forall }\mathbf{x}\in {\mathrm{\Sigma }}_K\subset {\mathbb{C}}^N.$$

10. Thus $\mathrm{\Phi }$ indeed satisfies RIP of order $K$ with some ${\delta }_K$ not larger than $\delta$.

Theorem 18.55

Let $\mathrm{\Phi }$ satisfy the RIP of order $K$ where $K\le M$. Let ${\mathrm{\Phi }}_J$ be any submatrix of $\mathrm{\Phi }$ with $k$ columns where $k\le K$. Let ${\mathrm{\Phi }}_J^{†}$ be its Moore-Penrose pseudo-inverse. Then the singular values of ${\mathrm{\Phi }}_J^{†}$ are nonzero and they are in the range given by

$$\frac{1}{\sqrt{1+{\delta }_K}}\le \sigma \le \frac{1}{\sqrt{1-{\delta }_K}}$$

where $\sigma$ is a singular value of ${\mathrm{\Phi }}_J^{†}$.

Proof. Construction of pseudoinverse of a matrix through its singular value decomposition is discussed in Lemma 4.79.

1. Lemma 4.80 shows that if $\sigma$ is a nonzero singular value of ${\mathrm{\Phi }}_J^{†}$ then $\frac{1}{\sigma }$ is a nonzero singular value of ${\mathrm{\Phi }}_J$.

2. From Corollary 18.4 we have that if $\frac{1}{\sigma }$ is a singular value of ${\mathrm{\Phi }}_J$ then,

   $$\sqrt{1-{\delta }_K}\le \frac{1}{\sigma }\le \sqrt{1+{\delta }_K}$$

3. Inverting the terms in the inequalities we get our result.

Theorem 18.56

Eigen values of $\mathbf{G}={\mathrm{\Phi }}_J^H{\mathrm{\Phi }}_J$ provide a lower bound on ${\delta }_K$ given by

$${\delta }_K\ge max(1-{\lambda }_{min},{\lambda }_{max}-1)$$

where $J$ is some index set choosing $K$ columns of $\mathrm{\Phi }$ and ${\delta }_K$ is the $K$-th restricted isometry constant for $\mathrm{\Phi }$.

In other words, singular values of ${\mathrm{\Phi }}_J$ provide a lower bound on ${\delta }_K$ given by

$${\delta }_K\ge max(1-{\sigma }_{min}^2,{\sigma }_{max}^2-1)$$

Proof. Obvious.

In the running example, the bounds tell us that

$${\delta }_3\ge 0.7071.$$

Certainly we have to consider all possible $(\genfrac{}{}{0ex}{}{N}{K})$ sub-matrices ${\mathrm{\Phi }}_J$ to come up with an overall lower bound on ${\delta }_K$.

This result doesn’t provide us any upper bound on ${\delta }_K$.

Theorem 18.57

Let $\mathrm{\Phi }$ satisfy the RIP of order $K$ where $K\le M$. Let ${\mathrm{\Phi }}_J$ be any submatrix of $\mathrm{\Phi }$ with $k$ columns where $k\le K$. Then

$$\Vert {\mathrm{\Phi }}_J\mathbf{x}{\Vert }_2\le \sqrt{1+{\delta }_K}\Vert \mathbf{x}{\Vert }_2\mathrm{\forall }\mathbf{x}\in {\mathbb{C}}^k.$$

Moreover

$$\Vert {\mathrm{\Phi }}_J^H\mathbf{y}{\Vert }_2\le \sqrt{1+{\delta }_K}\Vert \mathbf{y}{\Vert }_2\mathrm{\forall }\mathbf{y}\in {\mathbb{C}}^M.$$

Proof. We note that ${\mathrm{\Phi }}_J$ is an $M\times k$ matrix.

1. Let ${\sigma }_1$ be the largest singular value of ${\mathrm{\Phi }}_J$.

2. Then by Lemma 4.77 we have

   $$\Vert {\mathrm{\Phi }}_J\mathbf{x}{\Vert }_2\le {\sigma }_1\Vert \mathbf{x}{\Vert }_2\mathrm{\forall }\mathbf{x}\in {\mathbb{C}}^k.$$

   and

   $$\Vert {\mathrm{\Phi }}_J^H\mathbf{y}{\Vert }_2\le {\sigma }_1\Vert \mathbf{y}{\Vert }_2\mathrm{\forall }\mathbf{y}\in {\mathbb{C}}^M.$$

3. From Theorem 18.52 and Corollary 18.4 we get

   $${\sigma }_1\le \sqrt{1+{\delta }_K}.$$

4. This completes the proof.

First inequality is a restatement of restricted isometry property in (18.46). Second inequality is interesting. In compressive sensing terms, $\mathbf{y}$ is a measurement vector and we are using ${\mathrm{\Phi }}_J^H$ to project $\mathbf{y}$ back into ${\mathbb{C}}^N$ over a $k$ sparse support identified by $J$. The inequality provides an upper bound on how much the length can increase during this operation.

Theorem 18.58

Let $\mathrm{\Phi }$ satisfy the RIP of order $K$ where $K\le M$. Let ${\mathrm{\Phi }}_J$ be any submatrix of $\mathrm{\Phi }$ with $k$ columns where $k\le K$. Let ${\mathrm{\Phi }}_J^{†}$ be its Moore-Penrose pseudo-inverse. Then

$$\Vert {\mathrm{\Phi }}_J^{†}\mathbf{y}{\Vert }_2\le \frac{1}{\sqrt{1-{\delta }_K}}\Vert \mathbf{y}{\Vert }_2\mathrm{\forall }\mathbf{y}\in {\mathbb{C}}^M.$$

Proof. We note that ${\mathrm{\Phi }}_J^{†}$ is an $k\times M$ matrix.

1. Let ${\sigma }_1$ be the largest singular value of ${\mathrm{\Phi }}_J^{†}$.

2. Then by Lemma 4.77 we have

   $$\Vert {\mathrm{\Phi }}_J^{†}\mathbf{y}{\Vert }_2\le {\sigma }_1\Vert \mathbf{y}{\Vert }_2\mathrm{\forall }y\in {\mathbb{C}}^M.$$

3. From Theorem 18.55 we see that singular values of ${\mathrm{\Phi }}_J^{†}$ satisfy the inequalities

   $$\frac{1}{\sqrt{1+{\delta }_K}}\le \sigma \le \frac{1}{\sqrt{1-{\delta }_K}}.$$

4. Thus

   $${\sigma }_1\le \frac{1}{\sqrt{1-{\delta }_K}}.$$

5. Plugging it in we get

   $$\Vert {\mathrm{\Phi }}_J^{†}\mathbf{y}{\Vert }_2\le \frac{1}{\sqrt{1-{\delta }_K}}\Vert \mathbf{y}{\Vert }_2\mathrm{\forall }\mathbf{y}\in {\mathbb{C}}^M.$$

In the previous theorem we saw that back-projection using ${\mathrm{\Phi }}_J^H$ had an upper bound on how much the length of measurement vector could increase. In this theorem we see another upper bound on how much the length of measurement vector can increase when back projected using the pseudo inverse of ${\mathrm{\Phi }}_J$.

Theorem 18.59

Let $\mathrm{\Phi }$ satisfy the RIP of order $K$ where $K\le M$. Let ${\mathrm{\Phi }}_J$ be any submatrix of $\mathrm{\Phi }$ with $k$ columns where $k\le K$. Then

$$(1-{\delta }_K)\Vert \mathbf{x}{\Vert }_2\le \Vert {\mathrm{\Phi }}_J^H{\mathrm{\Phi }}_J\mathbf{x}{\Vert }_2\le (1+{\delta }_K)\Vert \mathbf{x}{\Vert }_2\mathrm{\forall }\mathbf{x}\in {\mathbb{C}}^k.$$

Moreover

$$\frac{1}{1+{\delta }_K}\Vert \mathbf{x}{\Vert }_2\le \Vert {\left({\mathrm{\Phi }}_J^H{\mathrm{\Phi }}_J\right)}^{-1}\mathbf{x}{\Vert }_2\le \frac{1}{1-{\delta }_K}\Vert \mathbf{x}{\Vert }_2\mathrm{\forall }\mathbf{x}\in {\mathbb{C}}^k.$$

Proof. We note that ${\mathrm{\Phi }}_J$ is a full column rank tall matrix.

1. We recall that all singular values of ${\mathrm{\Phi }}_J$ are positive and are bounded by (Corollary 18.4):

   $$\sqrt{1-{\delta }_K}\le {\sigma }_k\le \cdots \le {\sigma }_1\le \sqrt{1+{\delta }_K}$$

   where ${\sigma }_1,\dots ,{\sigma }_k$ are the singular values of ${\mathrm{\Phi }}_J$ (in descending order).

2. We note that ${\mathrm{\Phi }}_J^H{\mathrm{\Phi }}_J$ is an $k\times k$ matrix which is invertible (Corollary 18.3).

3. From Lemma 4.83 we get

   $${\sigma }_k^2\Vert \mathbf{x}{\Vert }_2\le \Vert {\mathrm{\Phi }}_J^H{\mathrm{\Phi }}_J\mathbf{x}{\Vert }_2\le {\sigma }_1^2\Vert \mathbf{x}{\Vert }_2\mathrm{\forall }\mathbf{x}\in {\mathbb{C}}^k.$$

4. Applying the bounds on ${\sigma }_i$ we get the result

   $$(1-{\delta }_K)\Vert \mathbf{x}{\Vert }_2\le \Vert {\mathrm{\Phi }}_J^H{\mathrm{\Phi }}_J\mathbf{x}{\Vert }_2\le (1+{\delta }_K)\Vert \mathbf{x}{\Vert }_2\mathrm{\forall }\mathbf{x}\in {\mathbb{C}}^k.$$

5. From Lemma 4.85 we have the bounds for ${\left({\mathrm{\Phi }}_J^H{\mathrm{\Phi }}_J\right)}^{-1}$ given by

   $$\frac{1}{{\sigma }_1^2}\Vert \mathbf{x}{\Vert }_2\le \Vert {\left({\mathrm{\Phi }}_J^H{\mathrm{\Phi }}_J\right)}^{-1}\mathbf{x}{\Vert }_2\le \frac{1}{{\sigma }_k^2}\Vert \mathbf{x}{\Vert }_2\mathrm{\forall }\mathbf{x}\in {\mathbb{C}}^k.$$

6. Applying the bounds on ${\sigma }_i$ we get the result

   $$\frac{1}{1+{\delta }_K}\Vert \mathbf{x}{\Vert }_2\le \Vert {\left({\mathrm{\Phi }}_J^H{\mathrm{\Phi }}_J\right)}^{-1}\mathbf{x}{\Vert }_2\le \frac{1}{1-{\delta }_K}\Vert \mathbf{x}{\Vert }_2\mathrm{\forall }\mathbf{x}\in {\mathbb{C}}^k.$$

In the sequel we will discuss that ${\mathrm{\Phi }}^H\mathrm{\Phi }\mathbf{x}$ can work as a very good proxy for the signal $\mathbf{x}$. The results in this theorem are very comforting in this regard.

Theorem 18.60

Let $\mathrm{\Phi }$ satisfy the RIP of order $K$ where $K\le M$. Let ${\mathrm{\Phi }}_J$ be any sub matrix of $\mathrm{\Phi }$ with $k$ columns where $k\le K$. Then

$$\Vert ({\mathrm{\Phi }}_J^H{\mathrm{\Phi }}_J-\mathbf{I})\mathbf{x}{\Vert }_2\le {\delta }_K\Vert \mathbf{x}{\Vert }_2\mathrm{\forall }\mathbf{x}\in {\mathbb{C}}^k.$$

Proof. .

1. From Theorem 18.53 we get

   $$\Vert {\mathrm{\Phi }}_J^H{\mathrm{\Phi }}_J-\mathbf{I}{\Vert }_2\le {\delta }_k\le {\delta }_K.$$

2. Thus since spectral norm is subordinate

   $$\Vert ({\mathrm{\Phi }}_J^H{\mathrm{\Phi }}_J-\mathbf{I})\mathbf{x}{\Vert }_2\le \Vert {\mathrm{\Phi }}_J^H{\mathrm{\Phi }}_J-\mathbf{I}{\Vert }_2\Vert \mathbf{x}{\Vert }_2\le {\delta }_K\Vert \mathbf{x}{\Vert }_2\mathrm{\forall }\mathbf{x}\in {\mathbb{C}}^k.$$

18.8.6. Approximate Orthogonality

We are going to show that disjoint sets of columns from $\mathrm{\Phi }$ span nearly orthogonal subspaces. This property is proved in [61].

Theorem 18.61

Let $\mathrm{\Phi }$ satisfy the RIP of order $K$ where $K\le M$. Let $S$ and $T$ denote index sets over the columns of $\mathrm{\Phi }$ with $|S|+|T|\le K$ and $S\cap T=\varnothing$. In other words, $S$ and $T$ are disjoint index sets. Let ${\mathrm{\Phi }}_S$ and ${\mathrm{\Phi }}_T$ denote corresponding sub-matrices consisting of columns indexed by $S$ and $T$ respectively. Then

$$\Vert {\mathrm{\Phi }}_S^H{\mathrm{\Phi }}_T{\Vert }_2\le {\delta }_K$$

where $\Vert \cdot {\Vert }_2$ denotes the $2$-norm or spectral norm of a matrix.

Proof. Define $R=S\cup T$.

1. Consider the sub-matrix ${\mathrm{\Phi }}_R$.

2. Construct another matrix $\mathrm{\Psi }={\mathrm{\Phi }}_R^H{\mathrm{\Phi }}_R-\mathbf{I}$.

3. The off-diagonal entries of $\mathrm{\Psi }$ are nothing but inner products of columns of ${\mathrm{\Phi }}_R$.

4. We note that every entry in the matrix ${\mathrm{\Phi }}_S^H{\mathrm{\Phi }}_T$ is an entry in $\mathrm{\Psi }$.

5. Moreover, ${\mathrm{\Phi }}_S^H{\mathrm{\Phi }}_T$ is a submatrix of $\mathrm{\Psi }$.

6. The spectral norm of a sub-matrix is never greater than the spectral norm of the matrix containing it.

7. Thus

   $$\Vert {\mathrm{\Phi }}_S^H{\mathrm{\Phi }}_T{\Vert }_2\le \Vert {\mathrm{\Phi }}_R^H{\mathrm{\Phi }}_R-\mathbf{I}{\Vert }_2.$$

8. From Theorem 18.53 the eigen values of ${\mathrm{\Phi }}_R^H{\mathrm{\Phi }}_R-\mathbf{I}$ satisfy

   $$1-{\delta }_K-1\le \lambda \le 1+{\delta }_K-1.$$

9. Thus the spectral norm of ${\mathrm{\Phi }}_R^H{\mathrm{\Phi }}_R-\mathbf{I}$ which is its largest eigen value (see Theorem 4.145) satisfies

   $$\Vert {\mathrm{\Phi }}_R^H{\mathrm{\Phi }}_R-\mathbf{I}{\Vert }_2\le {\delta }_K.$$

10. Plugging back we get

    $$\Vert {\mathrm{\Phi }}_S^H{\mathrm{\Phi }}_T{\Vert }_2\le {\delta }_K.$$

This result has a useful corollary. It establishes the approximate orthogonality between a set of columns in $\mathrm{\Phi }$ and portion of a sparse vector not covered by those columns.

Corollary 18.5

Let $\mathrm{\Phi }$ satisfy the RIP of order $K$ where $K\le M$. Let $T\subset \{1,\dots ,N\}$ be an index set and let $\mathbf{x}\in {\mathbb{C}}^N$ be some vector. Let $S=\mathrm{supp}(\mathbf{x})$. Further let us assume that $K\ge |T\cup S|$. Define $R=S\setminus T$.

Then the following holds

$$\Vert {\mathrm{\Phi }}_T^H\mathrm{\Phi }{\mathbf{x}}_R{\Vert }_2\le {\delta }_K\Vert {\mathbf{x}}_R{\Vert }_2$$

where ${\mathbf{x}}_R$ is obtained by keeping entries in $\mathbf{x}$ indexed by $R$ while setting others to 0 (see Definition 18.11).

Proof. The set $R$ denotes the indices at which $\mathbf{x}$ is nonzero but not yet covered in $T$. In a typical sparse recovery algorithm, one has discovered a candidate support $T$ which may not include all of $S$.

1. Since

   $$\mathrm{\Phi }\mathbf{x}=\sum _{i=1}^N{\varphi }_i{x}_i$$

   and ${\mathbf{x}}_R$ is zero on entries not indexed by $R$, hence

   $$\mathrm{\Phi }{\mathbf{x}}_R={\mathrm{\Phi }}_R{\mathbf{x}}_R$$

   where on the R.H.S. ${\mathbf{x}}_R\in {\mathbb{C}}^{|R|}$ by dropping the 0 entries from it not indexed by $R$ (see Definition 18.11).

2. Thus we have

   $$\Vert {\mathrm{\Phi }}_T^H\mathrm{\Phi }{\mathbf{x}}_R{\Vert }_2=\Vert {\mathrm{\Phi }}_T^H{\mathrm{\Phi }}_R{\mathbf{x}}_R{\Vert }_2.$$

3. From Lemma 4.90 we know that any operator norm is subordinate.

4. Thus

   $$\Vert {\mathrm{\Phi }}_T^H{\mathrm{\Phi }}_R{\mathbf{x}}_R{\Vert }_2\le \Vert {\mathrm{\Phi }}_T^H{\mathrm{\Phi }}_R{\Vert }_2\Vert {\mathbf{x}}_R{\Vert }_2.$$

5. Since $K\ge |T\cup S|$ hence we have

   $$|R|=|S\setminus T|\le K.$$

6. Further $T$ and $R$ are disjoint and $|T\cup R|\le K$.

7. Applying Theorem 18.61 we get

   $$\Vert {\mathrm{\Phi }}_T^H{\mathrm{\Phi }}_R{\Vert }_2\le {\delta }_K.$$

8. Putting back, we get our desired result

   $$\Vert {\mathrm{\Phi }}_T^H\mathrm{\Phi }{\mathbf{x}}_R{\Vert }_2\le {\delta }_K\Vert {\mathbf{x}}_R{\Vert }_2.$$

18.8.7. Signal Proxy

We can use the results so far to formalize the idea of signal proxy.

Theorem 18.62

Let $\mathbf{x}$ be a $k$-sparse signal Let $\mathrm{\Phi }$ satisfy the RIP of order $k+l$ or higher. Let $\mathbf{p}$ be defined as

$$\mathbf{p}=({\mathrm{\Phi }}^H\mathrm{\Phi }\mathbf{x}){|}_l$$

i.e. $\mathbf{p}$ is obtained by keeping the $l$ largest entries in $\mathbf{b}={\mathrm{\Phi }}^H\mathrm{\Phi }\mathbf{x}$. Then the following holds

$$\Vert \mathbf{p}{\Vert }_2\le (1+{\delta }_l+{\delta }_{k+l})\Vert \mathbf{x}{\Vert }_2.$$

Proof. Let $A=\mathrm{supp}(\mathbf{x})$ and $B=\mathrm{supp}(\mathbf{p})$.

1. Then $|A|\le k$ and $|B|\le l$.

2. Clearly

   $$\mathbf{p}=({\mathrm{\Phi }}^H\mathrm{\Phi }\mathbf{x}){|}_l=({\mathrm{\Phi }}^H\mathrm{\Phi }\mathbf{x}{)}_B.$$

3. From Theorem 18.20 we get

   $$\mathbf{p}={\mathrm{\Phi }}_B^H\mathrm{\Phi }\mathbf{x}.$$

4. Let $C=A\setminus B$.

5. Since $\mathbf{x}$ is supported on $A$ only, hence we can write

   $$\mathbf{x}={\mathbf{x}}_B+{\mathbf{x}}_C.$$

6. Thus from Corollary 18.1 we get ($B$ and $C$ are disjoint)

   $$\mathrm{\Phi }\mathbf{x}={\mathrm{\Phi }}_B{\mathbf{x}}_B+{\mathrm{\Phi }}_C{\mathbf{x}}_C.$$

7. Thus we have

   $$\mathbf{p}={\mathrm{\Phi }}_B^H{\mathrm{\Phi }}_B{\mathbf{x}}_B+{\mathrm{\Phi }}_B^H{\mathrm{\Phi }}_C{\mathbf{x}}_C.$$

8. Using triangle inequality we can write

   $$\Vert \mathbf{p}{\Vert }_2\le \Vert {\mathrm{\Phi }}_B^H{\mathrm{\Phi }}_B{\mathbf{x}}_B{\Vert }_2+\Vert {\mathrm{\Phi }}_B^H{\mathrm{\Phi }}_C{\mathbf{x}}_C{\Vert }_2.$$

9. Theorem 18.59 gives us

   $$\Vert {\mathrm{\Phi }}_B^H{\mathrm{\Phi }}_B{\mathbf{x}}_B{\Vert }_2\le (1+{\delta }_l)\Vert {\mathbf{x}}_B{\Vert }_2.$$

10. Since $B$ and $C$ are disjoint, hence Theorem 18.61 gives us

    $$\Vert {\mathrm{\Phi }}_B^H{\mathrm{\Phi }}_C{\mathbf{x}}_C{\Vert }_2\le {\delta }_{k+l}\Vert {\mathbf{x}}_C{\Vert }_2.$$

11. Since $B$ and $C$ are disjoint, hence

    $$\Vert {\mathbf{x}}_B{\Vert }_2\le \Vert \mathbf{x}{\Vert }_2\text{ and }\Vert {\mathbf{x}}_C{\Vert }_2\le \Vert \mathbf{x}{\Vert }_2.$$

12. Finally

    $$\Vert \mathbf{p}{\Vert }_2\le (1+{\delta }_l)\Vert {\mathbf{x}}_B{\Vert }_2+{\delta }_{k+l}\Vert {\mathbf{x}}_C{\Vert }_2\le (1+{\delta }_l+{\delta }_{k+l})\Vert \mathbf{x}{\Vert }_2.$$

18.8.8. RIP and Inner Product

Let $\mathbf{x}$ and ${\mathbf{x}}^{\prime }$ be two different vectors in ${\mathbb{C}}^N$ such that their support is disjoint. i.e. if

$$T=\mathrm{supp}(\mathbf{x})\subseteq \{1,\dots ,N\}$$

and

$$T^{\prime }=\mathrm{supp}({\mathbf{x}}^{\prime })\subseteq \{1,\dots ,N\}$$

then $T\cap T^{\prime }=\varnothing$.

Clearly

$$\Vert \mathbf{x}{\Vert }_0=|T|$$

and

$$\Vert {\mathbf{x}}^{\prime }{\Vert }_0=|T^{\prime }|.$$

Since the support of $\mathbf{x}$ and ${\mathbf{x}}^{\prime }$ are disjoint hence it is straightforward that

$$⟨\mathbf{x},{\mathbf{x}}^{\prime }⟩=0.$$

What can we say about the inner product of their corresponding embedded vectors $\mathrm{\Phi }\mathbf{x}$ and $\mathrm{\Phi }{\mathbf{x}}^{\prime }$?

Following theorem provides an upper bound on the magnitude of the inner product when the signal vectors $\mathbf{x},{\mathbf{x}}^{\prime }$ belong to the Euclidean space ${\mathbb{R}}^N$. This result is adapted from [21].

Theorem 18.63

Assume that the sensing matrix $\mathrm{\Phi }\in {\mathbb{R}}^{M\times N}$. For all $\mathbf{x},{\mathbf{x}}^{\prime }\in {\mathbb{R}}^N$ supported on disjoint subsets $T,T^{\prime }\subseteq \{1,\dots ,N\}$ with $|T|<k$ and $|T|<k^{\prime }$, we have

$$|⟨\mathrm{\Phi }\mathbf{x},\mathrm{\Phi }{\mathbf{x}}^{\prime }⟩|\le {\delta }_{k+k^{\prime }}\Vert \mathbf{x}{\Vert }_2\Vert {\mathbf{x}}^{\prime }{\Vert }_2$$

where ${\delta }_{k+k^{\prime }}$ is the restricted isometry constant for the sparsity level $k+k^{\prime }$.

Proof. Let $\hat{\mathbf{x}}=\frac{\mathbf{x}}{\Vert \mathbf{x}{\Vert }_2}$ and $\widehat{{\mathbf{x}}^{\prime }}=\frac{{\mathbf{x}}^{\prime }}{\Vert {\mathbf{x}}^{\prime }{\Vert }_2}$ be the corresponding unit norm vectors.

1. Then

   $$⟨\mathrm{\Phi }\mathbf{x},\mathrm{\Phi }{\mathbf{x}}^{\prime }⟩=⟨\mathrm{\Phi }\hat{x},\mathrm{\Phi }\widehat{x^{\prime }}⟩\Vert \mathbf{x}{\Vert }_2\Vert {\mathbf{x}}^{\prime }{\Vert }_2.$$

2. Hence if we prove the bound for unit norm vectors, then it will be straightforward to prove the bound for arbitrary vectors.

3. Let us assume without loss of generality that $\mathbf{x},{\mathbf{x}}^{\prime }$ are unit norm.

4. We need to show that

   $$|⟨\mathrm{\Phi }\mathbf{x},\mathrm{\Phi }{\mathbf{x}}^{\prime }⟩|\le {\delta }_{k+k^{\prime }}.$$

5. With the help of parallelogram identity (Theorem 4.93), we have

   $$⟨\mathrm{\Phi }\mathbf{x},\mathrm{\Phi }{\mathbf{x}}^{\prime }⟩=\frac{1}{4}(\Vert \mathrm{\Phi }\mathbf{x}+\mathrm{\Phi }{\mathbf{x}}^{\prime }{\Vert }_2^2-\Vert \mathrm{\Phi }\mathbf{x}-\mathrm{\Phi }{\mathbf{x}}^{\prime }{\Vert }_2^2).$$

6. Thus

   $$|⟨\mathrm{\Phi }\mathbf{x},\mathrm{\Phi }{\mathbf{x}}^{\prime }⟩|=\frac{1}{4}|\Vert \mathrm{\Phi }\mathbf{x}+\mathrm{\Phi }{\mathbf{x}}^{\prime }{\Vert }_2^2-\Vert \mathrm{\Phi }\mathbf{x}-\mathrm{\Phi }{\mathbf{x}}^{\prime }{\Vert }_2^2|.$$

7. Now

   $$\Vert \mathbf{x}\pm {\mathbf{x}}^{\prime }{\Vert }_2^2=\Vert \mathbf{x}{\Vert }_2^2+\Vert {\mathbf{x}}^{\prime }{\Vert }_2^2\pm 2⟨\mathbf{x},{\mathbf{x}}^{\prime }⟩=\Vert \mathbf{x}{\Vert }_2^2+\Vert {\mathbf{x}}^{\prime }{\Vert }_2^2=2$$

   since $\mathbf{x},{\mathbf{x}}^{\prime }$ are orthogonal and unit norm.

8. Using Theorem 18.48 we have

   $$\begin{array}{rl}& (1-{\delta }_{k+k^{\prime }})\Vert \mathbf{x}\pm {\mathbf{x}}^{\prime }{\Vert }_2^2\le \Vert \mathrm{\Phi }\mathbf{x}\pm \mathrm{\Phi }{\mathbf{x}}^{\prime }{\Vert }_2^2\le (1+{\delta }_{k+k^{\prime }})\Vert \mathbf{x}\pm {\mathbf{x}}^{\prime }{\Vert }_2^2\\ ⟹& 2(1-{\delta }_{k+k^{\prime }})\le \Vert \mathrm{\Phi }\mathbf{x}\pm \mathrm{\Phi }{\mathbf{x}}^{\prime }{\Vert }_2^2\le 2(1+{\delta }_{k+k^{\prime }}).\end{array}$$

9. Hence the maximum value of $\Vert \mathrm{\Phi }\mathbf{x}\pm \mathrm{\Phi }{\mathbf{x}}^{\prime }{\Vert }_2^2$ can be $2(1+{\delta }_{k+k^{\prime }})$ while the minimum value of $\Vert \mathrm{\Phi }\mathbf{x}\pm \mathrm{\Phi }{\mathbf{x}}^{\prime }{\Vert }_2^2$ can be $2(1-{\delta }_{k+k^{\prime }})$.

10. This gives us the upper bound

    $$|⟨\mathrm{\Phi }\mathbf{x},\mathrm{\Phi }{\mathbf{x}}^{\prime }⟩|\le \frac{1}{4}(2(1+{\delta }_{k+k^{\prime }})-2(1-{\delta }_{k+k^{\prime }}))={\delta }_{k+k^{\prime }}.$$

11. Finally when $\mathbf{x},{\mathbf{x}}^{\prime }$ are not unit norm, the bound generalizes to

    $$|⟨\mathrm{\Phi }\mathbf{x},\mathrm{\Phi }{\mathbf{x}}^{\prime }⟩|\le {\delta }_{k+k^{\prime }}\Vert \mathbf{x}{\Vert }_2\Vert {\mathbf{x}}^{\prime }{\Vert }_2.$$

A variation of this result is presented below:

Theorem 18.64

Assume that the sensing matrix $\mathrm{\Phi }\in {\mathbb{R}}^{M\times N}$. Let $\mathbf{u},\mathbf{v}\in {\mathbb{R}}^N$ be given and let

$$K=max(\Vert \mathbf{u}+\mathbf{v}{\Vert }_0,\Vert \mathbf{u}-\mathbf{v}{\Vert }_0).$$

Let $\mathrm{\Phi }$ satisfy RIP of order $K$ with the constant ${\delta }_K$. Then

$$|⟨\mathrm{\Phi }\mathbf{u},\mathrm{\Phi }\mathbf{v}⟩-⟨\mathbf{u},\mathbf{v}⟩|\le {\delta }_K\Vert \mathbf{u}{\Vert }_2\Vert \mathbf{v}{\Vert }_2.$$

This result is more general as it doesn’t require $\mathbf{u},\mathbf{v}$ to be supported on disjoint index sets. All it requires is them to be sufficiently sparse.

Proof. As, in the previous result, it is sufficient to prove it for the case where $\Vert \mathbf{u}{\Vert }_2=\Vert \mathbf{v}{\Vert }_2=1$. The simplified inequality becomes

$$|⟨\mathrm{\Phi }\mathbf{u},\mathrm{\Phi }\mathbf{v}⟩-⟨\mathbf{u},\mathbf{v}⟩|\le {\delta }_K.$$

1. Clearly

   $$\Vert \mathbf{u}\pm \mathbf{v}{\Vert }_2^2=\Vert \mathbf{u}{\Vert }_2^2+\Vert \mathbf{v}{\Vert }_2^2\pm 2⟨\mathbf{u},\mathbf{v}⟩=2\pm 2⟨\mathbf{u},\mathbf{v}⟩.$$

2. Due to RIP, we have

   $$(1-{\delta }_K)(2\pm 2⟨\mathbf{u},\mathbf{v}⟩)\le \Vert \mathrm{\Phi }(\mathbf{u}\pm \mathbf{v}){\Vert }_2^2\le (1+{\delta }_K)(2\pm 2⟨\mathbf{u},\mathbf{v}⟩).$$

3. From the parallelogram identity, we have

   (18.49)$$⟨\mathrm{\Phi }\mathbf{u},\mathrm{\Phi }\mathbf{v}⟩=\frac{1}{4}(\Vert \mathrm{\Phi }(\mathbf{u}+\mathbf{v}){\Vert }_2^2-\Vert \mathrm{\Phi }(\mathbf{u}-\mathbf{v}){\Vert }_2^2).$$

4. Taking the upper bound on $\Vert \mathrm{\Phi }(\mathbf{u}+\mathbf{v}){\Vert }_2^2$ and the lower bound on $\Vert \mathrm{\Phi }(\mathbf{u}-\mathbf{v}){\Vert }_2^2$ in (18.49), we obtain

   $$⟨\mathrm{\Phi }\mathbf{u},\mathrm{\Phi }\mathbf{v}⟩\le \frac{1}{2}((1+{\delta }_K)(1+⟨\mathbf{u},\mathbf{v}⟩)-(1-{\delta }_K)(1-⟨\mathbf{u},\mathbf{v}⟩)).$$

5. Simplifying, we get

   $$⟨\mathrm{\Phi }\mathbf{u},\mathrm{\Phi }\mathbf{v}⟩\le ⟨\mathbf{u},\mathbf{v}⟩+{\delta }_K.$$

6. At the same time, taking the lower bound on $\Vert \mathrm{\Phi }(\mathbf{u}+\mathbf{v}){\Vert }_2^2$ and the upper bound on $\Vert \mathrm{\Phi }(\mathbf{u}-\mathbf{v}){\Vert }_2^2$ in (18.49), we obtain

   $$⟨\mathrm{\Phi }\mathbf{u},\mathrm{\Phi }\mathbf{v}⟩\ge \frac{1}{2}((1-{\delta }_K)(1+⟨\mathbf{u},\mathbf{v}⟩)-(1+{\delta }_K)(1-⟨\mathbf{u},\mathbf{v}⟩)).$$

7. Simplifying, we get

   $$⟨\mathrm{\Phi }\mathbf{u},\mathrm{\Phi }\mathbf{v}⟩\ge ⟨\mathbf{u},\mathbf{v}⟩-{\delta }_K.$$

8. Combining the two results, we obtain

   $$|⟨\mathrm{\Phi }\mathbf{u},\mathrm{\Phi }\mathbf{v}⟩-⟨\mathbf{u},\mathbf{v}⟩|\le {\delta }_K.$$

For the complex case, the result can be generalized if we choose a bilinear inner product rather than the usual sesquilinear inner product.

Theorem 18.65

Let $\mathbf{u},\mathbf{v}\in {\mathbb{C}}^N$ be given and let

$$K=max(\Vert \mathbf{u}+\mathbf{v}{\Vert }_0,\Vert \mathbf{u}-\mathbf{v}{\Vert }_0).$$

Let the complex space ${\mathbb{C}}^N$ be equipped with the bilinear inner product

$$⟨\mathbf{u},\mathbf{v}{⟩}_B\triangleq \mathrm{Re}(⟨\mathbf{u},\mathbf{v}⟩)$$

i.e. the real part of the standard inner product.

Let $\mathrm{\Phi }$ satisfy RIP of order $K$ with the constant ${\delta }_K$. Then

$$|⟨\mathrm{\Phi }\mathbf{u},\mathrm{\Phi }\mathbf{v}{⟩}_B-⟨\mathbf{u},\mathbf{v}{⟩}_B|\le {\delta }_K\Vert \mathbf{u}{\Vert }_2\Vert \mathbf{v}{\Vert }_2.$$

Proof. Recall that the norm induced by the bilinear inner product $⟨\mathbf{u},\mathbf{v}{⟩}_B$ is the usual ${\ell }_2$ norm since

$$⟨\mathbf{u},\mathbf{u}{⟩}_B=\mathrm{Re}(⟨\mathbf{u},\mathbf{u}⟩)=\mathrm{Re}(\Vert \mathbf{u}{\Vert }_2^2)=\Vert \mathbf{u}{\Vert }_2^2.$$

1. Let us just work out the parallelogram identity for the complex case

   $$\begin{array}{rl}\Vert \mathbf{x}\pm \mathbf{y}{\Vert }_2^2& =⟨\mathbf{x}\pm \mathbf{y},\mathbf{x}\pm \mathbf{y}{⟩}_B\\ & =⟨\mathbf{x},\mathbf{x}{⟩}_B+⟨\mathbf{y},\mathbf{y}{⟩}_B\pm ⟨\mathbf{x},\mathbf{y}{⟩}_B\pm ⟨\mathbf{y},\mathbf{x}{⟩}_B\\ & =⟨\mathbf{x},\mathbf{x}{⟩}_B+⟨\mathbf{y},\mathbf{y}{⟩}_B\pm 2⟨\mathbf{x},\mathbf{y}{⟩}_B\end{array}$$

   due to the bilinearity of the real inner product.

2. We can see that the rest of the proof is identical to the proof of Theorem 18.64.

18.8.9. RIP and Orthogonal Projection

The first result in this section is presented for real matrices. The generalization for complex matrices will be done later.

1. Let $\mathrm{\Lambda }\subset \{1,\dots ,N\}$ be an index set.

2. Let $\mathrm{\Phi }\in {\mathbb{R}}^{M\times N}$ satisfy RIP of order $K$ with the restricted isometry constant ${\delta }_K$.

3. Assume that the columns of ${\mathrm{\Phi }}_{\mathrm{\Lambda }}$ are linearly independent.

4. We can define the pseudo inverse as

   $${\mathrm{\Phi }}_{\mathrm{\Lambda }}^{†}={\left({\mathrm{\Phi }}_{\mathrm{\Lambda }}^H{\mathrm{\Phi }}_{\mathrm{\Lambda }}\right)}^{-1}{\mathrm{\Phi }}_{\mathrm{\Lambda }}^H.$$

5. The orthogonal projection operator to the column space for ${\mathrm{\Phi }}_{\mathrm{\Lambda }}$ is given by

   $${\mathbf{P}}_{\mathrm{\Lambda }}={\mathrm{\Phi }}_{\mathrm{\Lambda }}{\mathrm{\Phi }}_{\mathrm{\Lambda }}^{†}.$$

6. The orthogonal projection operator onto the orthogonal complement of $\mathcal{C}({\mathrm{\Phi }}_{\mathrm{\Lambda }})$ (column space of ${\mathrm{\Phi }}_{\mathrm{\Lambda }}$) is given by

   $${\mathbf{P}}_{\mathrm{\Lambda }}^{\perp }=\mathbf{I}-{\mathbf{P}}_{\mathrm{\Lambda }}.$$

7. Both ${\mathbf{P}}_{\mathrm{\Lambda }}$ and ${\mathbf{P}}_{\mathrm{\Lambda }}^{\perp }$ satisfy the usual properties like $\mathbf{P}={\mathbf{P}}^H$ and ${\mathbf{P}}^2=\mathbf{P}$.

We further define

$${\mathrm{\Psi }}_{\mathrm{\Lambda }}={\mathbf{P}}_{\mathrm{\Lambda }}^{\perp }\mathrm{\Phi }.$$

1. We are orthogonalizing the columns in $\mathrm{\Phi }$ against $\mathcal{C}({\mathrm{\Phi }}_{\mathrm{\Lambda }})$.

2. In other words, keeping the component of the column which is orthogonal to the column space of ${\mathrm{\Phi }}_{\mathrm{\Lambda }}$.

3. Obviously the columns in ${\mathrm{\Psi }}_{\mathrm{\Lambda }}$ corresponding to the index set $\mathrm{\Lambda }$ would be $\mathbf{0}$.

We now present a result which shows that the matrix ${\mathrm{\Psi }}_{\mathrm{\Lambda }}$ satisfies a modified version of RIP [25].

Theorem 18.66

If $\mathrm{\Phi }$ satisfies the RIP of order $K$ with isometry constant ${\delta }_K$, and $\mathrm{\Lambda }\subset \{1,\dots ,N\}$ with $|\mathrm{\Lambda }|<K$, then the matrix ${\mathrm{\Psi }}_{\mathrm{\Lambda }}$ satisfies the modified version of RIP as

(18.50)$$(1-\frac{{\delta }_K}{1-{\delta }_K})\Vert \mathbf{x}{\Vert }_2^2\le \Vert {\mathrm{\Psi }}_{\mathrm{\Lambda }}\mathbf{x}{\Vert }_2^2\le (1+{\delta }_K)\Vert \mathbf{x}{\Vert }_2^2$$

for all $\mathbf{x}\in {\mathbb{R}}^N$ such that $\Vert \mathbf{x}{\Vert }_0\le K-|\mathrm{\Lambda }|$ and $\mathrm{supp}(\mathbf{x})\cap \mathrm{\Lambda }=\varnothing$.

In words, if $\mathrm{\Phi }$ satisfies RIP of order $K$, then ${\mathrm{\Psi }}_{\mathrm{\Lambda }}$ acts as an approximate isometry on every $(K-|\mathrm{\Lambda }|)$-sparse vector supported on ${\mathrm{\Lambda }}^c$.

Proof. From the definition of ${\mathrm{\Psi }}_{\mathrm{\Lambda }}$, we have

$${\mathrm{\Psi }}_{\mathrm{\Lambda }}\mathbf{x}=(\mathbf{I}-{\mathbf{P}}_{\mathrm{\Lambda }})\mathrm{\Phi }\mathbf{x}=\mathrm{\Phi }\mathbf{x}-{\mathbf{P}}_{\mathrm{\Lambda }}\mathrm{\Phi }\mathbf{x}.$$

1. Alternatively

   $$\mathrm{\Phi }\mathbf{x}={\mathrm{\Psi }}_{\mathrm{\Lambda }}\mathbf{x}+{\mathbf{P}}_{\mathrm{\Lambda }}\mathrm{\Phi }\mathbf{x}.$$

2. Since ${\mathbf{P}}_{\mathrm{\Lambda }}$ is an orthogonal projection, hence the vectors ${\mathbf{P}}_{\mathrm{\Lambda }}\mathrm{\Phi }\mathbf{x}$ and ${\mathrm{\Psi }}_{\mathrm{\Lambda }}\mathbf{x}={\mathbf{P}}_{\mathrm{\Lambda }}^{\perp }\mathrm{\Phi }\mathbf{x}$ are orthogonal.

3. Thus, we can write

   (18.51)$$\Vert \mathrm{\Phi }\mathbf{x}{\Vert }_2^2=\Vert {\mathbf{P}}_{\mathrm{\Lambda }}\mathrm{\Phi }\mathbf{x}{\Vert }_2^2+\Vert {\mathrm{\Psi }}_{\mathrm{\Lambda }}\mathbf{x}{\Vert }_2^2.$$

4. We need to show that $\Vert \mathrm{\Phi }\mathbf{x}{\Vert }_2\approx \Vert {\mathrm{\Psi }}_{\mathrm{\Lambda }}\mathbf{x}{\Vert }_2$ or alternatively that $\Vert {\mathbf{P}}_{\mathrm{\Lambda }}\mathrm{\Phi }\mathbf{x}{\Vert }_2$ is small under the conditions of the theorem.

5. Since $P_{\mathrm{\Lambda }}\mathrm{\Phi }\mathbf{x}$ is orthogonal to ${\mathrm{\Psi }}_{\mathrm{\Lambda }}\mathbf{x}$, hence

   (18.52)$$\begin{array}{rl}⟨{\mathbf{P}}_{\mathrm{\Lambda }}\mathrm{\Phi }\mathbf{x},\mathrm{\Phi }\mathbf{x}⟩& =⟨{\mathbf{P}}_{\mathrm{\Lambda }}\mathrm{\Phi }\mathbf{x},{\mathrm{\Psi }}_{\mathrm{\Lambda }}\mathbf{x}+{\mathbf{P}}_{\mathrm{\Lambda }}\mathrm{\Phi }\mathbf{x}⟩\\ & =⟨{\mathbf{P}}_{\mathrm{\Lambda }}\mathrm{\Phi }\mathbf{x},{\mathbf{P}}_{\mathrm{\Lambda }}\mathrm{\Phi }\mathbf{x}⟩+⟨{\mathbf{P}}_{\mathrm{\Lambda }}\mathrm{\Phi }\mathbf{x},{\mathrm{\Psi }}_{\mathrm{\Lambda }}\mathbf{x}⟩\\ & =⟨{\mathbf{P}}_{\mathrm{\Lambda }}\mathrm{\Phi }\mathbf{x},{\mathbf{P}}_{\mathrm{\Lambda }}\mathrm{\Phi }\mathbf{x}⟩\\ & =\Vert {\mathbf{P}}_{\mathrm{\Lambda }}\mathrm{\Phi }\mathbf{x}{\Vert }_2^2.\end{array}$$

6. Since ${\mathbf{P}}_{\mathrm{\Lambda }}$ is a projection onto the $\mathcal{C}({\mathrm{\Phi }}_{\mathrm{\Lambda }})$ (column space of ${\mathrm{\Phi }}_{\mathrm{\Lambda }}$), there exists a vector $\mathbf{z}\in {\mathbb{C}}^N$, such that $P_{\mathrm{\Lambda }}\mathrm{\Phi }\mathbf{x}=\mathrm{\Phi }\mathbf{z}$ and $\mathrm{supp}(\mathbf{z})\subseteq \mathrm{\Lambda }$.

7. Since $\mathrm{supp}(\mathbf{x})\cap \mathrm{\Lambda }=\varnothing$, hence $⟨\mathbf{x},\mathbf{z}⟩=0$.

8. We also note that $\Vert \mathbf{x}+\mathbf{z}{\Vert }_0=\Vert \mathbf{x}-\mathbf{z}{\Vert }_0\le K$.

9. Invoking Theorem 18.64, we have

   $$|⟨\mathrm{\Phi }\mathbf{z},\mathrm{\Phi }\mathbf{x}⟩|\le {\delta }_K\Vert \mathbf{z}{\Vert }_2\Vert \mathbf{x}{\Vert }_2.$$

10. Alternatively

    $$|⟨{\mathbf{P}}_{\mathrm{\Lambda }}\mathrm{\Phi }\mathbf{x},\mathrm{\Phi }\mathbf{x}⟩|\le {\delta }_K\Vert \mathbf{z}{\Vert }_2\Vert \mathbf{x}{\Vert }_2.$$

11. From RIP, we have

    $$\sqrt{1-{\delta }_K}\Vert \mathbf{z}{\Vert }_2\le \Vert \mathrm{\Phi }\mathbf{z}{\Vert }_2$$

    and

    $$\sqrt{1-{\delta }_K}\Vert \mathbf{x}{\Vert }_2\le \Vert \mathrm{\Phi }\mathbf{x}{\Vert }_2.$$

12. Thus

    $$(1-{\delta }_K)\Vert \mathbf{z}{\Vert }_2\Vert \mathbf{x}{\Vert }_2\le \Vert \mathrm{\Phi }\mathbf{z}{\Vert }_2\Vert \mathrm{\Phi }\mathbf{x}{\Vert }_2.$$

13. This gives us

    $$|⟨{\mathbf{P}}_{\mathrm{\Lambda }}\mathrm{\Phi }\mathbf{x},\mathrm{\Phi }\mathbf{x}⟩|\le \frac{{\delta }_K}{1-{\delta }_K}\Vert P_{\mathrm{\Lambda }}\mathrm{\Phi }\mathbf{x}{\Vert }_2\Vert \mathrm{\Phi }\mathbf{x}{\Vert }_2.$$

14. Applying (18.52), we get

    $$\Vert {\mathbf{P}}_{\mathrm{\Lambda }}\mathrm{\Phi }\mathbf{x}{\Vert }_2^2\le \frac{{\delta }_K}{1-{\delta }_K}\Vert {\mathbf{P}}_{\mathrm{\Lambda }}\mathrm{\Phi }\mathbf{x}{\Vert }_2\Vert \mathrm{\Phi }\mathbf{x}{\Vert }_2.$$

15. Canceling the common term, we get

    $$\Vert {\mathbf{P}}_{\mathrm{\Lambda }}\mathrm{\Phi }\mathbf{x}{\Vert }_2\le \frac{{\delta }_K}{1-{\delta }_K}\Vert \mathrm{\Phi }\mathbf{x}{\Vert }_2.$$

16. Trivially, we have $\Vert {\mathbf{P}}_{\mathrm{\Lambda }}\mathrm{\Phi }\mathbf{x}{\Vert }_2\ge 0$.

17. Applying these bounds on (18.51), we obtain

    $$(1-{\left(\frac{{\delta }_K}{1-{\delta }_K}\right)}^2)\Vert \mathrm{\Phi }\mathbf{x}{\Vert }_2^2\le \Vert {\mathrm{\Psi }}_{\mathrm{\Lambda }}\mathbf{x}{\Vert }_2^2\le \Vert \mathrm{\Phi }\mathbf{x}{\Vert }_2^2.$$

18. Finally, using the RIP again with

    $$(1-{\delta }_K)\Vert \mathbf{x}{\Vert }_2^2\le \Vert \mathrm{\Phi }\mathbf{x}{\Vert }_2^2\le (1+{\delta }_K)\Vert \mathbf{x}{\Vert }_2^2$$

    we obtain

    $$(1-{\left(\frac{{\delta }_K}{1-{\delta }_K}\right)}^2)(1-{\delta }_K)\Vert \mathbf{x}{\Vert }_2^2\le \Vert {\mathrm{\Psi }}_{\mathrm{\Lambda }}\mathbf{x}{\Vert }_2^2\le (1+{\delta }_K)\Vert \mathbf{x}{\Vert }_2^2.$$

19. Simplifying

    $$\begin{array}{rl}(1-{\left(\frac{{\delta }_K}{1-{\delta }_K}\right)}^2)(1-{\delta }_K)& =\frac{1+{\delta }_K^2-2{\delta }_K-{\delta }_K^2}{1-{\delta }_K}\\ & =\frac{1-2{\delta }_K}{1-{\delta }_K}\\ & =1-\frac{{\delta }_K}{1-{\delta }_K}.\end{array}$$

20. Thus, we get the intended result in (18.50).

18.8.10. RIP for Higher Orders

If $\mathrm{\Phi }$ satisfies RIP of order $K$, does it satisfy RIP of some other order $K^{\prime }>K$? There are some results available to answer this question.

Theorem 18.67

Let $c$ and $k$ be integers and let $\mathrm{\Phi }$ satisfy RIP of order $2k$. $\mathrm{\Phi }$ satisfies RIP of order $ck$ with a restricted isometry constant

$${\delta }_{ck}\le c{\delta }_{2k}$$

if $c{\delta }_{2k}<1$.

Note that this is only a sufficient condition. Thus if $c{\delta }_{2k}\ge 1$ we are not claiming whether $\mathrm{\Phi }$ satisfies RIP of order $ck$ or not.

Proof. For $c=1$, ${\delta }_k\le {\delta }_{2k}$. For $c=2$, ${\delta }_{2k}\le 2{\delta }_{2k}$. These two cases are trivial. We now consider the case for $c\ge 3$.

1. Let $S$ be an arbitrary index set of size $ck$. Let

   $$\mathrm{\Delta }={\mathrm{\Phi }}_S^H{\mathrm{\Phi }}_S-\mathbf{I}.$$

2. From Theorem 18.54, a sufficient condition for $\mathrm{\Phi }$ to satisfy RIP of order $ck$ is that

   $$\Vert \mathrm{\Delta }{\Vert }_2<1$$

   for all index sets $S$ with $|S|=ck$.

3. Thus if we can show that

   $$\Vert \mathrm{\Delta }{\Vert }_2\le c{\delta }_{2k}$$

   we would have shown that $\mathrm{\Phi }$ satisfies RIP of order $ck$.

4. We note that ${\mathrm{\Phi }}_S$ is of size $M\times ck$.

5. Thus $\mathrm{\Delta }$ is of size $ck\times ck$.

6. We partition $\mathrm{\Delta }$ into a block matrix of size $c\times c$

   $$\begin{array}{r}\mathrm{\Delta }=\left[\begin{array}{cccc}{\mathrm{\Delta }}_{11}& {\mathrm{\Delta }}_{12}& \dots & {\mathrm{\Delta }}_{1c}\\ {\mathrm{\Delta }}_{21}& {\mathrm{\Delta }}_{22}& \dots & {\mathrm{\Delta }}_{2c}\\ ⋮& ⋮& \ddots & ⋮\\ {\mathrm{\Delta }}_{c1}& {\mathrm{\Delta }}_{c2}& \dots & {\mathrm{\Delta }}_{cc}\end{array}\right]\end{array}$$

   where each entry ${\mathrm{\Delta }}_{ij}$ is a square matrix of size $k\times k$.

7. Each diagonal matrix ${\mathrm{\Delta }}_{ii}$ corresponds to some ${\mathrm{\Phi }}_T^H{\mathrm{\Phi }}_T-\mathbf{I}$ where $|T|=k$.

8. Thus we have (see Theorem 18.53)

   $$\Vert {\mathrm{\Delta }}_{ii}{\Vert }_2\le {\delta }_k.$$

9. The off-diagonal matrices ${\mathrm{\Delta }}_{ij}$ are

   $${\mathrm{\Delta }}_{ij}={\mathrm{\Phi }}_P^H{\mathrm{\Phi }}_Q$$

   where $P$ and $Q$ are disjoint index sets with $|P|=|Q|=k$ with $|P\cup Q|=2k$.

10. Thus from the approximate orthogonality condition (Theorem 18.61 ) we have

    $$\Vert {\mathrm{\Delta }}_{ij}{\Vert }_2\le {\delta }_{2k}.$$

11. Finally we apply Gershgorin circle theorem for block matrices (Corollary 4.29).

12. This gives us

    $$|\Vert \mathrm{\Delta }{\Vert }_2-\Vert {\mathrm{\Delta }}_{ii}{\Vert }_2|\le \sum _{j,j\ne i}\Vert {\mathrm{\Delta }}_{ij}\Vert \text{ for some }i\in \{1,2,\dots ,c\}.$$

13. Thus we have

    $$\begin{array}{rl}& |\Vert \mathrm{\Delta }{\Vert }_2-{\delta }_k|\le \sum _{j,j\ne i}{\delta }_{2k}\\ ⟹& |\Vert \mathrm{\Delta }{\Vert }_2-{\delta }_k|\le (c-1){\delta }_{2k}\\ ⟹& \Vert \mathrm{\Delta }{\Vert }_2\le {\delta }_k+(c-1){\delta }_{2k}\\ ⟹& \Vert \mathrm{\Delta }{\Vert }_2\le {\delta }_{2k}+(c-1){\delta }_{2k}\\ ⟹& \Vert \mathrm{\Delta }{\Vert }_2\le c{\delta }_{2k}.\end{array}$$

14. We have shown that $\Vert \mathrm{\Delta }{\Vert }_2\le c{\delta }_{2k}<1$.

15. Thus ${\delta }_{ck}\le \Vert \mathrm{\Delta }{\Vert }_2$.

16. Hence $\mathrm{\Phi }$ indeed satisfies RIP of order $ck$.

This theorem helps us extend RIP from an order $K$ to higher orders. If ${\delta }_{2k}$ isn’t sufficiently small, the bound isn’t useful.

18.8.11. Embeddings of Arbitrary Signals

So far we have considered only sparse signals while analyzing the embedding properties of a RIP satisfying matrix $\mathrm{\Phi }$. In this subsection we wish to explore bounds on the ${\ell }_2$ norm of an arbitrary signal when embedded by $\mathrm{\Phi }$. This result is adapted from [61].

Theorem 18.68

Let $\mathrm{\Phi }$ be an an $M\times N$ matrix satisfying

(18.53)$$\Vert \mathrm{\Phi }\mathbf{x}{\Vert }_2\le \sqrt{1+{\delta }_K}\Vert \mathbf{x}{\Vert }_2\mathrm{\forall }\mathbf{x}\in {\mathrm{\Sigma }}_K.$$

Then for every signal $\mathbf{x}\in {\mathbb{C}}^N$, the following holds:

$$\Vert \mathrm{\Phi }\mathbf{x}{\Vert }_2\le \sqrt{1+{\delta }_K}[\Vert \mathbf{x}{\Vert }_2+\frac{1}{\sqrt{K}}\Vert \mathbf{x}{\Vert }_1].$$

We note that the theorem requires $\mathrm{\Phi }$ to satisfy only the upper bound of RIP property (18.43). The proof is slightly involved.

Proof. We note that the bound is trivially true for $\mathbf{x}=\mathbf{0}$. Hence in the following we will consider only for $\mathbf{x}\ne \mathbf{0}$.

1. Consider an arbitrary index set $\mathrm{\Lambda }\subset \{1,2,\dots ,N\}$ such that $|\mathrm{\Lambda }|\le K$.

2. Consider the unit ball in the Banach space ${\ell }_2(\mathrm{\Lambda })$ given by

   (18.54)$$B_2^{\mathrm{\Lambda }}=\{\mathbf{x}\in {\mathbb{C}}^N|\mathrm{supp}(\mathbf{x})=\mathrm{\Lambda }\text{ and }\Vert \mathbf{x}{\Vert }_2\le 1\}$$

   i.e. the set of all signals whose support is $\mathrm{\Lambda }$ and whose ${\ell }_2$ norm is less than or equal to 1.

3. Now define a convex body

   (18.55)$$S=\mathrm{conv}\left\{\bigcup _{|\mathrm{\Lambda }|\le K}{B}_2^{\mathrm{\Lambda }}\right\}\subset {\mathbb{C}}^N.$$

4. We recall from Definition 9.9 that if $\mathbf{x}$ and $\mathbf{y}$ belong to $S$ then their convex combination $\theta \mathbf{x}+(1-\theta )\mathbf{y}$ with $\theta \in [0,1]$ must lie in $S$.

5. Further it can be verified that $S$ is a compact convex set with non-empty interior.

6. Hence it is a convex body.

7. Consider any $\mathbf{x}\in B_2^{{\mathrm{\Lambda }}_1}$ and $\mathbf{y}\in B_2^{{\mathrm{\Lambda }}_2}$.

8. From (18.53) and (18.54) we have

   $$\Vert \mathrm{\Phi }\mathbf{x}{\Vert }_2\le \sqrt{1+{\delta }_K}\Vert \mathbf{x}{\Vert }_2\le \sqrt{1+{\delta }_K}$$

   and

   $$\Vert \mathrm{\Phi }\mathbf{y}{\Vert }_2\le \sqrt{1+{\delta }_K}\Vert \mathbf{y}{\Vert }_2\le \sqrt{1+{\delta }_K}.$$

9. Now let

   $$\mathbf{z}=\theta \mathbf{x}+(1-\theta )\mathbf{y}\text{ where }\theta \in [0,1].$$

10. Then

    $$\Vert \mathbf{z}{\Vert }_2=\Vert \theta \mathbf{x}+(1-\theta )\mathbf{y}{\Vert }_2\le \theta \Vert \mathbf{x}{\Vert }_2+(1-\theta )\Vert \mathbf{y}{\Vert }_2\le \theta +(1-\theta )=1.$$

11. Further

    $$\begin{array}{rl}\Vert \mathrm{\Phi }\mathbf{z}{\Vert }_2& =\Vert \mathrm{\Phi }(\theta \mathbf{x}+(1-\theta )\mathbf{y}){\Vert }_2\\ & \le \Vert \mathrm{\Phi }\theta \mathbf{x}{\Vert }_2+\Vert \mathrm{\Phi }(1-\theta )\mathbf{y}{\Vert }_2\\ & =\theta \Vert \mathrm{\Phi }\mathbf{x}{\Vert }_2+(1-\theta )\Vert \mathrm{\Phi }\mathbf{y}{\Vert }_2\\ & \le \theta \sqrt{1+{\delta }_K}+(1-\theta )\sqrt{1+{\delta }_K}\\ & \le \sqrt{1+{\delta }_K}.\end{array}$$

12. Similarly, it can be shown that for every vector $\mathbf{x}\in S$ we have $\Vert \mathbf{x}{\Vert }_2\le 1$ and $\Vert \mathrm{\Phi }\mathbf{x}{\Vert }_2\le \sqrt{1+{\delta }_K}$.

    1. Let $\mathbf{x}\in S$.

    2. Then $\mathbf{x}=\sum _{i=1}^r{t}_i{\mathbf{x}}_i$ such that ${\mathbf{x}}_i\in B_2^{{\mathrm{\Lambda }}_i}$ where $|{\mathrm{\Lambda }}_i|\le K$, $t_i\ge 0$ and $\sum t_i=1$.

    3. Hence $\Vert {\mathbf{x}}_i{\Vert }_2\le 1$ for every $i$.

    4. Hence

       $$\Vert \mathbf{x}{\Vert }_2\le \sum _{i=1}^r{t}_i\Vert {\mathbf{x}}_i{\Vert }_2\le \sum _{i=1}^r{t}_i=1.$$

    5. Similarly $\Vert \mathrm{\Phi }{\mathbf{x}}_i{\Vert }_2\le \sqrt{1+{\delta }_K}$.

    6. Hence

       $$\Vert \mathrm{\Phi }\mathbf{x}{\Vert }_2\le \sum _{i=1}^r{t}_i\Vert \mathrm{\Phi }{\mathbf{x}}_i{\Vert }_2\le \sqrt{1+{\delta }_K}.$$

13. We now define another convex body

    (18.56)$$\mathrm{\Gamma }=\{\mathbf{x}|\Vert \mathbf{x}{\Vert }_2+\frac{1}{\sqrt{K}}\Vert \mathbf{x}{\Vert }_1\le 1\}\subset {\mathbb{C}}^N.$$

14. We quickly verify the convexity property.

    1. Let $\mathbf{x},\mathbf{y}\in \mathrm{\Gamma }$.

    2. Let

       $$\mathbf{z}=\theta \mathbf{x}+(1-\theta )\mathbf{y}\text{ where }\theta \in [0,1].$$

    3. Then

       $$\begin{array}{rl}& \Vert \mathbf{z}\Vert +\frac{1}{\sqrt{K}}\Vert \mathbf{z}{\Vert }_1\\ & =\Vert \theta \mathbf{x}+(1-\theta )\mathbf{y}{\Vert }_2+\frac{1}{\sqrt{K}}\Vert \theta \mathbf{x}+(1-\theta )\mathbf{y}{\Vert }_1\\ & \le \theta \Vert \mathbf{x}{\Vert }_2+(1-\theta )\Vert \mathbf{y}{\Vert }_2+\frac{\theta }{\sqrt{K}}\Vert \mathbf{x}{\Vert }_1+\frac{(1-\theta )}{\sqrt{K}}\Vert \mathbf{y}{\Vert }_1\\ & =\theta [\Vert \mathbf{x}{\Vert }_2+\frac{1}{\sqrt{K}}\Vert \mathbf{x}{\Vert }_1]+(1-\theta )[\Vert \mathbf{y}{\Vert }_2+\frac{1}{\sqrt{K}}\Vert \mathbf{y}{\Vert }_1]\\ & \le \theta +(1-\theta )=1.\end{array}$$

    4. Thus $\mathbf{z}\in \mathrm{\Gamma }$.

    5. This analysis shows that all convex combinations of elements in $\mathrm{\Gamma }$ belong to $\mathrm{\Gamma }$.

    6. Thus $\mathrm{\Gamma }$ is convex.

    7. Further it can be verified that $\mathrm{\Gamma }$ is a compact convex set with non-empty interior.

    8. Hence it is a convex body.

15. For any $\mathbf{x}\in {\mathbb{C}}^N$ one can find a $\mathbf{y}\in \mathrm{\Gamma }$ by simply applying an appropriate nonzero scale $\mathbf{y}=c\mathbf{x}$ where the scale factor $c$ depends on $\mathbf{x}$.

16. For a moment suppose that $\mathrm{\Gamma }\subset S$.

17. Then if $\mathbf{y}\in \mathrm{\Gamma }$ the following are true:

    $$\Vert \mathbf{y}{\Vert }_2+\frac{1}{\sqrt{K}}\Vert \mathbf{y}{\Vert }_1\le 1$$

    and

    $$\Vert \mathrm{\Phi }\mathbf{y}{\Vert }_2\le \sqrt{1+{\delta }_K}.$$

18. Now consider an arbitrary nonzero $\mathbf{x}\in {\mathbb{C}}^N$.

19. Let

    $$\alpha =\Vert \mathbf{x}{\Vert }_2+\frac{1}{\sqrt{K}}\Vert \mathbf{x}{\Vert }_1.$$

20. Define

    $$\mathbf{y}=\frac{1}{\alpha }\mathbf{x}.$$

21. Then

    $$\Vert \mathbf{y}{\Vert }_2+\frac{1}{\sqrt{K}}\Vert \mathbf{y}{\Vert }_1=\frac{1}{\alpha }(\Vert \mathbf{x}{\Vert }_2+\frac{1}{\sqrt{K}}\Vert \mathbf{x}{\Vert }_1)=1.$$

22. Thus $\mathbf{y}\in \mathrm{\Gamma }$ and

    $$\begin{array}{rl}& \Vert \mathrm{\Phi }\mathbf{y}{\Vert }_2\le \sqrt{1+{\delta }_K}\\ ⟹& {\Vert \mathrm{\Phi }\frac{1}{\alpha }\mathbf{x}\Vert }_2\le \sqrt{1+{\delta }_K}\\ ⟹& \Vert \mathrm{\Phi }\mathbf{x}{\Vert }_2\le \sqrt{1+{\delta }_K}\alpha \\ ⟹& \Vert \mathrm{\Phi }\mathbf{x}{\Vert }_2\le \sqrt{1+{\delta }_K}(\Vert \mathbf{x}{\Vert }_2+\frac{1}{\sqrt{K}}\Vert \mathbf{x}{\Vert }_1)\mathrm{\forall }\mathbf{x}\in {\mathbb{C}}^N\end{array}$$

    which is our intended result.

23. Hence if we show that $\mathrm{\Gamma }\subset S$ holds, we would have proven our theorem.

We will achieve this by showing that every vector $\mathbf{x}\in \mathrm{\Gamma }$ can be shown to be a convex combination of vectors in $S$.

1. We start with an arbitrary $\mathbf{x}\in \mathrm{\Gamma }$.

2. Let $I=\mathrm{supp}(\mathbf{x})$.

3. We partition $I$ into disjoint sets of size $K$.

4. Let there be $J+1$ such sets given by

   $$I=\bigcup _{j=0}^J{I}_j.$$

5. Let $I_0$ index the $K$ largest entries in $\mathbf{x}$ (magnitude wise).

6. Let $I_1$ be next $K$ largest entries and so on.

7. Since $|I|$ may not be a multiple of $K$, hence the last index set $I_J$ may not have $K$ indices.

8. We define

   $$\begin{array}{r}{\mathbf{x}}_{I_j}(i)=\{\begin{array}{ll}x(i)& \text{if }i\in I_j;\\ 0& \text{otherwise}.\end{array}\end{array}$$

9. Thus we can write

   $$\mathbf{x}=\sum _{j=0}^J{\mathbf{x}}_{I_j}.$$

10. Now let

    $${\theta }_j=\Vert {\mathbf{x}}_{I_j}{\Vert }_2\text{ and }{\mathbf{y}}_j=\frac{1}{{\theta }_j}{\mathbf{x}}_{I_j}.$$

11. We can write

    $$\mathbf{x}=\sum _{j=0}^J{\theta }_j{\mathbf{y}}_j.$$

12. In this construction of $\mathbf{x}$ we can see that $1\ge {\theta }_0\ge {\theta }_1\ge \cdots \ge {\theta }_J\ge 0$.

13. Also ${\mathbf{y}}_j\in S$ since ${\mathbf{y}}_j$ is a unit norm $K$ sparse vector (18.55).

14. We will show that $\sum _j{\theta }_j\le 1$ in a short while.

15. This will imply that $\mathbf{x}$ is a convex combination of vectors from $S$.

16. But since $S$ is convex hence $\mathbf{x}\in S$.

17. This will imply that $\mathrm{\Gamma }\subset S$.

18. The proof will be complete.

We now show that $\sum _j{\theta }_j\le 1$.

1. Pick any $j\in \{1,\dots ,J\}$.

2. Since ${\mathbf{x}}_{I_j}$ is $K$-sparse hence due to Theorem 18.17 we have

   $${\theta }_j=\Vert {\mathbf{x}}_{I_j}{\Vert }_2\le \sqrt{K}\Vert {\mathbf{x}}_{I_j}{\Vert }_{\mathrm{\infty }}.$$

3. It is easy to see that $I_{j-1}$ identifies exactly $K$ nonzero entries in $\mathbf{x}$ and each of nonzero entries in ${\mathbf{x}}_{I_{j-1}}$ is larger than the largest entry in ${\mathbf{x}}_{I_j}$ (magnitude wise).

4. Thus we have

   $$\Vert {\mathbf{x}}_{I_{j-1}}{\Vert }_1=\sum _{i\in I_{j-1}}|x_i|\ge \sum _{i\in I_{j-1}}\Vert {\mathbf{x}}_{I_j}{\Vert }_{\mathrm{\infty }}=K\Vert {\mathbf{x}}_{I_j}{\Vert }_{\mathrm{\infty }}.$$

5. Thus

   $$\Vert {\mathbf{x}}_{I_j}{\Vert }_{\mathrm{\infty }}\le \frac{1}{K}\Vert {\mathbf{x}}_{I_{j-1}}{\Vert }_1.$$

6. Combining the two inequalities we get

   $${\theta }_j\le \frac{1}{\sqrt{K}}\Vert {\mathbf{x}}_{I_{j-1}}{\Vert }_1.$$

7. This lets us write

   $$\sum _{j=1}^J{\theta }_j\le \sum _{j=1}^J\frac{1}{\sqrt{K}}\Vert {\mathbf{x}}_{I_{j-1}}{\Vert }_1\le \frac{1}{\sqrt{K}}\Vert \mathbf{x}{\Vert }_1$$

   since

   $$\Vert \mathbf{x}{\Vert }_1=\sum _{j=0}^J\Vert {\mathbf{x}}_{I_j}{\Vert }_1\ge \sum _{j=1}^J\Vert {\mathbf{x}}_{I_{j-1}}{\Vert }_1.$$

8. Finally

   $${\theta }_0=\Vert {\mathbf{x}}_{I_0}{\Vert }_2\le \Vert \mathbf{x}{\Vert }_2.$$

9. This gives us the inequality

   $$\sum _{j=0}^J{\theta }_j\le \Vert \mathbf{x}{\Vert }_2+\frac{1}{\sqrt{K}}\Vert \mathbf{x}{\Vert }_1\le 1$$

   since $\mathbf{x}\in \mathrm{\Gamma }$.

10. Recalling our steps we can express $\mathbf{x}$ as

    $$\mathbf{x}={\theta }_j{\mathbf{y}}_j$$

    where ${\mathbf{y}}_j\in S$ and $\sum {\theta }_j\le 1$ implies that $\mathbf{x}\in S$ since $S$ is convex.

11. Thus $\mathrm{\Gamma }\subset S$.

12. This completes the proof.

18.8.12. A General Form of RIP

A more general restricted isometry bound can be for an arbitrary matrix $\mathrm{\Phi }$ can be as follows

$$\alpha \Vert \mathbf{x}{\Vert }_2^2\le \Vert \mathrm{\Phi }\mathbf{x}{\Vert }_2^2\le \beta \Vert \mathbf{x}{\Vert }_2^2$$

where $0<\alpha \le \beta <\mathrm{\infty }$.

It is straightforward to scale $\mathrm{\Phi }$ to match the bounds in (18.43).

Let ${\delta }_K=\frac{\beta -\alpha }{\alpha +\beta }$. Then $1-{\delta }_K=\frac{2\alpha }{\alpha +\beta }$ and $1+{\delta }_K=\frac{2\beta }{\alpha +\beta }$.

Putting in (18.43) we get

$$\begin{array}{rl}& \frac{2\alpha }{\alpha +\beta }\Vert \mathbf{x}{\Vert }_2^2\le \Vert \mathrm{\Phi }\mathbf{x}{\Vert }_2^2\le \frac{2\beta }{\alpha +\beta }\Vert \mathbf{x}{\Vert }_2^2\\ ⟹& \alpha \Vert \mathbf{x}{\Vert }_2^2\le \Vert \sqrt{\frac{\alpha +\beta }{2}}\mathrm{\Phi }\mathbf{x}{\Vert }_2^2\le \beta \Vert \mathbf{x}{\Vert }_2^2.\end{array}$$

Thus by multiplying $\mathrm{\Phi }$ with $\sqrt{2/(\alpha +\beta )}$ we can transform the more general bound to the form of (18.43).

18.8.13. Finding out RIP Constants

The optimal value of RIP constant of $K$-th order ${\delta }_K$ can be obtained by solving the following optimization problem.

Algorithm 18.2

$$\begin{array}{rlrl}& \underset{0<\delta <1}{\text{minimize}}& & \delta \\ & \text{subject to }& & (1-\delta )\Vert \mathbf{x}{\Vert }_2^2\le \Vert \mathrm{\Phi }\mathbf{x}{\Vert }_2^2\le (1+\delta )\Vert \mathbf{x}{\Vert }_2^2\mathrm{\forall }\mathbf{x}\in {\mathrm{\Sigma }}_K.\end{array}$$

This problem isn’t easy to solve. In fact it has been shown in [4] that this problem is NP-hard.

18.8.14. RIP and Coherence

Here we establish a relationship between the RIP constants and coherence of a dictionary.

Rather than a general matrix $\mathrm{\Phi }$, we restrict our attention to a dictionary $\mathcal{D}\in {\mathbb{C}}^{N\times D}$ We assume that the dictionary is overcomplete $(D>N)$ and full rank $\mathrm{rank}(\mathcal{D})=N$. Dictionary is assumed to satisfy RIP of some order.

Theorem 18.69 (Coherence upper bound for RIP constant)

Let $\mathcal{D}$ satisfy RIP of order $K$. Then

$${\delta }_K\le (K-1)\mu (\mathcal{D}).$$

Proof. We recall that ${\delta }_K$ is the smallest constant $\delta$ satisfying

$$(1-\delta )\Vert \mathbf{x}{\Vert }_2^2\le \Vert \mathcal{D}\mathbf{x}{\Vert }_2^2\le (1+\delta )\Vert \mathbf{x}{\Vert }_2^2\mathrm{\forall }\mathbf{x}\in {\mathrm{\Sigma }}_K.$$

1. Let $\mathrm{\Lambda }$ be any index set with $|\mathrm{\Lambda }|=K$.

2. Then

   $$\Vert \mathcal{D}\mathbf{x}{\Vert }_2^2=\Vert {\mathcal{D}}_{\mathrm{\Lambda }}{\mathbf{x}}_{\mathrm{\Lambda }}{\Vert }_2^2\mathrm{\forall }\mathbf{x}\in {\mathbb{C}}^{\mathrm{\Lambda }}.$$

3. Since $\mathcal{D}$ satisfies RIP of order $K$, hence ${\mathcal{D}}_{\mathrm{\Lambda }}$ is a subdictionary (its columns are linearly independent).

4. Recall from Theorem 18.30 that

   $$(1-(K-1)\mu )\Vert \mathbf{v}{\Vert }_2^2\le \Vert {\mathcal{D}}_{\mathrm{\Lambda }}\mathbf{v}{\Vert }_2^2\le (1+(K-1)\mu )\Vert \mathbf{v}{\Vert }_2^2$$

   holds true for every $\mathbf{v}\in {\mathbb{C}}^K$.

5. Since ${\delta }_K$ is smallest possible constant, hence

   $$1+{\delta }_K\le 1+(K-1)\mu ⟹{\delta }_K\le (K-1)\mu (\mathcal{D}).$$