The RIP and the NSP

RIP and NSP are connected. If a matrix \(\Phi\) satisfies RIP then it also satisfies NSP (under certain conditions).

Thus RIP is strictly stronger than NSP (under certain conditions).

We will need following lemma which applies to any arbitrary \(h \in \RR^N\) . The lemma will be proved later.

Lemma

Suppose that \(\Phi\) satisfies RIP of order \(2K\), and let \(h \in \RR^N, h \neq 0\) be arbitrary. Let \(\Lambda_0\) be any subset of \(\{1,2,\dots, N\}\) such that \(|\Lambda_0| \leq K\).

Define \(\Lambda_1\) as the index set corresponding to the \(K\) entries of \(h_{\Lambda_0^c}\) with largest magnitude, and set \(\Lambda = \Lambda_0 \cup \Lambda_1\). Then

\[\| h_{\Lambda} \|_2 \leq \alpha \frac{\| h_{\Lambda_0^c} \|_1 }{ \sqrt{K}} + \beta \frac{| \langle \Phi h_{\Lambda}, \Phi h \rangle | }{\| h_{\Lambda} \|_2},\]

where

\[\alpha = \frac{\sqrt{2} \delta_{2K}}{ 1 - \delta_{2K}} , \beta = \frac{1}{ 1 - \delta_{2K}}.\]

Let us understand this lemma a bit. If \(h \in \NullSpace (\Phi)\), then the lemma simplifies to

\[\| h_{\Lambda} \|_2 \leq \alpha \frac{\| h_{\Lambda_0^c} \|_1 }{ \sqrt{K}}\]
  • \(\Lambda_0\) maps to the initial few ( \(K\) or less) elements we chose.
  • \(\Lambda_0^c\) maps to all other elements.
  • \(\Lambda_1\) maps to largest (in magnitude) \(K\) elements of \(\Lambda_0^c\) .
  • \(h_{\Lambda}\) contains a maximum of \(2K\) non-zero elements.
  • \(\Phi\) satisfies RIP of order \(2K\) .
  • Thus \((1 - \delta_{2K}) \| h_{\Lambda} \|_2 \leq \| \Phi h_{\Lambda} \|_2 \leq (1 + \delta_{2K}) \| h_{\Lambda} \|_2\) .

We now state the connection between RIP and NSP.

Theorem

Suppose that \(\Phi\) satisfies RIP of order \(2K\) with \(\delta_{2K} < \sqrt{2} - 1\) . Then \(\Phi\) satisfies the NSP of order \(2K\) with constant

\[C= \frac {\sqrt{2} \delta_{2K}} {1 - (1 + \sqrt{2})\delta_{2K}}\]
Proof

We are given

\[(1- \delta_{2K}) \| x \|^2_2 \leq \| \Phi x \|^2_2 \leq (1 + \delta_{2K}) \| x \|^2_2\]

holds for all \(x \in \Sigma_{2K}\) where \(\delta_{2K} < \sqrt{2} - 1\).

We have to show that:

\[\| h_{\Lambda}\|_2 \leq C \frac{\| h_{{\Lambda}^c}\|_1 }{\sqrt{K}}\]

holds \(\forall h \in \NullSpace (\Phi)\) and \(\forall \Lambda\) such that \(|\Lambda| \leq 2K\).

Let \(h \in \NullSpace(\Phi)\) . Then \(\Phi h = 0\) .

Let \(\Lambda_m\) denote the \(2K\) largest entries of \(h\). Then

\[\| h_{\Lambda}\|_2 \leq \| h_{\Lambda_m}\|_2 \quad \forall \Lambda : |\Lambda| \leq 2K.\]

Similarly

\[\| h_{\Lambda^c}\|_1 \geq \| h_{\Lambda_m^c}\|_1 \quad \forall \Lambda : |\Lambda| \leq 2K.\]

Thus if we show that \(\Phi\) satisfies NSP of order \(2K\) for \(\Lambda_m\) , i.e.

\[\| h_{\Lambda_m}\|_2 \leq C \frac{\| h_{{\Lambda_m}^c}\|_1 }{\sqrt{K}}\]

then we would have shown it for all \(\Lambda\) such that \(|\Lambda| \leq 2K\) . So let \(\Lambda = \Lambda_m\) .

We can divide \(\Lambda\) into two components \(\Lambda_0\) and \(\Lambda_1\) of size \(K\) each.

Since \(\Lambda\) maps to the largest \(2K\) entries in \(h\) hence whatever entries we choose in \(\Lambda_0\) , the largest \(K\) entries in \(\Lambda_0^c\) will be \(\Lambda_1\) .

Hence as per lemma above above, we have

\[\| h_{\Lambda} \|_2 \leq \alpha \frac{\| h_{\Lambda_0^c}\|_1}{\sqrt{K}}\]

Also

\[\Lambda = \Lambda_0 \cup \Lambda_1 \implies \Lambda_0 = \Lambda \setminus \Lambda_1 = \Lambda \cap \Lambda_1^c \implies \Lambda_0^c = \Lambda_1 \cup \Lambda^c\]

Thus we have

\[\| h_{\Lambda_0^c} \|_1 = \| h_{\Lambda_1} \|_1 + \| h_{\Lambda^c} \|_1\]

We have to get rid of \(\Lambda_1\) .

Since \(h_{\Lambda_1} \in \Sigma_K\) , by applying lem:u_sigma_k_norms we get

\[\| h_{\Lambda_1} \|_1 \leq \sqrt{K} \| h_{\Lambda_1} \|_2\]

Hence

\[\| h_{\Lambda} \|_2 \leq \alpha \left ( \| h_{\Lambda_1} \|_2 + \frac{\| h_{\Lambda^c} \|_1}{\sqrt{K}} \right)\]

But since \(\Lambda_1 \subset \Lambda\) , hence \(\| h_{\Lambda_1} \|_2 \leq \| h_{\Lambda} \|_2\) , hence

\[\begin{split}&\| h_{\Lambda} \|_2 \leq \alpha \left ( \| h_{\Lambda} \|_2 + \frac{\| h_{\Lambda^c} \|_1}{\sqrt{K}} \right)\\ \implies &(1 - \alpha) \| h_{\Lambda} \|_2 \leq \alpha \frac{\| h_{\Lambda^c} \|_1}{\sqrt{K}}\\ \implies &\| h_{\Lambda} \|_2 \leq \frac{\alpha}{1 - \alpha} \frac{\| h_{\Lambda^c} \|_1}{\sqrt{K}} \quad \text{ if } \alpha \leq 1.\end{split}\]

Note that the inequality is also satisfied for \(\alpha = 1\) in which case, we don’t need to bring \(1-\alpha\) to denominator.

Now

\[\begin{split}&\alpha \leq 1\\ \implies &\frac{\sqrt{2} \delta_{2K}}{ 1 - \delta_{2K}} \leq 1 \\ \implies &\sqrt{2} \delta_{2K} \leq 1 - \delta_{2K}\\ \implies &(\sqrt{2} + 1) \delta_{2K} \leq 1\\ \implies &\delta_{2K} \leq \sqrt{2} - 1\end{split}\]

Putting

\[C = \frac{\alpha}{1 - \alpha} = \frac {\sqrt{2} \delta_{2K}} {1 - (1 + \sqrt{2})\delta_{2K}}\]

we see that \(\Phi\) satisfies NSP of order \(2K\) whenever \(\Phi\) satisfies RIP of order \(2K\) with \(\delta_{2K} \leq \sqrt{2} -1\) .

Note that for \(\delta_{2K} = \sqrt{2} - 1\) , \(C=\infty\) .