# A Note on Block-Sparse Signal Recovery with Coherent Tight Frames

Authors: Yao Wang; Jianjun Wang; Zongben Xu
Journal: Discrete Dynamics in Nature and Society
 (2013)

---

## Abstract

This note discusses the recovery of signals from undersampled data in the situation that such signals are nearly block sparse in terms of an overcomplete and coherent tight frameD. By introducing the notion of block D-restricted isometry property (D-RIP), we establish several sufficient conditions for the proposed mixed l2/l1-analysis method to guarantee stable recovery of nearly block-sparse signals in terms of D. One of the main results of this note shows that if the measurement matrix satisfies the block D-RIP with constants δk<0.307, then the signals which are nearly block k-sparse in terms of D can be stably recovered via mixed l2/l1-analysis in the presence of noise.


---

## Body

## 1. Introduction

Compressed sensing (CS) [1, 2] has attracted great interests in a number of fields including information processing, electrical engineering, and statistics. In principle, CS theory states that it is possible to recover an unknown signal from considerably few information if the unknown signal has a sparse or nearly sparse representation in an orthonormal basis. However, a large number of applications in signal and image processing point to problems where signals are not sparse in an orthogonal basis but in an overcomplete and tight frame; see, for example, [3, 4] and the reference therein. Examples include the reflected radar and sonar signals (Gabor frames) and the images with curves (curvelet frames). In such contexts, the signal f∈ℝN can be expressed as f=Dx, where D∈ℝN×d (d≥N) is a matrix whose d columns D1,…,Dd form a tight frame and x∈ℝd is sparse or nearly sparse. Then one acquires f via the observed few linear measurements y=Φf+z, where Φ is a known M×N matrix (M<N), y∈ℝM are available measurements, and z∈ℝM is a vector of measurements error.There are two common ways to recoverf based on y and Φ. One natural way is first solving an l1-minimization problem:
(1)minx∈ℝN∥x∥1subject  toy-ΦDx∈ℬ
to find the sparse transform coefficients x^; here ℬ is a bounded set determined by the noise structure and then reconstructing the signal y by a synthesis operation; that is, y^=Dx^. This is the so-called l1-synthesis or synthesis based method [5, 6]. Since the entries of ΦD are correlated when D is highly coherent, ΦD may no longer satisfy the standard restricted isometry property (RIP) and the mutual incoherence property (MIP) which are commonly used in the standard CS framework. Therefore, it is not easy to study the theoretical performance of the l1-synthesis method.An alternative tol1-synthesis is the l1-analysis method, which finds the estimator f^ directly by solving the following l1-minimization problem:
(2)minx∈ℝN∥D*f∥1subject  toy-Φf∈ℬ.
It has been shown that there is a remarkable difference between the two methods despite their apparent similarity [5]. To investigate the theoretical performance of l1-analysis, Candès et al. [7] introduced the definition of D-RIP: a measurement matrix Φ is said to satisfy the restricted isometry property adapted to D (abbreviated D-RIP) with constant δk if
(3)(1-δk)∥Dc∥22≤∥ΦDc∥22≤(1+δk)∥Dc∥22
holds for every vector c∈ℝd that is k-sparse. Note that it is computationally difficult to verify the D-RIP for a given deterministic matrix. But as discussed in [7], the matrices which satisfy the standard RIP requirements will also satisfy the D-RIP requirements. It has been shown that l1-analysis can recover a signal that is (nearly) sparse in terms of D with a small and zero error under various conditions on the D-RIP, such as δ2k<0.08 or δ7k<0.6 used in [7], δk<0.307 used in [8], and so forth.There are a growing number of practical scenarios in which the transform coefficientx is not only sparse, but the nonzero entries of x appear in some fixed blocks as well. Such block sparsity (in terms of D) naturally arises in MR imaging [9], color imaging [10], and source localization [11]. Mathematically, such vector can be modeled x∈ℝd over a block index set ℐ={l1,…,lm} as follows:
(4)x=[x1⋯xl1︸x[1]xl1+1⋯xl1+l2︸x[2]⋯xd-lm+1⋯xd︸x[m]]T.
Here x[i] denotes the ith subblock of x and li is the block size for the ith subblock. In this term, a vector x is called block k-sparse over index set ℐ if x[i] is nonzero for at most k indices i. Now our objective of this note is to recover an unknown signal f∈ℝN that is nearly block k-sparse in terms of D from a collection of M linear measurements y. We suggest the use of the following mixed l2/l1-analysis method to recover such signals:
(5)minf∈ℝn∥D*f∥2,1subject  toy-Φf∈ℬ.
In this note, we will consider two types of bounded noise: ℬl2={z:∥z∥2≤ϵ} and ℬl∞={z:∥D*Φ*z∥∞≤λ}. To study the performance of such method, we will introduce the definition of the block D-RIP of a measurement matrix, which is an extension of the block RIP introduced in [12].Definition 1.
LetD be an N×d matrix whose d columns form a tight frame for ℝN. An M×N measurement matrix Φ is said to satisfy the block D-RIP over ℐ={l1,…,lm} with constant δk∣ℐ if
(6)(1-δk∣ℐ)∥Dc∥22≤∥ΦDc∥22≤(1+δk∣ℐ)∥Dc∥22
holds for every vector c∈ℝd that is block k-sparse over ℐ.Note that we only require theD-RIP for block-sparse signals, which are a certain subset of K-sparse signals (K is the sum of the k largest values of li). Thus, the block D-RIP constant δk∣ℐ is typically smaller than the D-RIP constant δK. With a slight abuse of notation, we still denote δk by the block D-RIP constant δk∣ℐ without further specification. It is also computationally difficult to verify the block D-RIP for a given deterministic matrix. But using the similar arguments as those in [12], one can easily verify that random matrices with Gaussian, sub-Gaussian entries satisfy the block D-RIP with overwhelming probability. With this, we will establish some sufficient conditions for mixed l2/l1-analysis to guarantee stable recovery of the nearly block k-sparse signal f in terms of D. The main contribution of this note is to show that if the measurement matrix Φ has the block D-RIP constants δk<0.307, then the signal f can be stably recovered via mixed l2/l1-analysis in the noise case. Note that the block k-sparse signal f is also a standard K-sparse signal. Thus, from [8], f can be stably recovered via l1-analysis if Φ has the D-RIP constants δK<0.307. Since the block D-RIP constant δk is typically smaller than the D-RIP constant δK, our obtained condition is not as stringent as that obtained by l1-analysis. This reveals the advantage of mixed l2/l1-analysis over l1-analysis in the block-sparse (in terms of D) setting.In the next section, we give two key lemmas. In Section3, some new block D-RIP conditions for stable recovery of nearly block k-sparse signals (in terms of D) via mixed l2/l1-analysis are presented. We conclude this paper with some discussions on the block D-RIP bounds in Section 4.


## 2. Preliminaries

We begin with introducing the definition of blockD-restricted orthogonality constant, which is a natural extension of D-restricted orthogonality constant (D-ROC) introduced in [8].Definition 2.
The blockD-restricted orthogonality constant θk,k′∣ℐ of order k, k′, is the smallest positive number that satisfies
(7)|〈ΦDc,ΦDc′〉-〈Dc,Dc′〉|≤θk,k′∣ℐ∥c∥2∥c′∥2
for all c and c′ such that c and c′ are block k-sparse and block k′-sparse over block index set ℐ, respectively.For convenience, in the remainder of this note, we useθk,k′, instead of θk,k′∣ℐ, to represent the block D-ROC whenever the confusion is not caused. Similar to the D-RIP and the D-ROC, the following monotone properties can be easily observed:
(8)δk≤δk1,ifk≤k1≤m;θk,k′≤θk1,k1′,ifk≤k1,k′≤k1′,k1+k1′≤m.From the parallelogram and the definition of blockD-RIP, it is easy to see that
(9)|〈ΦDc,ΦDc′〉-〈Dc,Dc′〉|≤δk+k′∥Dc∥2∥Dc′∥2
for all c and c′ such that c and c′ are block k-sparse and block k′-sparse.In order to derive the main results of this note, we will introduce two useful inequalities related toθk,k′ and δk.Lemma 3.
For all nonnegative integersk,k′≤d, one has
(10)θk,k′≤δk+k′.Proof.
SinceD is a tight frame, we have ∥Dc∥2≤∥c∥2 for any vector c. Then using (9) and the definition of θk,k′, we can directly get the results.Lemma 4.
For anya≥1 and positive integers k,k′ such that ak′ is an integer, one has
(11)θk,ak′≤aθk,k′.Proof.
The proof is similar to the procedure of the proof of Lemma  1 in [13] and the proof of Lemma  2.6 in [8] with some modifications. Let c and c′ be block k-sparse and block ak′-sparse, respectively. Without loss of generality, we assume that the indices of nonzero blocks of c′ is {1,…,ak′}. For i=1,…,ak′, let ci′∈ℝd be a vector such that ci′ keeps the (imod(ak′))th, ((i+k′-1)mod(ak′))th nonzero blocks of c′ and replaces other blocks by zero. By the Cauchy-Schwarz inequality, we have
(12)|〈ΦDc,ΦDc′〉-〈Dc,Dc′〉|=|〈ΦDc,1k′ΦD∑i=1ak′ci′〉-〈Dc,1k′D∑i=1ak′‍ci′〉|≤1k′∑i=1ak′‍|〈ΦDc,ΦDci′〉-〈Dc,Dci′〉|≤1k′θk,k′∥c∥2∑i=1ak′∥ci′∥2≤1k′θk,k′∥c∥2ak′∑i=1ak′∥ci′∥22=aθk,k′∥c∥2∥c′∥2,
which yields the result.Remark 5.
Note that Lemma4 is in essence the square-root lifting inequality first introduced by Cai et al. in [13]. It is obvious that when D=I and li=1 for all i=1,…,m, Lemma 4 degenerates to Lemma  1 in [13].


## 3. Recovery via Mixedl2/l1 Analysis

In this section, we establish several blockD-RIP conditions for stable recovery of nearly block-sparse signals (in terms of D) via mixed l2/l1 analysis approach (5). In the sequel, we denote by x[k] the vector consisting of the k largest blocks over ℐ of x∈ℝd in l2 norm; that is, x[k]=arg min∥v∥2,0≤k∥x-v∥2,1, where ∥x∥2,0=∑i=1mI(∥x[i]∥2>0) and I(∥x[i]∥2>0) is an indicator function.Theorem 6.
Letk1 and k2 be positive integers such that 0≤8(k1-k)≤k2. Denote that t=k1/k2+(1/4)k1/k2-(2(k1-k))/k1k2 and γ=1-δk1-tθk1,k2. If the matrix Φ satisfies δk1+tθk1,k2<1, then the solution f^ to (5) obeys(i)
l2noise:(13)∥f^-f∥2≤221+δk1γϵ+(22θk1,k2γk2+12k1)∥D*f-(D*f)[k]∥2,1,(ii)
l∞noise:(14)∥f^-f∥2≤22k1γλ+(22θk1,k2γk2+12k1)∥D*f-(D*f)[k]∥2,1.Proof.
The proof will follow the ideas from [8, 14]. Let f^=f+h be a solution of (5), where f is the original signal. Write D*h=(c[1],…,c[d]) and rearrange the block indices such that ∥c[1]∥2≥∥c[2]∥2≥⋯∥c[d]∥2. Let T={1,2,…,k} and let Ω be the block index set over the k blocks with largest l2 norm of D*f. We represent D as a concatenation of column-blocks D[i] of size M×li:
(15)D=[D1⋯Dl1︸D[1]Dl1+1⋯Dl1+l2︸D[2]⋯Dd-lm+1⋯Dd︸D[m]],
where DT is the matrix D restricted to the column-blocks indexed by T. We use DT* to denote (DT)*. Partition {1,2,…,d} into the following sets:
(16)S0={1,2,…,k1},S1={k1+1,…,k1+k2},S2={k1+k2+1,…,k1+2k2},….
Sincef^ is a minimizer of (5), then we have
(17)∥DΩ*f∥2,1-∥DΩ*h∥2,1+∥DΩc*h∥2,1-∥DΩc*f∥2,1≤∥DΩ*(f+h)∥2,1+∥DΩc*(f+h)∥2,1=∥DΩ*f^∥2,1+∥DΩc*f^∥2,1=∥D*f^∥2,1≤∥D*f∥2,1=∥DΩ*f∥2,1+∥DΩc*f∥2,1.
This implies
(18)∥DΩc*h∥≤2∥DΩc*f∥2,1+∥DΩ*h∥2,1.
Note that∥DT*h∥2,1≥∥DΩ*h∥2,1 and ∥DTc*h∥2,1≤∥DΩc*h∥2,1, and it thus follows from (18) that
(19)∥DTc*h∥2,1-∥DT*h∥2,1≤∥DΩc*h∥2,1-∥DΩ*h∥2,1≤2∥DΩc*f∥2,1,
which leads to
(20)∥DTc*h∥2,1≤∥DT*h∥2,1+2∥DΩc*f∥2,1.
Using the inequality involving l1 and l2 norms (see Proposition  2.1 in [14]), it is easy to see that
(21)∥DSj*h∥2=(∑i=k1+(j-1)k2+1k1+jk2∥c[j]∥22)1/2≤∥DSj*h∥2,1k2+(k2(∥c[k1+(j-1)k2+1]∥200000000000000000000-∥c[k1+jk2]∥2)k2)×(4)-1
holds for any j≥1. Thus, summing these terms yields
(22)∑j≥1∥DSj*h∥2≤1k2∑j≥1∥DSj*h∥2,1+k2∥ck1+1∥24≤1k2(∥DTc*h∥2,1-(k1-k)∥ck1+1∥2)+k2∥ck1+1∥24.
This, along with (20), gives
(23)∑j≥1∥DSj*h∥2≤1k2(∥DT*h∥2,1+2∥DΩc*f∥2,1-(k1-k)∥ck1+1∥2)+k2∥ck1+1∥24≤1k2(∥DS0*h∥2,1+2∥DΩc*f∥2,1-2(k1-k)∥ck1+1∥2∥DS0*h∥2,1)+k2∥ck1+1∥24=1k2(∥DS0*h∥2,1+2∥DΩc*f∥2,1)+(k24-2(k1-k)k2)∥ck1+1∥2.
Since ∥DS0*h∥2,1≤k1∥DS0*h∥2 and ∥ck1+1∥22≤∥DS0*h∥22/k1, we can get
(24)∑j≥1∥DSj*h∥2≤t∥DS0*h∥2+2∥DΩc*f∥2,1k2.
Similar to the consequence of D-RIP (see [8]), we have
(25)〈Φh,ΦDDS0*h〉≥(1-δk1)∥DS0*h∥22-θk1,k2∥DS0*h∥2∑j≥1∥DSj*h∥2≥(1-δk1-tθk1,k2)∥DS0*h∥22-2k2θk1,k2∥DS0*h∥2∥DΩc*f∥2,1,
where, for the second inequality, we have used (24).
Letℬ={z:∥z∥2≤ϵ}. Then, by the feasibility of f^ (also see [8]), we have
(26)∥Φh∥2=∥Φf^-Φf∥2≤∥Φf-y∥2+∥Φf^-y∥2≤2ϵ.
Thus
(27)〈Φh,ΦDDS0*h〉≤∥Φh∥2∥ΦDDS0*h∥2≤2ϵ1+δk1∥DS0*h∥2.
It then follows from (25) and (27) that
(28)∥DS0*h∥2≤11-δk1-tθk1,k2×(2ϵ1+δk1+2k2θk1,k2∥DΩc*f∥2,1).
By (20), it is not hard to see that
(29)∥DS0c*h∥22≤∥DS0c*h∥2,1∥DS0*h∥2,1k1≤∥DTc*h∥2,1∥DS0*h∥2,1k1≤∥DS0*h∥2,1k1(∥DS0*h∥2,1+2∥DΩc*f∥2,1)≤∥DS0*h∥22+2∥DS0*h∥2k1∥DΩc*f∥2,1.
Consequently, we have
(30)∥h∥22=∥D*h∥22=∥DS0*h∥22+∥DS0c*h∥22≤2∥DS0*h∥22+2∥DS0*h∥2k1∥DΩc*f∥2,1.
Plugging (28) into the previously mentioned inequality and by a direct calculation, we get
(31)∥h∥22≤(22(1+δk1)1-δk1-tθk1,k2ϵ+(22θk1,k2(1-δk1-tθk1,k2)k2+12k122θk1,k2(1-δk1-tθk1,k2)k2)∥DΩc*f∥2,122(1+δk1)1-δk1-tθk1,k2)2,
which yields (13).
Forℬ={z:∥D*Φ*z∥∞≤λ}, by the feasibility of f^ (also see [8]), we have
(32)∥D*Φ*Φh∥∞≤∥D*Φ*(y-Φf)∥∞+∥D*Φ*(Φf^-y)∥∞≤2λ.
Thus, we can get
(33)〈Φh,ΦDDS0*h〉≤∥D*Φ*Φh∥∞∥DS0*h∥1≤2λk1∥DS0*h∥2.
Combining (25) with (33) and by a simple calculation, we get
(34)∥DS0*h∥2≤11-δk1-tθk1,k2(2λk1+2k2θk1,k2∥DΩc*f∥2,1).
Note that we also have (30). Plugging (34) into (30) yields
(35)∥h∥22≤(2λk11-δk1-tθk1,k2+(22θk1,k2(1-δk1-tθk1,k2)k2+12k122θk1,k2(1-δk1-tθk1,k2)k2)∥DΩc*f∥2,12λk11-δk1-tθk1,k2)2,
which leads to (14).Remark 7.
Different choices ofk1 and k2 can result in different sufficient conditions in Theorem 6. For instance, we can list some of them in Table 1. Since the condition δ2k<4/9 implies that δk+1.25θk,k<1, we get a sufficient condition that involves δ2k; that is, δ2k<4/9 is a sufficient recovery condition for mixed l2/l1-analysis (5).Table 1
Different sufficient conditions.
k
1
k
2
Recovery condition
k
k
δ
k
+
1.25
θ
k
,
k
<
1
k
4
9
k
δ
k
+
5
3
θ
k
,
(
4
/
9
)
k
<
1
9
8
k
k
δ
(
9
/
8
)
k
+
9
8
θ
k
,
(
9
/
8
)
k
<
1
k
4
k
δ
k
+
θ
k
,
4
k
<
1
8
7
k
8
7
k
δ
(
8
/
7
)
k
+
θ
(
8
/
7
)
k
+
(
8
/
7
)
k
<
1
k
2
k
δ
k
+
3
2
4
θ
k
,
2
k
<
1Remark 8.
Though we have only considered bounded noise in Theorem6, the conclusion, however, can be applied directly to Gaussian noise.Theorem 9.
If the matrixΦ satisfies the block D-RIP with δk<0.307, then the solution f^ to (5) obeys(i)
l2noise:(36)∥f^-f∥2≤10.307-δkϵ+1(0.307-δk)k∥D*f-(D*f)[k]∥2,1,(ii)
l∞noise:(37)∥f^-f∥2≤k0.307-δkλ+1(0.307-δk)k∥D*f-(D*f)[k]∥2,1.Proof.
In Theorem6, we take k1=k, 1≤k2<k. By applying Lemmas 3 and 4 and using the similar proof techniques in [14], we can immediately get the results.Remark 10.
When the block sizeli=1 for all 1≤i≤m, (36) and (37) are the same as those of Theorem  3.1 in [8].Remark 11.
When no noise is present andf is exactly block-k sparse (in terms of D), f^ recovers f exactly.


## 4. Discussion

This note has presented some conditions of the measurement matrixΦ for the mixed l2/l1-analysis method to stably recover signals which are nearly block sparse in terms of a coherent tight frame D. To the best of our knowledge, this is the first theoretical characterization of the proposed mixed l2/l1-analysis method in the compressed sensing framework. In a recent paper [15], Cai and Zhang established a sharp RIP condition for the standard sparse recovery via l1 minimization. They showed that in the noiseless case the RIP condition δk<1/3 is sharp for exact recovery of k-sparse signals via l1 minimization. One may then argue whether the block D-RIP condition δk<1/3 is also sharp for mixed l2/l1-analysis. Moreover, Davies and Gribonval [16] showed that it is impossible to recover certain standard k-sparse signals via l1 minimization under RIP condition δ2k<2/2. It is interesting to investigate whether 2/2 is also an upper bound on the block D-RIP constant δ2k for mixed l2/l1-analysis.



---

*Source: 905027-2013-12-03.xml*