# A Simple Gaussian Measurement Bound for Exact Recovery of Block-Sparse Signals

Authors: Zhi Han; Jianjun Wang; Jia Jing; Hai Zhang
Journal: Discrete Dynamics in Nature and Society
 (2014)

---

## Abstract

We present a probabilistic analysis on conditions of the exact recovery of block-sparse signals whose nonzero elements appear in fixed blocks. We mainly derive a simple lower bound on the necessary number of Gaussian measurements for exact recovery of such block-sparse signals via the mixedl2/lq(0<q≤1) norm minimization method. In addition, we present numerical examples to partially support the correctness of the theoretical results. The obtained results extend those known for the standard lq minimization and the mixed l2/l1 minimization methods to the mixed l2/lq(0<q≤1) minimization method in the context of block-sparse signal recovery.


---

## Body

## 1. Introduction and Main Results

The problem of block-sparse signal recovery naturally arises in a number of genetics, image processing, and machine learning tasks. Prominent examples include DNA microarrays [1], wavelet sparsity modeling [2], color imaging [3], and wideband spectrum sensing [4]. In these contexts, we often require to recover an unknown signal x∈RN from an underdetermined system of linear equations y=Φx, where y∈RM are available measurements and Φ is a M×N(M<N) measurement matrix. Unlike previous works in compressed sensing (CS) [5–7], the unknown signal x not only is sparse but also exhibits additional structure in the form where the nonzero coefficients appear in some fixed blocks. We refer to such a structured sparse vector as block-sparse signal in this paper. Following [8–11], we only consider the nonoverlapping case in the present study. Thus, from mathematical point, a block signal x∈RN can be viewed as concatenation of x in m blocks of length d; that is,
(1)x=x1⋯xd︸x1xd+1⋯x2d︸x2⋯xN-d+1⋯xN︸xmT,
where x[i] denotes the ith block of x and N=md (m,d∈Z+). In these terms, we say that x is block k-sparse if x[i] has nonzero Euclidean norm for at most k blocks. In this paper, we furthermore assume that each element in these k nonzero blocks has nonzero coefficient. Obviously, if d=1, the block-sparse signal degenerates to the conventional sparse signal well studied in compressed sensing.Denote(2)x2,0=∑i=1m‍Ixi2>0,whereI(∥x[i]∥2>0) is an indicator function; that is, I(xi2>0)=1, if xi2>0; I(xi2>0)=0, otherwise. Thus a block k-sparse signal x can be defined as a signal that satisfies x2,0≤k. It is known that, under certain conditions on measurement matrix Φ (i.e., [8]), there is a unique block-sparse signal that obeys the observation y=Φx and can be exactly recovered by solving the problem
(3)min⁡xx2,0s.t.y=Φx.Similar to the standardl0 minimization problem, (3) is NP-hard and computationally intractable except for very small size. Motivated by the study of CS, one then commonly uses the strategy to replace the l2/l0 norm with its closest convex surrogate l2/l1 norm, thus to solve a mixed l2/l1 norm minimization problem:
(4)min⁡xx2,1s.t.y=Φx,
where x2,1=∑i=1mx[i]2. This model can be treated as a second-order cone program (SOCP) problem and many standard software packages can be used for the solutions very efficiently. In many practical cases, the measurements y are corrupted by bounded noise; then we can apply the modified SOCP or the group version of basis pursuit denoising (BPDN, [12]) program as the following:
(5)min⁡xy-Φx22+λx2,1,
where λ is a tuning parameter, which controls the tolerance of the noise term. There are also many methods to solve this optimization problem efficiently, such as the block-coordinate descent technique [13] and the Landweber iterations technique [14]. Conditions under which solving problem (4) can successfully recover a block-sparse signal x have been extensively studied [8, 10, 15]. For example, Eldar and Mishali [8] generalized the conventional RIP notion to the block-sparse setting and showed that if Φ satisfies the block-RIP (see Definition 1) with constant δ2k<0.414, solving (4) can accurately get any block-sparse solution of y=Φx.Among the latest researches in compressed sensing, many authors [16–21] have showed that lq minimization with 0<q<1 allows the exact recovery of conventional sparse signals from much fewer linear measurements than that by l1 minimization. Naturally, it would be interesting to make an ongoing effort to extend lq(0<q<1) minimization to the setting of block-sparsity. Specifically, the following mixed l2/lq(0<q≤1) norm minimization problem is proposed (see [11])
(6)min⁡xx2,qqs.t.y=Φx,for block-sparse signal recovery, as a generalization of the standardlq minimization, where x2,q=(∑i=1mx[i]2q)1/q. Similar to the standard lq minimization problem, (6) is also a nonconvex problem for any 0<q<1, and finding its global minimizer is in general computationally impossible. However, it is well known that there are several efficient heuristic methods to compute local minimizers of the standard lq(0<q≤1) minimization problem; say, for example, [18, 22]. One can generalize those approaches to solve the mixed l2/lq minimization problem (6). In particular, we will adopt the iteratively reweighted least squares techniques in this paper.In [17], Chartrand and Staneva conducted a detailed analysis of the lq(0<q≤1) minimization approach for the nonblock sparse recovery problem. They derived a lower bound of Gaussian measurement for exact recovery of a nonblock sparse signal. Furthermore, Eldar and Mishali [8] also provided a lower bound on block-sparse signal recovery in the Gaussian measurement ensemble for the mixed l2/l1 minimization. Along this line, we will provide in this paper a lower bound of Gaussian measurements for exact recovery of block-sparse signal through the mixed l2/lq(0<q≤1) norm minimization. The obtained results will complement the results of [8, 17] and demonstrate particularly that the block version of lq(0<q≤1) minimization can reduce the number of Gaussian measurements necessary for the exact recovery as q decreases.To introduce our results, we first state the definition of block-RIP [8] as follows.Definition 1 (see [8]).
LetΦ:RN→RM be an M×N measurement matrix. One says that Φ has the block-RIP over I={d1=d,…,dm=d} (then N=md) with constant δk|I if for every block k-sparse signal x∈RN over I such that
(7)1-δk|Ix22≤Φx22≤1+δk|Ix22.This new definition of block-RIP is crucial for our analysis of the mixedl2/lq(0<q≤1) minimization method. For convenience, we still use δk instead of δk|I, henceforth to represent the block-RIP constant of order k. With this notion, we can prove the following sufficient condition for exact recovery of a block k-sparse signal.Theorem 2.
Letx∈RN be an arbitrary block k-sparse signal. For any given q∈(0,1], if the measurement matrix Φ∈RM×N has the block-RIP (7) with constant
(8)δ2k<12-q423-q32/q-1,
then the mixedl2/lq minimization problem (6) has a unique solution, given by the original signal x.Condition (8) generalizes the condition of the mixed l2/l1 case in [8] to the mixed l2/lq(0<q≤1) case. Note that the right-hand side of (8) is monotonically decreasing with q, which shows that decreasing q can get weaker recovery condition. This shows further that fewer measurements might be needed to recover a block k-sparse signal whenever the mixed l2/lq (0<q<1) minimization methods are used instead of the mixed l2/l1 minimization method. For clarifying this issue more precisely, we can adopt a similar probabilistic method of [17] to derive a simple lower bound on how many random Gaussian measurements are sufficient for (8) to hold with high probability. The result to be verified is in Section 3.Theorem 3.
LetΦ be a M×N matrix with i.i.d. zero-mean unit variance Gaussian entries and N=md for some integer m. For any given q∈(0,1], if
(9)M≥C1qkd+C2qkdlog⁡mk,
then the subsequent conclusion is true with probability exceeding1-1/mk: Φ satisfies (8); therefore, any block k-sparse signal x∈RN can be recovered exactly by the solution of the mixed l2/lq minimization problem (6).Theorem3 shows that a block k-sparse signal x can be recovered exactly with high probability by solving the mixed l2/lq minimization (6) provided the number of Gaussian measurements M satisfies
(10)M≈C2qklog⁡mk.More detailed remarks on this bound will be presented in Section3.The rest of the paper is organized as follows. In Section2, we present several key lemmas needed for the proofs of our main results. All these lemmas can be regarded as generalizations of the standard non-block-sparse case to the block-sparse case. The proofs of Theorems 2 and 3 are given in Section 3. Numerical experiments are provided in Section 4 to demonstrate the correctness of the theoretical results. We conclude the paper then in Section 5 with some useful remarks.


## 2. Fundamental Lemmas

In this section, we establish several lemmas necessary for the proofs of the main results.Lemma 4 (see [8]).
Consider(11)Φx,Φx′≤δk+k′x2x′2,
for allx, x′ supported on disjoint subsets T,T′⊆{1,2,…,N} with |T|<k, |T′|<k′.In the next lemma, we show that the probability that block restricted isometry constantδk exceeds a certain scope decays exponentially in certain length of x.Lemma 5 (see [8]).
SupposeΦ is an M×N matrix from the Gaussian ensemble; namely, Φij~N(0,1/M). Let δk|I be the smallest value satisfying the block-RIP of Φ over I={d1=d,d2=d,…,dm=d} and N=md for some integer m. Then, for every ϵ>0, the block restricted isometry constant δk|I satisfies the following inequality:
(12)1+δk|I>1+1+ϵNMkdN+2dHkdN
which holds with high probability2e-mH(kd/N)ϵ, where H(p)=-plog⁡(p)-(1-p)log⁡(1-p)(0<p<1).Lemma 6.
SupposeΦ is an M×N matrix from the Gaussian ensemble; namely, Φij~N(0,1/M). For any 0<δ<1, the following estimation
(13)1-δx22≤Φx22≤1+δx22
holds uniformly forx∈RL with probability exceeding 1-2(12/δ)Le-M(1+δ/2)mH(k/m)/k.Proof.
Note that [23] has verified the subsequent conclusion: if Φ is a random matrix of size M×N drawn according to a distribution that satisfies the concentration inequality P(Φx22-x22≥βx22)≤2e-Mc0(β), where c0(β) is a constant dependent only on β such that c0(β)>0 for 0<β<1, then, for any set T with |T|=k<n and any 0<δ<1, there holds the estimation
(14)1-δx2≤Φ2≤1+δx2x∈T
with probability exceeding1-2(12/δ)ke-Mc0(δ/2). By Lemma 5, the concentration inequality is clearly true for Gaussian measurement matrix. Thus Lemma 6 follows.We also need the following inequality.Lemma 7 (see [24]).
For any fixedq∈(0,1) and x∈RN,
(15)x2≤xqN1/q-1/2+Nmax⁡1≤i≤Nxi-min⁡1≤i≤Nxi.


## 3. Proofs of Theorems

With the preparations made in the last section, we now prove the main results of the paper. Henceforth, we letΦ denote an M×N matrix whose elements are i.i.d. random variables; specifically, Φij~N(0,1/M). We prove Theorem 2 by using the block-RIP and Lemmas 4 and 7.Proof of Theorem2.
First notice that assumption (8) implies δ2k<1 and further implies the uniqueness of x satisfying the observation y=Φx. Let x*=x+h be a solution of (6). Our goal is then to show that h=0. For this purpose, we let xT be the signal that is identical to x on the index set T and to zero elsewhere. Let T0 be the block index set over the k nonzero blocks of x, and we decompose h into a series of vectors hT0,hT1,hT2,…,hTJ such that
(16)h=∑iJ‍hTi.
HerehTi is the restriction of h onto the set Ti and each Ti consists of k blocks (except possibly TJ). Rearrange the block indices such that hTj12≥hTj22≥⋯≥hTjk2≥hTj+112≥hTj+1[2]2≥⋯, for any j≥1.
From [9], x* is the unique sparse solution of (6) being equal to x if and only if
(17)hT02,q<hT0c2,q
for all nonzero signalh in the null space of Φ. This is the so-called the null space property (NSP). In order to characterize the NSP more precisely, we consider the following equivalent form: there exists a constant γ(h,q) satisfying 0<γ(h,q)<1 such that
(18)hT02,q=γh,qhT0c2,q.
We proceed by showing thatγ(h,q)<1 under the assumption of Theorem 2.
In effect, we observe that(19)h2=hT0⋃‍T1+h(T0⋃‍T1)c2≤hT0⋃‍T12+h(T0⋃‍T1)c2.
For anyj≥2, if we denote dj=(hTj[1]2, hTj[2]2,…, hTj[k]2), then we have
(20)dj2=∑i=1k‍hTji221/2=hTj2,djq=∑i=1k‍hTji2q1/q=hTj2,q,max⁡1≤i≤kdji=max⁡1≤i≤khTji2=hTj∞,T,min⁡1≤i≤kdji=min⁡1≤i≤khTji2.
By Lemma7, we thus have
(21)∑j≥2‍dj2≤q1/22-q1/q-1/221/q-1k1/q-1/2∑j≥1‍djq;
that is,(22)∑j≥2‍hTj2≤q1/22-q1/q-1/221/q-1k1/q-1/2∑j≥1‍hTj2,q≤q1/22-q1/q-1/221/q-1k1/q-1/2∑j≥1‍hTj2,qq1/q.
On the other hand, let(23)hT02,q=γh,qhT0c2,q,hT12,qq=t∑i≥1‍hTi2,qq.
It is easy to see that(24)∑i≥2hTi22‍≤hT212,q2-q∑j≥2hTj2,qq≤hT112q+hT122q+⋯+hT1k2qk(2-q)/q×∑j≥2hTj2,qq=hT12,qqk(2-q)/q∑j≥2hTj2,qq=hT12,qqk(2-q)/q∑j≥1hTj2,qq-hT12,qq=hT12,qqk(2-q)/q1thT12,qq-hT12,qq=1-ttk(2-q)/qhT12,q2=1-tt1-2/qk(2-q)/q∑j≥1hTj2,qq2/q.
SinceΦx=Φx*, we have Φh=0, which means Φ(hT0+hT1)=-Φ(∑j≥2hTj). By the definition of block-RIP, Lemma 4, (22), and (24), it then follows that
(25)Φ∑j≥2hTj22=∑i,j≥2ΦhTi,ΦhTj‍=∑j≥2ΦhTj,ΦhTj+2∑i,j≥2,i<jΦhTi,ΦhTj‍≤1+δk∑j≥2hTj22+2δ2k∑i>j≥2hTi2hTj2≤∑j≥2hTj22+δ2k∑i≥2hTi22≤1-tt1-2/qk(2-q)/q+δ2kq2-q2/q-122/q-2k2/q-1∑j≥1hTj2,qq2/q.
By the definition of block-RIPδ2k and by using Hölder’s equality, we then get
(26)ΦhT0+hT122≥1-δ2khT0+hT122=1-δ2khT022+hT122≥1-δ2kk1-2/qhT02,q2+k1-2/qhT12,q2=1-δ2kk1-2/q×γh,q2hT0c2,q2/q+t2/q∑i≥1hTi2,qq2/q=1-δ2kk1-2/qγh,q2+t2/q∑i≥1hTi2,qq2/q.
This together with (24) and (25) implies
(27)γh,q2≤1-t/t1-2/q+q2-q2/q-1/22/q-2δ2k1-δ2k-t2/q≐ft.
Through a straightforward calculation, one can check that the maximum off(t) occurs at t0=(1-q/2)/(2-δ2k) and
(28)ft0=1-q/22/q-11-δ2kq22-δ2k2/q-1+2qδ2k.
Iff(t0)<1, then we clearly have γ(h,q)<1 and finish the proof. However, f(t0)<1 gives that
(29)δ2k2-q2-δ2k+q1-q/22-δ2k2/q<2-q2-δ2k1-δ2k
or, equivalently,(30)2δ2k-12-δ2k2/q-1+122/qq2-q2/q-1<0.
Note that (30) implies 0<δ2k<1/2 and
(31)2δ2k-12-δ2k2/q-1+122/qq2-q2/q-1<2δ2k-1322/q-1+122/qq2-q2/q-1.
By simple calculations, we can check that, for any givenq∈(0,1], inequality (30) is true as long as
(32)δ2k<12-q423-q32/q-1;
that is, condition (8) is satisfied. With this, the proof of Theorem 2 is completed.Now we adopt the probabilistic methods to analyze how condition (8) can be satisfied; particularly, how many measurements are needed for exact recovery of a block k-sparse signal.Proof of Theorem3.
From Theorem2, we only need to show that, under condition (9), (8) holds with high probability. In particular, we will proceed to determine how random Gaussian measurements are sufficient for exact recovery of block k-sparse signals with a failure probability at most 1/mk. To this end, we let L=2kd. Then by Lemma 6, an upper bound for the probability that any M×L submatrix of Φ fails to satisfy the block-RIP (30) is
(33)m2k212δ2kLe-M1+δ2k/2mHk/m/k.
By inequality1/mk≥kk/mkek, it suffices to show that we can have the following estimation:
(34)12δ2kLe-M1+δ2k/2mHk/m/k≤kk2mkek2k2km2ke2k.
So by a simple calculation,(35)M≥11+δ2k/2m/kHk/m×Llog⁡12δ2k+3klog⁡mk+3-2ln⁡2k+ln⁡2≥C1qkd+C2qklog⁡mk,
where C1(q)=3-log⁡2+dlog⁡12/(1/2-(q/4)(2/3-q/3)2/q-1)/(1+1/4-q/82/3-q/32/q-1)m/kHk/m,  C2(q)=3/(1+1/4-q/82/3-q/32/q-1)m/kHk/m. That is, (35) is satisfied as long as (9) is met. This justifies Theorem 3.Remark 8.
From the right-hand side of (35), we can further see that, except the first term related to m/k, other terms in the numerator are only related to k and d, that is, to the numbers of nonzero blocks and the block size. Obviously, those terms have a smaller contribution to the number of measurements. Basically, Theorem 3 shows that the signal x with block-sparsity x2,0≤k can be recovered exactly by the solution of the mixed l2/lq minimization (6) with high probability provided roughly
(36)M≈C2qklog⁡mk.Obviously, this result generalizes the well-known result in [8] on the Gaussian ensemble for the mixed l2/l1 minimization. We can further see from Theorem 3 that, when specified to q=1, the bound (36) has the same order as Eldar’s result (O(klog⁡(m/k)), see [8]). It is also obvious that C(q) is monotonically increasing with respect to q∈(0,1], which then implies that decreasing q allows fewer necessary measurements for exact recovery of block-sparse signals by the mixed l2/lq minimization method. Since, when block size d=1, the mixed l2/lq minimization method degenerates to the standard lq minimization method, the presented result then provides a theoretical support to such experimental observation reported in the following section.


## 4. Numerical Experiments

In this section, we conduct two numerical experiments to support the correctness of the obtained theoretical results. Iteratively reweighted least squares (IRLS) method has been proved to be very efficient for the standardlq minimization. Thus, in the experiments, we adopted IRLS method to solve the following unconstrained smoothed version of (6):
(37)min⁡xx2,qϵ,q+12τy-Φx22,
where τ is a regularization parameter and x2,qϵ,q=∑i=1m(x[i]22+ϵ2)q/2. Note that, through defining a diagonal weighting matrix W as Wi=diag⁡(q1/2(ϵ2+x[i]22)q/4-1/2), (37) can be transformed to the following weighted least squares minimization problem:
(38)12τy-Φx22+12Wx22.With this, the IRLS algorithm we used can be summarized as follows (more details can be found in [11]).Step 1.
Set the iteration countt to zero and ϵ0=1. Initialize x(0)=min⁡⁡y-Φx22.Step 2.
Let(39)Wt=diag⁡q1/2ϵt2+xti221/2-q/4,i=1,…,m,
and update(40)xt+1=Wt-1ΦWt-1Txt+1=×ΦWt-1+τI-1ΦWt-1Ty,ϵt+1=ϵt10.Step 3.
Terminate the iteration on convergence or whent attains a specified maximum number tmax⁡.Otherwise, sett=t+1 and go to Step 2.The above algorithm can be seen as a natural generalization of general sparse signal recovery algorithm to the block-sparse setting, which alternates between estimatingx and redefining the weighting matrix W. Though this algorithm is for the unconstrained penalized problem (37), it can still give a good estimation on the minimum of the constrained problem (6) when we choose a sufficient small τ (such as τ=10-6). In the following experiments, we set τ=10-6 and terminate the algorithm if ϵ<10-7 or x(t+1)-x(t)2<10-8.In our first experiment, we took the signal lengthN=128, the block size d=4, and the block-sparsity k=6. For independent 100 trails, we first randomly generated the block-sparse signal x with values from a Gaussian distribution of mean 0 and standard deviation 1, and then we randomly drew a measurement matrix Φ from Gaussian ensemble. We also took the number of measurements varying from 24 to 124. The purpose of the experiment was then to check the correctness of Theorem 3. We considered four different values of q=0.1,0.5,0.7,1 for both the mixed l2/lq minimization method and the standard lq minimization method.The experiment result is shown in Figure1. It is seen from Figure 1 that, for all the experiment runs, the smaller q requires the smaller number of measurements for exact recovery of block sparse signals. This observation is consistent with Theorem 3. On the other hand, for a fixed q, the mixed l2/lq method is clearly superior to the standard lq method in this block-sparse setting. For instance, the mixed l2/lq method with q=0.1 only uses 50 Gaussian measurements for the exact recovery, while the number of measurements needed for lq method is around 90. This observation also partially supports the theoretical assertion of Theorem 3, namely, that incorporating the block structure into recovery method requires fewer measurements for exact recovery.Figure 1
Plots of the exact recovery frequency versus the number of measurements, for the use of the mixedl2/lq and the standard lq minimization methods with different values of q.In our second experiment, we further studied the effect of block sized for block-sparse signal recovery. We set N=256 and drew a measurement matrix of size 128×256 from Gaussian ensemble. In this experiment, the block size d was changed while keeping the total sparsity kd=64 fixed. Figure 2 shows the average root mean squares error (RMSE). Here RMSR is defined as ∑i=1N(xi-x^i)2/N in the logarithmic scale over 100 independent random runs. One can easily see from Figure 2 that the recovery performance for the standard lq method is independent of the active block number k, while the recovery errors for the mixed l2/lq method are significantly better than the standard lq method when the active block number k is far smaller than the total signal sparsity kd. Since the total sparsity kd is fixed and larger d leads to smaller k, as predicted by Theorem 3, the necessary measurement number needed for exact recovery of a block k-sparse signal by the mixed method is also reduced. This also demonstrates the advantage of the mixed l2/lq method over the standard lq method.Figure 2
Plots of average RMSE (log-scale) versus block size, for the use of the mixedl2/lq and the standard lq minimization methods with different values of q.


## 5. Conclusion

In this paper, the number of Gaussian measurements necessary for the exact recovery of a block-sparse signal by the mixedl2/lq(0<q≤1) norm minimization has been studied. The main contribution is the derivation of a lower bound on the necessary number of Gaussian measurements for the exact recovery based on a probabilistic analysis with block-RIP. The obtained results are helpful for understanding the recovery capability and algorithm development of the mixed l2/lq norm minimization approach for sparse recovery and, particularly, facilitate the applications in the development of block-sparse information processing.



---

*Source: 104709-2014-11-26.xml*