Sparse Representation of a Polytope and Recovery of Sparse Signals and Low-rank Matrices

Introduction

A closely related problem to compressed sensing is the affine rank minimization problem (ARMP) (Recht et al. ), which aims to recover an unknown low-rank matrix based on its affine transformation. In ARMP, one observes

where $\|B\|_{\ast}$ is the nuclear norm of $B$, which is defined as the sum of all singular values of $B$.

When $s$ is not an integer, we define $\delta_{s}^{A}$ as $\delta_{\lceil s\rceil}^{A}$.

Different conditions on the RIC for sparse signal recovery have been introduced and studied in the literature. For example, sufficient conditions for the exact recovery in the noiseless case include $\delta_{2k}<\sqrt{2}-1$ in , $\delta_{2k}<0.472$ in , $\delta_{2k}<0.497$ in , $\delta_{k}<0.307$ in , $\delta_{k}<1/3$ and $\delta_{2k}\leq 1/2$ in . There are also other sufficient conditions that involve the RIC of different orders, e.g. $\delta_{3k}^{A}+3\delta_{4k}^{A}<2$ in , $\delta_{k}^{A}+\delta_{2k}^{A}<1$ in , $\delta_{2k}^{A}<0.5746$ jointly with $\delta_{8k}^{A}<1$, $\delta_{3k}^{A}<0.7731$ jointly with $\delta_{16k}^{A}<1$ in and $\delta_{2k}^{A}<4/\sqrt{41}$ in .

When $r$ is not an integer, we define $\delta_{r}^{\mathcal{M}}$ as $\delta_{\lceil r\rceil}^{\mathcal{M}}$.

As in compressed sensing, there are many sufficient conditions based on the RIC to guarantee the exact recovery of matrices of rank at most $r$ through the constrained nuclear norm minimization (4). These include $\delta_{4r}^{\mathcal{M}}<\sqrt{2}-1$ , $\delta_{5r}^{\mathcal{M}}<0.607$, $\delta_{4r}^{\mathcal{M}}<0.558$, and $\delta_{3r}^{\mathcal{M}}<0.4721$ , $\delta_{2r}^{\mathcal{M}}<0.4931$ , $\delta_{r}^{\mathcal{M}}<0.307$ , $\delta_{r}^{\mathcal{M}}<1/3$ , and $\delta_{2r}^{\mathcal{M}}<1/2$ .

Among these sufficient RIP conditions, $\delta_{k}^{A}<1/3$ and $\delta_{r}^{\mathcal{M}}<1/3$ have been verified in to be sharp for both sparse signal recovery and low-rank matrix recovery problems. Sharp conditions on the higher order RICs are however still unknown. As pointed out by Blanchard and Thompson , higher-order RIC conditions can be satisfied by a significantly larger set of Gaussian random matrices in some settings. It is therefore of both theoretical and practical interests to obtain sharp sufficient conditions on the high order RICs.

Then $v\in T(\alpha,s)$ if and only if $v$ is in the convex hull of $U(\alpha,s,v)$. In particular, any $v\in T(\alpha,s)$ can be expressed as

Combining the results developed in Sections 2 and 3, we establish the following sharp sufficient RIP conditions for the exact recovery of all $k$-sparse signals and low-rank matrices in the noiseless case. We focus here on the exact sparse and noiseless case; the general approximately sparse (low-rank) and noisy case is considered in Sections 2 and 3.

for some $t\geq 4/3$, then the nuclear norm minimizer $X_{*}$ of (4) with $\mathcal{B}=\{0\}$ recovers $X$ exactly.

Moreover, it will be shown that for any $\epsilon>0$, $\delta_{tk}^{A}<\sqrt{\frac{t-1}{t}}+\epsilon$ is not sufficient to guarantee the exact recovery of all $k$-sparse signals for large $k$. Similar result also holds for matrix recovery. For the more general approximately sparse (low-rank) and noisy cases considered in Sections 2 and 3, it is shown that Conditions (8) and (9) are also sufficient respectively for stable recovery of (approximately) $k$-sparse signals and (approximately) rank-$r$ matrices in the noisy case. An oracle inequality is also given in the case of compressed sensing with Gaussian noise under the condition $\delta_{tk}^{A}<\sqrt{(t-1)/t}$ when $t\geq 4/3$.

The rest of the paper is organized as follows. Section 2 considers sparse signal recovery and Section 3 focuses on low-rank matrix recovery. Discussions on the case $t<4/3$ and some related issues are given in Section 4. The proofs of the key technical result Lemma 1.1 and the main theorems are contained in Section 5.

Compressed Sensing

Let us consider the signal recovery model (1) in the setting where the observations contain noise and the signal is not exactly $k$-sparse. This is of significant interest for many applications. Two types of bounded noise settings,

are of particular interest. The first bounded noise case was considered for example in . The second case is motivated by the Dantzig Selector procedure proposed in . Results on the Gaussian noise case, which is commonly studied in statistics, follow immediately. For notational convenience, we write $\delta$ for $\delta^{A}_{tk}$.

Now consider the signal recovery model (1) with $\|A^{T}z\|_{\infty}\leq\varepsilon$. Suppose $\hat{\beta}^{DS}$ is the minimizer of (2) with $\mathcal{B}=\mathcal{B}^{DS}(\eta)=\{z:\|A^{T}z\|_{\infty}\leq\eta\}$ for some $\eta\geq\varepsilon$. If $\delta=\delta_{tk}^{A}<\sqrt{(t-1)/t}$ for some $t\geq 4/3$, then

The result for the noiseless case follows directly from Theorem 2.1. When $\beta$ is exactly $k$-sparse and there is no noise, by setting $\eta=\epsilon=0$ and by noting $\beta_{-\max(k)}=0$, we have $\hat{\beta}=\beta$ from (10), where $\hat{\beta}$ is the minimizer of (2) with $\mathcal{B}=\{0\}$.

It should be noted that Theorems 1.1 and 2.1 also hold for $1<t<4/3$ with exactly the same proof. However the bound $\sqrt{(t-1)/t}$ is not sharp for $1<t<4/3$. See Section 4 for further discussions. The condition $t\geq 4/3$ is crucial for the “sharpness” results given in Theorem 2.2 at the end of this section.

The signal recovery model (1) with Gaussian noise is of particular interest in statistics and signal processing. The following results on the i.i.d. Gaussian noise case are immediate consequences of the above results on the bounded noise cases using the same argument as that in , since the Gaussian random variables are essentially bounded.

and with probability at least $1-1/\sqrt{\pi\log p}$,

The oracle inequality approach was introduced by Donoho and Johnstone in the context of wavelet thresholding for signal denoising. It provides an effective way to study the performance of an estimation procedure by comparing it to that of an ideal estimator. In the context of compressed sensing, oracle inequalities have been given in under various settings. Proposition 2.2 below provides an oracle inequality for compressed sensing with Gaussian noise under the condition $\delta_{tk}^{A}<\sqrt{(t-1)/t}$ when $t\geq 4/3$.

Given (1), suppose the error vector $z\sim N_{n}(0,\sigma^{2}I)$, $\beta$ is $k$-sparse. Let $\hat{\beta}^{DS}$ be the minimizer of (2) with $\mathcal{B}=\{z:\|A^{T}z\|_{\infty}\leq 4\sigma\sqrt{\log p}\}$. If $\delta_{tk}^{A}<\sqrt{(t-1)/t}$ for some $t\geq 4/3$, then with probability at least $1-1/\sqrt{\pi\log p}$,

We now turn to show the sharpness of the condition $\delta_{tk}^{A}<\sqrt{(t-1)/t}$ for the exact recovery in the noiseless case and stable recovery in the noisy case. It should be noted tha tthe result in the special case $t=2$ was shown in .

Let $t\geq 4/3$. For all $\varepsilon>0$ and $k\geq 5/\varepsilon$, there exists a matrix $A$ satisfying $\delta_{tk}<\sqrt{\frac{t-1}{t}}+\varepsilon$ and some $k$-sparse vector $\beta_{0}$ such that

Affine Rank Minimization

We consider the affine rank minimization problem (3) in this section. As mentioned in the introduction, this problem is closely related to compressed sensing. The close connections between compressed sensing and ARMP have been studied in Oymak, et al. . We shall present here the analogous results on affine rank minimization without detailed proofs.

Similarly, consider ARMP (3) with $z$ satisfying $\|\mathcal{M}^{\ast}(z)\|\leq\varepsilon$. Let $X_{\ast}^{DS}$ be the minimizer of (4) with $\mathcal{M}=\mathcal{B}^{DS}(\eta)$ defined in (14), then

In the special noiseless case where $z=0$, it can be seen from either of these two inequalities above that all matrices $X$ with rank at most $r$ can be exactly recovered provided that $\delta_{tr}^{\mathcal{M}}<\sqrt{(t-1)/t}$, for some $t\geq 4/3$.

The following result shows that the condition $\delta_{tr}^{\mathcal{M}}<\sqrt{(t-1)/t}$ with $t\geq 4/3$ is sharp. These results together establish the optimal bound on $\delta_{tr}^{\mathcal{M}}$ $(t\geq 4/3)$ for the exact recovery in the noiseless case.

Suppose $t\geq 4/3$. For all $\varepsilon>0$ and $r\geq 5/\varepsilon$, there exists a linear map $\mathcal{M}$ with $\delta_{tr}^{\mathcal{M}}<\sqrt{(t-1)/t}+\varepsilon$ and some matrix $X_{0}$ of rank at most $r$ such that

in the noiseless case, i.e. $b=\mathcal{M}(X_{0})$, the nuclear norm minimization method (4) with $\mathcal{B}=\{0\}$ fails to exactly recover $X_{0}$, i.e. $X_{\ast}\neq X_{0}$, where $X_{\ast}$ is the solution to (4).

in the noisy case, i.e. $b=\mathcal{M}(X_{0})+z$, for all constraints $\mathcal{B}_{z}$ (may depends on $z$), the nuclear norm minimization method (4) fails to stably recover $X_{0}$, i.e. $X_{\ast}\nrightarrow X_{0}$ as $z\to 0$, where $X_{\ast}$ is the solution to (4) with $\mathcal{B}=\mathcal{B}_{z}$.

Discussion

We shall focus the discussions in this section exclusively on compressed sensing as the results on affine rank minimization is analogous. In Section 2, we have established the sharp RIP condition on the high-order RICs,

for the recovery of $k$-sparse signals in compressed sensing. In addition, it is known from that $\delta_{k}^{A}<1/3$ is also a sharp RIP condition. For a general $t>0$, denote the sharp bound for $\delta_{tk}^{A}$ as $\delta_{\ast}(t)$. Then

A natural question is: What is the value of $\delta_{\ast}(t)$ for $t<4/3$ and $t\neq 1$? That is, what is the sharp bound for $\delta_{tk}^{A}$ when $t<4/3$ and $t\neq 1$? We have the following partial answer to the question.

In addition, the following result shows that $\delta_{*}(t)\leq\frac{t}{4-t}$ for all $0<t<4/3$. In particular, when $t=1$, the upper bound $t/(4-t)$ coincides with the true sharp bound $1/3$.

For $0<t<4/3$, $\varepsilon>0$ and any integer $k\geq 1$, $\delta_{tk}^{A}<\frac{t}{4-t}+\varepsilon$ is not suffient for the exact recovery. Specifically, there exists a matrix $A$ with $\delta_{tk}^{A}=\frac{t}{4-t}$ and a $k$-sparse vector $\beta_{0}$ such that $\hat{\beta}\neq\beta_{0}$, where $\hat{\beta}$ is the minimizer of (2) with $\mathcal{B}=\{0\}$.

Propositions 4.1 and 4.2 together show that $\delta_{*}(t)=\frac{t}{4-t}$ when $tk$ is even and $0<t<1$. We are not able to provide a complete answer for $\delta_{*}(t)$ when $0<t<4/3$. We conjecture that $\delta_{*}(t)=\frac{t}{4-t}$ for all $0<t<4/3$. The following figure plots $\delta_{*}(t)$ as a function of $t$ based on this conjecture for the interval $(0,4/3)$.

Our results show that exact recovery of $k$-sparse signals in the noiseless case is guaranteed if $\delta_{tk}^{A}<\sqrt{(t-1)/t}$ for some $t\geq 4/3$. It is then natural to ask the question: Among all these RIP conditions $\delta_{tk}^{A}<\delta_{\ast}(t)$, which one is easiest to be satisfied? There is no general answer to this question as no condition is strictly weaker or stronger than the others. It is however interesting to consider special random measurement matrices $A=(A_{ij})_{n\times p}$ where

Baraniuk et al provides a bound on RICs for a set of random matrices from concentration of measure. For these random measurement matrices, Theorem 5.2 of shows that for positive integer $m<n$ and $0<\lambda<1$,

For $0<t<4/3$, using the conjectured value $\delta_{*}(t)=\frac{t}{4-t}$, we have

It is easy to see when $p,k,$ and $p/k\to\infty$, the lower bound of $n$ to ensure $\delta_{tk}^{A}<t/(4-t)$ or $\delta_{tk}^{A}<\sqrt{(t-1)/t}$ to hold in high probability is $n\geq k\log(p/k)n^{\ast}(t)$, where

For the plot of $n^{\ast}(t)$, see Figure 1. $n^{\ast}(t)$ has minimum $83.2$ when $t=1.85$. Moreover, among integer $t$, $t=2$ can also provide a near-optimal minimum: $n^{\ast}(2)=83.7$.

We should note that the above analysis is based on the bound given in (17) which itself can be possibly improved.

Proofs

We shall first establish the technical result, Lemma 1.1, and then prove the main results.

Proof of Lemma 1.1. First, suppose $v\in T(\alpha,s)$. We can prove $v$ is in the convex hull of $U(\alpha,s,v)$ by induction. If $v$ is $s$-sparse, $v$ itself is in $U(\alpha,s,v)$.

Suppose the statement is true for all $(l-1)$-sparse vectors $v$ ($l-1\geq s$). Then for any $l$-sparse vector $v$ such that $\|v\|_{\infty}\leq\alpha$, $\|v\|_{1}\leq s\alpha$, without loss of generality we assume that $v$ is not $(l-1)$-sparse (otherwise the result holds by assumption of $l-1$). Hence we can express $v$ as $v=\sum_{i=1}^{l}a_{i}e_{i}$, where $e_{i}$’s are different unit vectors with one entry of $\pm 1$ and other entries of zeros; $a_{1}\geq a_{2}\geq\cdots\geq a_{l}>0$. Since $\sum_{i=1}^{l}a_{i}=\|v\|_{1}\leq s\alpha$, so

which means $D$ is not empty. Take the largest element in $D$ as $j$, which implies

(It is noteworthy that even if the largest $j$ in $D$ is $l-1$, (18) still holds). Define

which satisfies $\sum_{i=j}^{l}a_{i}=(l-j)\sum_{i=j}^{l}b_{i}$. By (18), for all $j\leq w\leq l$,

then $0\leq\lambda_{w}\leq 1$, $\sum_{w=j}^{l}\lambda_{w}=1$, $\sum_{w=j}^{l}\lambda_{w}v_{w}=v$, $\text{supp}(v_{w})\subseteq\text{supp}(v)$. We also have

In addition, $v_{i}=\sum_{i=1}^{N_{w}}\lambda_{i,w}u_{i,w}$, so $v=\sum_{w=j}^{l}\sum_{i=1}^{N_{w}}\lambda_{w}\lambda_{i,w}u_{i,w}$, which proves the result for $l$.

The proof of the other part of the lemma is easier. When $v$ is in the convex hull of $U(\alpha,s,v)$, then we have

which finished the proof of the lemma. $\square$

Proof of Theorem 1.1 First, we assume that $tk$ is an integer. By the well-known Null Space Property (Theorem 1 in ), we only need to check for all $h\in\mathcal{N}(A)\setminus\{0\}$, $\|h_{\max(k)}\|_{1}<\|h_{-\max(k)}\|_{1}$. Suppose there exists $h\in\mathcal{N}(A)\setminus\{0\}$, such that $\|h_{\max(k)}\|_{1}\geq\|h_{-\max(k)}\|_{1}$. Set $\alpha=\|h_{\max(k)}\|_{1}/k$. We divide $h_{-\max(k)}$ into two parts, $h_{-\max(k)}=h^{(1)}+h^{(2)}$, where

Then $\|h^{(1)}\|_{1}\leq\|h_{-\max(k)}\|_{1}\leq\alpha k$. Denote $|\text{supp}(h^{(1)})|=\|h^{(1)}\|_{0}=m$. Since all non-zero entries of $h^{(1)}$ have magnitude larger than $\alpha/(t-1)$, we have

Namely $m\leq k(t-1)$. In addition we have

We now apply Lemma 1.1 with $s=k(t-1)-m$. Then $h^{(2)}$ can be expressed as a convex combination of sparse vectors: $h^{(2)}=\sum_{i=1}^{N}\lambda_{i}u_{i}$, where $u_{i}$ is $(k(t-1)-m)$-sparse and

Now we suppose $\mu\geq 0,c\geq 0$ are to be determined. Denote $\beta_{i}=h_{\max(k)}+h^{(1)}+\mu u_{i}$, then

Since $h_{\max(k)}$, $h^{(1)}$, $u_{i}$ are $k$-, $m$-, $(k(t-1)-m)$-sparse respectively, $\beta_{i}=h_{\max(k)}+h^{(1)}+\mu u_{i}$, $\sum_{j=1}^{N}\lambda_{j}\beta_{j}-c\beta_{i}-\mu h=(1-\mu-c)(h_{\max(k)}+h^{(1)})-c\mu u_{i}$ are all $tk$-sparse vectors.

Since $Ah=0$ and (24), we have $A(\sum_{j=1}^{N}\lambda_{j}\beta_{j}-c\beta_{i})=A((1-\mu-c)(h_{\max(k)}+h^{(1)})-c\mu u_{i})$. Set $c=1/2$, $\mu=\sqrt{t(t-1)}-(t-1)$, let the left hand side of (25) minus the right hand side, we get

When $tk$ is not an integer, note $t^{\prime}=\lceil tk\rceil/k$, then $t^{\prime}>t$, $t^{\prime}k$ is an integer,

which can be deduced to the former case. Hence we finished the proof. $\square$

Define $\alpha=(\|h_{\max(k)}\|_{1}+2\|\beta_{-\max(k)}\|_{1})/k$. Similarly as the proof of Theorem 1.1, we divide $h_{-\max(k)}$ into two parts, $h_{-\max(k)}=h^{(1)}+h^{(2)}$, where

Then $\|h^{(1)}\|_{1}\leq\|h_{-\max(k)}\|_{1}\leq\alpha k$. Denote $|\text{supp}(h^{(1)})|=\|h^{(1)}\|_{0}=m$. Since all non-zero entries of $h^{(1)}$ have magnitude larger than $\alpha/(t-1)$, we have

Namely $m\leq k(t-1)$. Hence, (21) still holds. Besides, $\|h_{\max(k)}+h^{(1)}\|_{0}=k+m\leq tk$, we have

Again by (21), we apply Lemma 1.1 by setting $s=k(t-1)-m$, we can express $h^{(2)}$ as a weighted mean: $h^{(2)}=\sum_{i=1}^{N}\lambda_{i}u_{i}$, where $u_{i}$ is $(k(t-1)-m)$-sparse and (22) still holds. Hence,

Now we suppose $1\geq\mu\geq 0,c\geq 0$ are to be determined. Denote $\beta_{i}=h_{\max(k)}+h^{(1)}+\mu u_{i}$, then we still have (24). Similarly to the proof of Theorem 1.1, since $h_{\max(k)},h^{(1)},u_{i}$ are $k$-, $m$-, $(k(t-1)-m)$-sparse vectors, respectively, we know $\beta_{i}=h_{\max(k)}+h^{(1)}+\mu u_{i}$, $\sum_{j=1}^{N}\lambda_{j}\beta_{j}-c\beta_{i}-\mu h=(1-\mu-c)(h_{\max(k)}+h^{(1)})-c\mu u_{i}$ are all $tk$ sparse vectors.

Suppose $x=\|h_{\max(k)}+h^{(1)}\|_{2}$, $P=\frac{2\|\beta_{-\max(k)}\|_{1}}{\sqrt{k}}$, then

Now since $\beta_{i}$, $(\frac{1}{2}-\mu)(h_{\max(k)}+h^{(1)})-\frac{\mu}{2}u_{i}$ are all $tk$-sparse vectors, we apply the definition of $\delta_{tk}^{A}$ and also (27) to get

which is an second-order inequality for $x$. By solving this inequality we get

Finally, note that $\|h_{-\max(k)}\|_{1}\leq\|h_{\max(k)}\|_{1}+P\sqrt{k}$, by Lemma 5.3 in , we obtain $\|h_{-\max(k)}\|_{2}\leq\|h_{\max(k)}\|_{2}+P$, so

When $tk$ is not an integer, again we define $t^{\prime}=\lceil tk\rceil/k$, then $t^{\prime}>t$ and $\delta_{t^{\prime}k}^{A}=\delta_{tk}^{A}<\sqrt{\frac{t-1}{t}}<\sqrt{\frac{t^{\prime}-1}{t^{\prime}}}$. We can prove the result by working on $\delta_{t^{\prime}k}^{A}$.

For the inequality on $\hat{\beta}^{DS}$ (11), the proof is similar. Define $h=\hat{\beta}^{DS}-\beta$. We have the following inequalities

instead of (26) and (27). We can prove (11) basically the same as the proof above except that we use (29) instead of (27) when we go from the third term to the fourth term in (28). $\square$

Proof of Proposition 2.1. By a small extension of Lemma 5.1 in , we have $\|z\|_{2}\leq\sigma\sqrt{n+2\sqrt{n\log n}}$ with probability at least $1-1/n$; $\|A^{T}z\|_{\infty}\leq\sigma\sqrt{2(1+\delta_{1}^{A})\log p}\leq 2\sigma\sqrt{\log p}$ with probability at least $1-1/\sqrt{\pi\log p}$. Then the Proposition is immediately implied by Theorem 2.1. $\square$

Proof of Proposition 2.2. The proof of Proposition (2.2) is similar to that of Theorem 4.1 in and Theorem 2.7 in .

First, as in the proof of Proposition 2.1, we have $\|A^{T}z\|_{\infty}\leq\lambda/2$ with probability at least $1/\sqrt{\pi\log n}$. In the rest proof, we will prove (12) in the event that $\|A^{T}z\|_{\infty}\leq\lambda/2$. Define

Let $\bar{\beta}=\arg\min_{\xi}K(\xi,\beta)$. Since $K(\bar{\beta},\beta)\leq K(\beta,\beta)$, we have $\gamma\|\bar{\beta}\|_{0}\leq\gamma\|\beta\|_{0}$, which means $\bar{\beta}$ is $k$-sparse.

Now we introduce the following lemma which can be regarded as an extension of Lemma 4.1 in .

We omit the proof here as the proof of Lemma 4.1 in can still apply to this lemma.

When $t\geq 2$, $\delta_{2k}^{A}\leq\delta_{tk}^{A}$, which means

With a small edition on Lemma 5.4 in and Lemma 3.5 in , we have

Since $\bar{\beta}$ is $k$-sparse, we can apply Theorem 2.1 by plugging $\beta$ by $\bar{\beta}$ and get

Suppose $\beta^{\prime}=\sum_{i=1}^{p}\beta\cdot 1_{\{|\beta_{i}|>\mu\}}$, where $\mu=\sqrt{\frac{\gamma}{1+\delta_{k}^{A}}}$. Then

Therefore, we have proved (12) in the event that $\|A^{T}z\|_{\infty}\leq\lambda/2$. $\square$

Proof of Theorem 2.2. For any $\varepsilon>0$ and $k\geq 5/\varepsilon$, suppose $p\geq 2tk$, $m^{\prime}=((t-1)+\sqrt{t(t-1)})k$, $m$ is the largest integer strictly smaller than $m^{\prime}$. Then $m<m^{\prime}$ and $m^{\prime}-m\leq 1$. Since $t\geq 4/3$, we have $m^{\prime}\geq k$. Define

Now for all $\lceil tk\rceil$-sparse vector $\beta$,

Since $\beta$ is $\lceil tk\rceil$-sparse, by Cauchy-Schwarz Inequality,

We used the fact that $m^{\prime}\geq k$, $0<m^{\prime}-m\leq 1$ and

which implies $\delta_{tk}^{A}\leq\sqrt{(t-1)/t}+\varepsilon$.

Note that $A\beta_{1}=0$, so $A\beta_{0}=A\gamma_{0}$. Besides, $\beta_{0}$ is $k$-sparse and $\|\gamma_{0}\|_{1}<\|\beta_{0}\|_{1}$.

Proof of Proposition 4.1. We use the technical tools developed in Cai and Zhang to prove this result. We begin by introducing another important concept in the RIP framework - restricted orthogonal constants (ROC) proposed in .

is a sufficient condition for exact recovery of all $k$-sparse vectors. By Lemma 3.1 in , $\theta_{tk,tk}^{A}\leq 2\delta_{tk}^{A}$ when $tk$ is even; $\theta_{tk,tk}^{A}\leq\frac{2tk}{\sqrt{(tk)^{2}-1}}\delta_{tk}^{A}$ when $tk$ is odd. Hence,

The proposition is implied by the inequalities above and (31). $\square$

Proof of Proposition 4.2. The idea of the proof is quite similar to Theorem 3.2 by Cai and Zhang . Define

We can immediately see $\|A\beta\|_{2}^{2}\leq(1+t/(4-t))\|\beta\|_{2}^{2}$. On the other hand by Cauchy-Schwarz’s inequality,

Therefore, we must have $\delta_{tk}^{A}=\delta_{\lceil tk\rceil}^{A}<t/(4-t)+\varepsilon$.

Then $\beta_{0},\beta_{0}^{\prime}$ are both $k$-sparse, and $y=A\beta_{0}=A\beta_{0}^{\prime}$. There’s no way to recover both $\beta_{0},\beta_{0}^{\prime}$ only from $(y,A)$. $\square$

References