4.3 Instance-optimal guarantees revisited  (Page 2/2)

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}$ drawn according to a strictly sub-Gaussian distribution with $c^2=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$ is arbitrary and ${\kappa }_2={\delta }^2/2{\kappa }^{*}-log(42e/\delta )/{\kappa }_1$ .

Even within the class of probabilistic results, there are two distinct flavors. The typical approach is to combine a probabilistic construction of a matrix that will satisfy the RIP with high probability with the previous results in this chapter. This yields a procedure that, with high probability, will satisfy a deterministic guarantee applying to all possible signals $x$ . A weaker kind of result is one that states that given a signal $x$ , we can draw a random matrix $\Phi$ and with high probability expect certain performance for that signal $x$ . This type of guarantee is sometimes called instance-optimal in probability . The distinction is essentially whether or not we need to draw a new random $\Phi$ for each signal $x$ . This may be an important distinction in practice, but if we assume for the moment that it is permissible to draw a new matrix $\Phi$ for each $x$ , then we can see that [link] may be somewhat pessimistic. In order to establish our main result we will rely on the fact, previously used in "Matrices that satisfy the RIP" , that sub-Gaussian matrices preserve the norm of an arbitrary vector with high probability. Specifically, a slight modification of Corollary 1 from "Matrices that satisfy the RIP" shows that for any $x\in {\mathbb{R}}^N$ , if we choose $\Phi$ according to the procedure in [link] , then we also have that

with ${\kappa }_3=4/{\kappa }^{*}$ . Using this we obtain the following result.

Let $x\in {\mathbb{R}}^N$ be fixed. Set ${\delta }_{2K}<\sqrt{2}-1$ Suppose that $\Phi$ is an $M\times N$ sub-Gaussian random matrix with $M\ge {\kappa }_{1}Klog\left(N,/,K\right)$ . Suppose we obtain measurements of the form $y=\Phi x$ . Set $ϵ=2{\sigma }_K{\left(x\right)}_2$ . Then with probability exceeding $1-2exp(-{\kappa }_{2}M)-exp(-{\kappa }_{3}M)$ , when $\mathcal{B}\left(y\right)=\{z:{∥\Phi ,z,-,y∥}_2\le ϵ\}$ , the solution $\widehat{x}$ to [link] obeys

First we recall that, as noted above, from [link] we have that $\Phi$ will satisfy the RIP of order $2K$ with probability at least $1-2exp(-{\kappa }_{2}M)$ . Next, let $\Lambda$ denote the index set corresponding to the $K$ entries of $x$ with largest magnitude and write $x=x_{\Lambda }+x_{{\Lambda }^c}$ . Since $x_{\Lambda }\in {\Sigma }_K$ , we can write $\Phi x=\Phi x_{\Lambda }+\Phi x_{{\Lambda }^c}=\Phi x_{\Lambda }+e$ . If $\Phi$ is sub-Gaussian then from Lemma 2 from "Sub-Gaussian random variables" we have that $\Phi x_{{\Lambda }^c}$ is also sub-Gaussian, and one can apply [link] to obtain that with probability at least $1-exp(-{\kappa }_{3}M)$ , ${∥\Phi ,x_{{\Lambda }^c}∥}_2\le 2{∥x_{{\Lambda }^c}∥}_2=2{\sigma }_K{\left(x\right)}_2$ . Thus, applying the union bound we have that with probability exceeding $1-2exp(-{\kappa }_{2}M)-exp(-{\kappa }_{3}M)$ , we satisfy the necessary conditions to apply Theorem 1 from "Signal recovery in noise" to $x_{\Lambda }$ , in which case ${\sigma }_K{\left(x_{\Lambda }\right)}_1=0$ and hence

From the triangle inequality we thus obtain

which establishes the theorem.

Thus, although it is not possible to achieve a deterministic guarantee of the form in [link] without taking a prohibitively large number of measurements, it is possible to show that such performance guarantees can hold with high probability while simultaneously taking far fewer measurements than would be suggested by [link] . Note that the above result applies only to the case where the parameter is selected correctly, which requires some limited knowledge of $x$ , namely ${\sigma }_K{\left(x\right)}_2$ . In practice this limitation can easily be overcome through a parameter selection technique such as cross-validation  [link] , but there also exist more intricate analyses of ${\ell }_1$ minimization that show it is possible to obtain similar performance without requiring an oracle for parameter selection  [link] . Note that [link] can also be generalized to handle other measurement matrices and to the case where $x$ is compressible rather than sparse. Moreover, this proof technique is applicable to a variety of the greedy algorithms described later in this course that do not require knowledge of the noise level to establish similar results  [link] , [link] .