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.
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
where
Let us understand this lemma a bit. If \(h \in \NullSpace (\Phi)\), then the lemma simplifies to
- \(\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.
Suppose that \(\Phi\) satisfies RIP of order \(2K\) with \(\delta_{2K} < \sqrt{2} - 1\) . Then \(\Phi\) satisfies the NSP of order \(2K\) with constant
We are given
holds for all \(x \in \Sigma_{2K}\) where \(\delta_{2K} < \sqrt{2} - 1\).
We have to show that:
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
Similarly
Thus if we show that \(\Phi\) satisfies NSP of order \(2K\) for \(\Lambda_m\) , i.e.
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
Also
Thus we have
We have to get rid of \(\Lambda_1\) .
Since \(h_{\Lambda_1} \in \Sigma_K\) , by applying lem:u_sigma_k_norms we get
Hence
But since \(\Lambda_1 \subset \Lambda\) , hence \(\| h_{\Lambda_1} \|_2 \leq \| h_{\Lambda} \|_2\) , hence
Note that the inequality is also satisfied for \(\alpha = 1\) in which case, we don’t need to bring \(1-\alpha\) to denominator.
Now
Putting
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\) .