A strong restricted isometry property, with an application to phaseless compressed sensing

Vladislav Voroninski, Zhiqiang Xu

Introduction

The restricted isometry property (RIP), first introduced by Candès and Tao , is one of the most commonly used tools in the study of sparse/low rank signal recovery problem. The RIP also has some connections to the Johnson-Lindenstrauss lemma and its study has lead to new results about the lemma . The aim of this paper is to present a strong restricted isometry property which naturally occurs when considering phaseless compressed sensing.

In practice, signals of interest are often sparse in some basis and in particular this occurs in some regimes of X-ray crystallography. It is natural to exploit this sparsity structure to minimize the number of measurements needed for recovery since measurement acquisition is expensive and can destroy the sample at hand. We define phaseless compressed sensing (PCS) as the problem of recovering a sparse signal from few such phaseless measurements. It was shown in that a $k$ -sparse signal $x_{0}$ can be recovered from $O(k^{2}\log n)$ phaseless measurements via convex programming. Surprisingly, and in contrast to the case of compressed sensing from linear measurements, it was also established in that the natural information theoretic lower-bound of $O(k\log n)$ measurements cannot be achieved using a naive semi-definite programming relaxation.

Meanwhile, phaseless measurements are generically injective modulo phase over $k$ -sparse signals as soon as the over-sampling factor is $2$ . Thus, the combinatorially hard problem of finding

Main results

For convenience, let $[m]:=\{1,\ldots,m\}$ . Now we introduce the definition of SRIP:

It is well-known that an $m\times n$ Gaussian matrix with $m=O(k\log(n/k))$ satisfies the RIP property of order $k$ with high probability. We establish below that the SRIP also holds for random Gaussian matrices of the same size with high probability, for constants $\theta_{-},\theta_{+}$ which are necessarily bounded below by some non-zero universal constant. We have the following result:

where $\lvert Ax\rvert:=[\lvert\langle{a_{j},x}\rangle\rvert:j\in[m]]$ and $[m]:=\{1,\ldots,m\}$ .

Theorem 2.1 shows that Gaussian random matrixes satisfy SRIP with high probability. Another popular measurement ensemble in compressed sensing is the Bernoulli ensemble, which is defined as

For any matrix A in this ensemble, we set

i.e., the first two entries of $a_{j}$ are same provided $j\in I_{0}$ . Then either $\lvert I_{0}\rvert\geq m/2$ or $\lvert I_{0}^{c}\rvert\geq m/2$ holds. Without loss of generality, we assume that $\lvert I_{0}\rvert\geq m/2$ . Then a simple observation is that the first two columns of the matrix $A_{I_{0}}:=[a_{j}:j\in I_{0}]^{\top}$ are linearly dependent, which implies that $A$ does not satisfy SRIP of order $k\geq 2$ .

Restricted Isometry Properties of some $m\times n$ matrix $A$ can be interpreted as controlling the singular values of various submatrices of $A$ . For instance, establishing that A has the RIP of order $k$ and level $\delta$ , is equivalent to saying that the singular values of any $m\times k$ submatrix of A lie in a $\delta$ -neighborhood of 1. From this perspective, the SRIP with these parameters demands that the same is true of any $m^{\prime}\times k$ submatrix of A for which $m^{\prime}\geq m/2$ , which in turn means that any $m^{\prime}\times n$ submatrix of A, with $m^{\prime}\geq m/2$ , satisfies RIP with the aforementioned parameters. This can be interpreted as an erasure robust-property. D. Mixon and A. Bandiera have studied Numerically Erasure Robust Frames , which instead have the property that singular values of any $m^{\prime}\times n$ submatrix of A, with $m^{\prime}>m/2$ are in a $\delta$ neighborhood of 1. Our results are complementary. For instance, the RIP property is robust to arbitrarily large erasures, while this is unknown for NERFs.

Preliminaries

provided $A$ satisfies the RIP of order $t\cdot k$ and $\delta_{t\cdot k}<\sqrt{1-\frac{1}{t}}$ where $t>4/3$ .

The authors of used (3.5) to present a simple proof that the random matrices at hand satisfy RIP. This inequality (3.5) also follows by the concentration of measure of Gaussian space:

The expectation of the $k$ th smallest random variable. Follow the definition in , we say that a random variable $\xi$ satisfies the $(\alpha,\beta)$ -condition if

where $\alpha>0,\beta>0$ are parameters. Then the following theorem presents a lower bound for the expectation of the $k$ th smallest order statistic of $m$ such independent random variables.

() Let $\alpha>0,\beta>0$ . Let $\xi_{1},\ldots,\xi_{m}$ be independent random variables satisfying the $(\alpha,\beta)$ -condition. Then

where $c_{\alpha}=\frac{1}{2e\alpha}(1-\frac{1}{4\sqrt{\pi}})$ and $\lvert\xi\rvert_{(k)}$ is the $k$ th smallest order statistic, i.e., $\lvert\xi\rvert_{(1)}\leq\cdots\leq\lvert\xi\rvert_{(m)}$ .

Johnson-Lindenstrauss Lemma. The J-L lemma, which has proven to be a useful tool in dimensionality reduction, follows easily from (3.5) :

The strong concentration of measure inequality and Johnson-Lindenstrauss Lemma

In this section, we extend the concentration inequality (3.5) to a stronger version which plays an important role in our proof of the main results.

where $\lvert x\rvert_{(1)}\leq\cdots\leq\lvert x\rvert_{(m)}$ . Then we have

Here, in the third inequality, we use the rearrangement inequality. Then we have

We assume that $X_{1},\ldots,X_{m}$ are i.i.d. ${\mathcal{N}}(0,1)$ and set

where $\lvert X\rvert_{(1)}\leq\lvert X\rvert_{(2)}\leq\cdots\leq\lvert X\rvert_{(m)}$ . Then for any $m\geq 1$ , we have

where $\nu_{0}:=\frac{1}{32e}\cdot\sqrt{\frac{\pi}{2}}\cdot\left(1-\frac{1}{4\sqrt{\pi}}\right)\thickapprox 0.0124$ .

We first consider the case where $m\leq 8$ . Then Theorem 3.2 implies that

We next only consider the case where $m>8$ . By applying Theorem 3.2 to standard Gaussian rvs, for which $\alpha=\sqrt{2/\pi}$ , we obtain that

We take $k=\lfloor m/4\rfloor$ and obtain that

Combining (4.6) and (4.7), we obtain that

Combining the results above, we arrive at

Under the conditions of Lemma 4.2 we have

Combining Lemma 4.1 and Theorem 3.1, we obtain that

where $\tau\geq 0$ . Taking $\tau:=\sqrt{m}t$ , we arrive at

We next state the strong concentration of measure inequalities:

holds with probability $1-2e^{-cm}$ where $c>0$ is an absolute constant.

Without loss of generality, we assume that $\|\bar{x}\|_{2}=1$ . Set $y:=A\bar{x}$ and $y_{I}:=A_{I}\bar{x}$ where $I\subseteq[m]$ . Then the entries of $y$ are independent realizations of Gaussian random variables $y_{j}\sim{\mathcal{N}}(0,1/m)$ . Based on Lemma 4.2, $\mu_{m}\geq\nu_{0}$ for any $m\geq 1$ . Taking $t=\nu_{0}/2$ in Lemma 4.3, we have

And hence, the upper bound follows from the proof of the classical concentration of measure inequalities (3.5). ∎

Combining Lemma 4.4 and a standard probability argument of J-L lemma, we can obtain the erasure-robust version of the J-L Lemma, which can be interpreted as a J-L map that has robustness to corrupted measurements.

holds for all $u,v\in Q$ and all $I\subset[m]$ with $\lvert I\rvert\geq m/2$ . Here $f_{I}(u)$ denotes the sub-vector of $f(u)$ only the entries with the indices in $I$ are kept.

Based on the argument of Lemma 4.4, one can observe that $c_{-}\thickapprox 10^{-5}$ and also take $c_{+}=1+\epsilon$ for arbitrary fixed $\epsilon>0$ . Numerical experiments show that Lemma 4.5 still holds if one takes $c_{-}\thickapprox 0.1$ . And hence, it would be interesting to improve the constant $c_{-}$ in Lemma 4.5.

Proofs of Theorem 2.1 and 2.2

First, note that $\|A_{I}x\|_{2}^{2}\leq\|Ax\|_{2}^{2}$ for any $I\subset[m]$ . And hence, according to RIP theory, there exists $1<\theta_{+}<2$ so that

Note that $\lvert{\mathcal{N}}_{\epsilon}\rvert\leq(12/\epsilon)^{tk}$ . Then, according to Lemma 4.4, there exists $c_{-}>0$ such that

We can take $\epsilon$ small enough so that $\sqrt{c_{-}}-\sqrt{\theta_{+}}\epsilon>0$ . Set $\theta_{-}:=(\sqrt{c_{-}}-\sqrt{\theta_{+}}\epsilon)^{2}$ . Then

holds for all $x$ with ${\rm supp}(x)\subset\Omega$ with probability at least $1-\exp(tk\log(12/\epsilon)-cm)$ . Note that there are ${n\choose tk}$ distinct $\Omega\subset[n]$ and

Thus the desired SRIP property holds for all $tk$ -sparse vectors with probability at least $1-\exp(-cm/2)$ provided

The solution to (5.8), if it exists, is denoted as $x_{\epsilon}$ . We claim that for any $\epsilon\in\{1,-1\}^{m}$ we must have

if $x_{\epsilon}$ exists (it may not exist), and the equality holds if and only if $x_{\epsilon}=\pm x_{0}$ .

Assume the claim is false. Then either $\|x_{\epsilon}\|_{1}<\|x_{0}\|_{1}$ or $\|x_{\epsilon}\|_{1}=\|x_{0}\|_{1}$ but $x_{\epsilon}\neq\pm x_{0}$ . Observe that $|Ax_{\epsilon}|=|Ax_{0}|$ . So $\langle{a_{j},x_{\epsilon}}\rangle=\pm\langle{a_{j},x_{0}}\rangle$ for all $j$ . Let

Then either $\lvert I\rvert\geq m/2$ or $\lvert I^{c}\rvert\geq m/2$ . We first assume that $\lvert I\rvert\geq m/2$ . Then $A_{I}x_{\epsilon}=A_{I}x_{0}$ . Here $A_{I}=[a_{j}:j\in I]^{\top}$ . However, $A$ satisfies the strong RIP of order $tk$ and levels $\theta_{-},\theta_{+}$ with $t\geq\max\{\frac{1}{2\theta_{-}-\theta_{-}^{2}},\frac{1}{2\theta_{+}-\theta_{+}^{2}}\}$ . Consequently $A_{I}$ satisfies RIP of order $tk$ and $\delta_{tk}\leq\max\{{1-\theta_{-}},{\theta_{+}-1}\}<\sqrt{1-\frac{1}{t}}$ . Then, using the results in (see also Section 3), we must have

Note that $x_{\epsilon}\in\{x:A_{I}x=A_{I}x_{0}\}$ and hence $\|x_{0}\|_{1}\leq\|x_{\epsilon}\|_{1}$ . Based on the assumption of either $\|x_{\epsilon}\|_{1}<\|x_{0}\|_{1}$ or $\|x_{\epsilon}\|_{1}=\|x_{0}\|_{1}$ , we obtain $\|x_{\epsilon}\|_{1}=\|x_{0}\|_{1}$ , which implies that $x_{\epsilon}=x_{0}$ , which is a contradiction. In the case $\lvert I^{c}\rvert\geq m/2$ , similar argument yields $x_{\epsilon}=-x_{0}$ , also a contradiction. We have now proved the theorem. ∎

Discussion and future directions