7.2 Proof of the rip for sub-gaussian matrices  (Page 2/2)

Let $ϵ\in (0,1)$ be given. There exists a set of points $Q$ such that ${\parallel q\parallel }_2=1$ for all $q\in Q$ , $\left|Q\right|\le {(3/ϵ)}^K$ , and for any $x\in {\mathbb{R}}^K$ with ${\parallel x\parallel }_2=1$ there is a point $q\in Q$ satisfying ${\parallel x-q\parallel }_2\le ϵ$ .

We construct $Q$ in a greedy fashion. We first select an arbitrary point $q_1\in {\mathbb{R}}^K$ with $\parallel q_1{\parallel }_2=1$ . We then continue adding points to $Q$ so that at step $i$ we add a point $q_i\in {\mathbb{R}}^K$ with $\parallel q_i{\parallel }_2=1$ which satisfies $\parallel q_i-q_j{\parallel }_2>ϵ$ for all $j<i$ . This continues until we can add no more points (and hence for any $x\in {\mathbb{R}}^K$ with ${\parallel x\parallel }_2=1$ there is a point $q\in Q$ satisfying ${\parallel x-q\parallel }_2\le ϵ$ .) Now we wish to bound $\left|Q\right|$ . Observe that if we center balls of radius $ϵ/2$ at each point in $Q$ , then these balls are disjoint and lie within a ball of radius $1+ϵ/2$ . Thus, if $B^K\left(r\right)$ denotes a ball of radius $r$ in ${\mathbb{R}}^K$ , then

and hence

We now turn to our main theorem, which is based on the proof given in [link] .

Fix $\delta \in (0,1)$ . Let $\Phi$ be an $M\times N$ random matrix whose entries ${\phi }_{ij}$ are i.i.d. with ${\phi }_{ij}\sim \mathrm{SSub}(1/M)$ . If

then $\Phi$ satisfies the RIP of order $K$ with the prescribed $\delta$ with probability exceeding $1-2e^{-{\kappa }_{2}M}$ , where ${\kappa }_1>1$ is arbitrary and ${\kappa }_2={\delta }^2/2{\kappa }^{*}-1/{\kappa }_1-log(42e/\delta )$ .

First note that it is enough to prove [link] in the case ${\parallel x\parallel }_2=1$ , since $\Phi$ is linear. Next, fix an index set $T\subset \{1,2,...,N\}$ with $\left|T\right|=K$ , and let $X_T$ denote the $K$ -dimensional subspace spanned by the columns of ${\Phi }_T$ . We choose a finite set of points $Q_T$ such that $Q_T\subseteq X_T$ , ${\parallel q\parallel }_2=1$ for all $q\in Q_T$ , and for all $x\in X_T$ with ${\parallel x\parallel }_2=1$ we have

From [link] , we can choose such a set $Q_T$ with $|Q_T{|\le (42/\delta )}^K$ . We then repeat this process for each possible index set $T$ , and collect all the sets $Q_T$ together:

There are $\left(\genfrac{}{}{0pt}{}{N}{K}\right)$ possible index sets $T$ . We can bound this number by

where the last inequality follows since from Sterling's approximation we have $K!\ge {(K/e)}^K$ . Hence $\left|Q\right|\le {(42eN/\delta K)}^K$ . Since the entries of $\Phi$ are drawn according to a strictly sub-Gaussian distribution, from [link] we have [link] . We next use the union bound to apply [link] to this set of points with $ϵ=\delta /\sqrt{2}$ , with the result that, with probability exceeding

we have

We observe that if $M$ satisfies [link] then

and thus [link] exceeds $1-2e^{-{\kappa }_{2}M}$ as desired.

We now define $A$ as the smallest number such that

Our goal is to show that $A\le \delta$ . For this, we recall that for any $x\in {\Sigma }_K$ with ${\parallel x\parallel }_2=1$ , we can pick a $q\in Q$ such that ${\parallel x-q\parallel }_2\le \delta /14$ and such that $x-q\in {\Sigma }_K$ (since if $x\in X_T$ , we can pick $q\in Q_T\subset X_T$ satisfying ${\parallel x-q\parallel }_2\le \delta /14$ ). In this case we have

Since by definition $A$ is the smallest number for which [link] holds, we obtain $\sqrt{1+A}\le \sqrt{1+\delta /\sqrt{2}}+\sqrt{1+A}·\delta /14$ . Therefore

as desired. We have proved the upper inequality in [link] . The lower inequality follows from this since

which completes the proof.

Above we prove above that the RIP holds with high probability when the matrix $\Phi$ is drawn according to a strictly sub-Gaussian distribution. However, we are often interested in signals that are sparse or compressible in some orthonormal basis $\Psi \ne I$ , in which case we would like the matrix $\Phi \Psi$ to satisfy the RIP. In this setting it is easy to see that by choosing our net of points in the $K$ -dimensional subspaces spanned by sets of $K$ columns of $\Psi$ , [link] will establish the RIP for $\Phi \Psi$ for $\Phi$ again drawn from a sub-Gaussian distribution. This universality of $\Phi$ with respect to the sparsity-inducing basis is an attractive property that was initially observed for the Gaussian distribution (based on symmetry arguments), but we can now see is a property of more general sub-Gaussian distributions. Indeed, it follows that with high probability such a $\Phi$ will simultaneously satisfy the RIP with respect to an exponential number of fixed bases.