On the gap between RIP-properties and sparse recovery conditions

Introduction

The restricted isometry property (RIP) is a well-established tool to analyze the performance of sparse recovery methods. The standard version defines the restricted isometry constant of order $s$ as the smallest number $\delta_{s}$ such that

recovers a vector $x^{\sharp}$ which satisfies

where $C>0$ is an absolute constant. This bound is optimal, see also below.

Previous attempts in analyzing (BPDNp) have used RIP conditions of the form

The relation between (RIPp,q) and (BPDNp)

for any $1\leq q\leq 2$; the special case $q=2$ is stated in (2). In particular, if $\hat{x}$ is exactly $s$-sparse (so $\sigma_{s}(\hat{x})_{1}=0$) and $\varepsilon=0$, then $\hat{x}$ can be reconstructed exactly. Conversely, it is known that $m\gtrsim s\log(n/s)$ measurements are also necessary for exact reconstruction of all $s$-sparse vectors (see e.g. [14, Theorem 10.11]).

A very similar connection exists between (RIP1,1) and (BPDN1) . Indeed, the adjacency matrix of a random left $d$-regular bipartite graph with $n$ left vertices and $m$ right vertices with probability $1-\eta$ satisfies an (RIP1,1) condition of the form

where $C(\delta)=O((1-2\delta)^{-1})$ for $\delta\uparrow 1/2$.

The two positive results for $p=q=2$ and $p=q=1$ have triggered further research on (BPDNp) via restricted isometry properties. In it was shown that a standard $m\times n$ Gaussian matrix with

satisfies an (RIPp,2) property for $2\leq p<\infty$ of the form

In it is shown that the $m\times n$ adjacency matrix $A$ of a random left $d$-regular bipartite graph with $n$ left vertices and $m$ right vertices with high probability satisfies an (RIPp,p) property

see [3, Theorem A.6] for a more precise statement. Interestingly, also proved a lower bound on $m$ assuming that the $m\times n$ matrix satisfies (RIPp,p). Their result [3, Theorem 4.1] essentially shows that one needs at least $m\gtrsim s^{p}$ measurements for $p\neq 2$, so that the case $p=2$ should be considered a singularity. A straightforward modification of their argument shows that to satisfy (RIPp,2) one needs at least $m\gtrsim s^{p/2}$, so that also the result in (cf. (4)) cannot be improved significantly. We leave the verification of this implication to the interested reader.

To summarize, two important phenomena occur when moving away from the familiar (RIP2,2). First, one may need to consider different random matrix constructions to satisfy an RIP property with the optimal number of measurements. Second, the optimal scaling of the number of measurements in terms of the signal sparsity may dramatically worsen, especially for $p>2$.

Sparse recovery via BPDNp: improved results

One might think that the two phenomena concerning the (RIPp,q) properties for $p\neq 2$ mentioned above, may carry over to recovery results via (BPDNp) (see e.g. ), in particular, that the minimal required number of measurements depends significantly worse than linear on the sparsity. We will now show that rather the contrary is true: the scaling in terms of the sparsity generally does not worsen if $p\neq 2$ and, moreover, the optimal recovery results are realized by a standard Gaussian matrix.

requires either strong concentration properties or a larger number of measurements $m$ than the optimal number $s\log(en/s)$ (see the discussion in and Section 6 for more details).

The following observation follows immediately from the proof of Theorem 2.1 in , by replacing the “Chebyshev” bound

where $(\varepsilon_{i})_{i\geq 1}$ is a Rademacher sequence. Let $u>0$ and $t>0$, then, with probability at least $1-2e^{-2t^{2}}$,

If $A$ has this property, then any solution $x^{\#}$ to

satisfies, for any $1\leq r\leq q$, the reconstruction error bound

with $C_{\rho}=(1+\rho)^{2}/(1-\rho)$ and $D_{\rho}=(3+\rho)/(1-\rho)$ when $\left\|e\right\|\leq\varepsilon$ (cf. [14, Theorem 4.25]).

Note that $T_{\rho,s}^{q}$ contains $\Sigma_{s}$. We use the following observation.

and let $D_{s}^{q}$ be its convex hull. Then $D_{s}^{q}$ is the unit ball with respect to the norm

where $I_{1},\ldots,I_{\lceil n/s\rceil}$ form a uniform partition of $[n]$, i.e.,

and $x^{*}$ is the nonincreasing rearrangement of $x$. As a consequence,

We proceed by making straightforward modifications to the proof of [17, Lemma 3] (see also [29, Lemma 4.5] or ), which corresponds to the case $q=2$.

so $D_{s}^{q}$ is contained in the $\|\cdot\|_{D_{s}^{q}}$-unit ball. To prove the reverse inclusion, suppose that $\|x\|_{D_{s}^{q}}\leq 1$. We partition the index set $[n]$ into subsets $S_{1}$, $S_{2}$, …of size $s$, such that $S_{1}$ corresponds to the indices of the $s$ largest entries of $x$, $S_{2}$ to the next $s$ ones, etc. Set $\alpha_{i}=\|x_{S_{i}}\|_{q}$. Then $x$ can be written as

Clearly, for any $\alpha_{i}\neq 0$, $\|\alpha_{i}^{-1}x_{S_{i}}\|_{q}=1$ and $\|\alpha_{i}^{-1}x_{S_{i}}\|_{0}\leq s$, so $x\in D_{s}^{q}$.

where we used that in the worst case $S$ corresponds to $s$ largest absolute coefficients of $x$. It follows that

Since $\|x\|_{q}\leq 1$, (5) implies that $\|x\|_{D_{s}^{q}}\leq 2+\rho^{-1}$. ∎

We are now prepared to prove the main result of this article. To keep our exposition accessible, we first consider the special case of a standard Gaussian random matrix, i.e., a matrix with independent normally distributed entries with mean zero and variance one. In Section 5 we generalize our result to a wider class of random matrices.

Let $A$ be an $m\times n$ standard Gaussian matrix. Fix $1\leq p\leq\infty$, $q\geq 2$ and $0<\eta<1$. Suppose that

The most interesting case in the above theorem is $q=2$. Then the optimal scaling $m\geq Cs\log(en/s)$ implies that with high probability we obtain the error bound

where $X_{i}$ denotes the $i$-th row of $A$. To apply Lemma 3.1, we estimate the small ball probability $Q_{\mathcal{F}}$ and the expected Rademacher supremum $R_{m}(\mathcal{F})$ for the set of linear functions

Let $V=m^{-1/2}\sum_{i=1}^{m}\varepsilon_{i}X_{i}$, then by Lemma 3.2,

as $D_{s}^{q}$ is the convex hull of $\Sigma_{s}^{q}$. Since any $x\in\Sigma_{s}^{q}$ satisfies $\|x\|_{2}\leq s^{1/2-1/q}\|x\|_{q}$,

Since $X_{1},\ldots,X_{m}$ are independent standard Gaussian vectors, so is $V$. Thus,

the Gaussian width of $\Sigma_{s}^{2}$. It is known that

see e.g. [17, Lemma 4], and we can conclude that

where $g$ is a standard Gaussian real-valued random variable. Therefore,

Now pick $u_{*}$ small enough so that the right hand side is bigger than $1/2$, say. Pick $m$ large enough so that

By Lemma 3.1 we can now conclude that (7) holds with $\tau=4^{1/p}/u_{*}$.

Finally, let $p=\infty$. Since $\|Ax\|_{\log m}\leq e\|Ax\|_{\infty}$,

Thus, in this case the result follows from our proof for $p=\log m$. ∎

Application to quantized compressed sensing

To obtain a satisfactory reconstruction $x^{\#}$ of the signal, we would like to ensure that it is quantization consistent. This means that we require that $y=Q_{\theta}(Ax^{\#})$. If we define

then $x^{\#}$ is quantization consistent if and only if $Ax^{\#}-y\in B_{\theta}$. Thus, we should solve the following quantization consistent basis pursuit program

This program is strongly related to (BPDN∞) with $\varepsilon=\theta/2$ (which correspond to taking the closure $\overline{B_{\theta}}$ instead of $B_{\theta}$ in (QCBP)). In fact, either 1) a minimizer for (QCBP) exists, this is then also a minimizer for (BPDN∞), or 2) no minimizer exists, in which case every minimizer of (BPDN∞) is quantization inconsistent. In particular, Theorem 3.3 implies the following statement.

Let $A$ be an $m\times n$ standard Gaussian matrix and $0<\eta<1$. Suppose that

Comparing Corollary 4.1 to the performance of the usual basis pursuit denoising, (BPDN2), we can still reconstruct with the optimal number of measurements, but the reconstruction error does not decay beyond (a constant multiple of) the quantization precision $\theta$.

Let us compare to the work in , where the authors introduced and analyzed (BPDNp) with $2\leq p<\infty$ for the purpose of recovering a signal from quantized measurements (as described above). They did not obtain a result for $p=\infty$, but the idea is that the reconstruction becomes more consistent as $p\rightarrow\infty$. A main result in shows the following, via an (RIPp,2)-based analysis. Assume that the error vector $e$ consists of i.i.d. $U([-\theta/2,\theta/2])$ random variables, that is we assume that the quantization error is uniformly distributed in each bin (this is called the high resolution assumption). With probability at least $1-e^{-2t^{2}}$,

This suggests to try to recover $\hat{x}$ via (BPDNp) with $\varepsilon=\varepsilon_{p}$. Let $A$ be an $m\times n$ standard Gaussian matrix with

Compared to Corollary 4.1, the reconstruction error due to quantization error shows decay with $p$. Note, however, that the value we can take for $p$ is implicitly limited by (8), and in particular we cannot set $p=\infty$ so that $x^{\sharp}$ is not guaranteed to be quantization consistent. Moreover, when $p>2$, the number of required measurements grows faster than linear in the sparsity. In fact, it grows exponentially in $p$, as opposed to the minimal number of measurements needed in Corollary 4.1.

Generalization to different distributions

From the proof of Theorem 3.3 we extract the following statement, which allows us to generalize our recovery result (as well as Corollary 4.1) to a variety of random matrices beyond the Gaussian case, while retaining the same (optimal) recovery guarantees as for a standard Gaussian matrix.

Let $A$ be an $m\times n$ random matrix with i.i.d. rows $X_{1},\ldots,X_{m}$ which are distributed as $X$. Suppose that for some $u_{*}>0$ and $\beta>0$,

and, if $V=m^{-1/2}\sum_{i}\varepsilon_{i}X_{i}$ then for some $\kappa>0$,

where $V_{1}^{*}\geq\ldots\geq V_{n}^{*}$ is the nonincreasing rearrangement of $V$. Fix $1\leq p\leq\infty$ and $q\geq 2$. If

To verify the small ball condition (9), it is often useful to apply the Paley-Zygmund inequality

which holds for any nonnegative random variable $\zeta$. In particular, if $X$ is a random vector with independent, mean-zero entries $\xi_{1},\ldots,\xi_{n}$ which have variance $\sigma^{2}$ and fourth moment bounded by $\mu^{4}$, then

whenever $\|x\|_{2}=1$. We refer to [14, Lemmas 7.16 and 7.17] for details.

Let us now verify the conditions of Theorem 5.1 for some concrete classes of matrices.

Suppose that the rows of $A$ are i.i.d. copies of $X$, where $X$ is

If $m\gtrsim s^{2-2/q}\log(en/s)+\log(\eta^{-1})$ then the conclusion of Theorem 3.3 holds.

We verify the two conditions of Theorem 5.1. To verify (9), we use (10) for $|\langle X,x\rangle|^{2}$ to get

whenever $0\leq u\leq 1$ and $\|x\|_{2}=1$. In the last inequality, we used that $X$ is sub-isotropic and subgaussian.

To verify the second condition, note that by assumption, the random variable $\langle X_{i},x-y\rangle$ is 2-subgaussian for any $x,y\in\Sigma_{s}^{2}$. Therefore $V=m^{-1/2}\sum_{i}\varepsilon_{i}X_{i}$ is a $4$-subgaussian random vector (see e.g. [14, Theorem 7.27]). By Dudley’s inequality (see e.g. [14, Theorem 8.23]),

The following result concerns matrices with i.i.d. entries.

Suppose that $X=(\xi_{1},\ldots,\xi_{n})$, with the $\xi_{i}$ independent, mean-zero and identically distributed as $\xi$. Suppose that for some $\lambda>0$ and $\alpha\geq 1/2$,

then the conclusion of Theorem 5.1 holds.

We fix the randomness in the Rademacher sequence $(\varepsilon_{i})$. The random variables $V_{j}=m^{-1/2}\sum_{i=1}^{m}\varepsilon_{i}X_{ij}$ are then independent and mean-zero. Since $X_{ij}$ satisfies (12), [21, Lemma 2.8] shows that if $m\geq(\log(n))^{\max\{2\alpha-1,1\}}$, then for any $2\leq p\leq\log(n)$

i.e., the first $\log(n)$ moments show subgaussian behaviour. Therefore, (the proof of) [25, Lemma 6.5] shows that

The result is now immediate from Theorem 5.1. ∎

If the $A_{ij}$ are random signs (i.e. Rademachers), then $m\gtrsim s^{2-2/q}\log(en/s)+\log(\eta^{-1})$ is sufficient for the recovery guarantee in Theorem 3.3. This follows from Corollary 5.3 with $\lambda=1$, $\alpha=1/2$ and $\beta,u_{*}$ universal constants.

If the $A_{ij}$ are standard symmetric exponential random variables, then $m\gtrsim s^{2-2/q}\log(en/s)+\log(\eta^{-1})$ suffices for the recovery guarantee in Theorem 3.3. Indeed, in this case one can apply Corollary 5.3 with $\lambda=\alpha=1$ and take for $\beta,u_{*}$ universal constants.

Suppose that the $A_{ij}$ are distributed as a random variable $\xi$, which has probability density function

for some $\gamma>1$. One readily calculates that

then $m\gtrsim s^{2-2/q}\log(en/s)+\log(\eta^{-1})$ is sufficient for the recovery guarantee in Theorem 3.3.

The last example illustrates that only the behaviour of the first $\log n$ moments of the entries of $A$ is important for our sparse recovery result, the higher moments need not even exist.

We will use the following comparison theorem from (see also Theorem 2.5 in ), which is based on earlier work in . It will allow us to reduce the general case of matrices with i.i.d. isotropic, unconditional, log-concave rows to the special case of a standard symmetric exponential matrix.

Let $A$ be an $m\times n$ matrix with i.i.d. rows $X_{i}$ distributed as $X$, where $X$ is an isotropic, unconditional log-concave vector. If $m\gtrsim s^{2-2/q}\log(en/s)+\log(\eta^{-1})$, then the conclusion of Theorem 3.3 holds.

We verify the conditions of Theorem 5.1. By a result of Borell (see e.g. [22, Proposition 2.14]), $X$ is a sub-exponential vector. In fact, for any $p\geq 1$,

Since $X$ is isotropic, we can apply (10) for $|\langle X,x\rangle|^{2}$ to get

whenever $0\leq u\leq 1$ and $\|x\|_{2}=1$. This shows that (9) holds with absolute constants $u_{*},\beta>0$.

where $\mathcal{E}$ is an $m\times n$ standard symmetric exponential matrix. As a consequence, we have

RIP RIP?

The classical RIP property, (RIP2,2), played a major role in the theory of compressed sensing since . It has proved to be an optimal tool to analyze standard basis pursuit denoising for subgaussian matrices. It has also been used to show that various other random matrices, including structured random matrices, allow for uniform sparse recovery via (BPDN2) if one increases the number of measurements with additional logarithmic factors. Nevertheless, it is known that for certain ensembles (e.g. subexponential) this logarithmic increase can be avoided, establishing a gap between RIP and sparse recovery conditions.

In this work we showed that this gap becomes much more pronounced when considering (BPDNp) for $p\neq 2$. An analysis of this program via an RIP condition erroneously suggests that 1) the required optimal number of measurements for uniform sparse recovery may be much larger than in the case $p=2$, especially if $p>2$, and 2) that one may need to consider random measurements different from Gaussian to attain this optimal number. This begs the question: does this mean that researchers interested in sparse recovery should stop considering restricted isometry properties? In this paper we showed that by proving a lower (RIPp,q)-type of bound on an extension of the set of sparse vectors (cf. (7)), one can prove an optimal recovery result for a large class of matrices, which do not satisfy (RIPp,q) in the optimal measurement regime. Thus, it seems the gap between RIP-properties and sparse recovery conditions originates in the upper bound of the RIP “for all $x\in\Sigma_{s},\left\|Ax\right\|_{p}\leq C\left\|x\right\|_{q}$” – at least when considering convex optimization approaches for recovery.

To move towards a definitive answer of our question, it would be interesting to determine whether similar gaps occur between RIP-properties and sparse recovery conditions for other numerical methods. For example, there are several algorithms such as iterative hard thresholding and CoSamp for which convergence results are currently only known under the (classical) RIP.

Acknowledgements

H. Rauhut acknowledges funding by the European Research Council through the Starting Grant StG 258926.

References