Recovery analysis for weighted mixed ℓ2/ℓp minimization

arXiv:1709.00257v2 [cs.IT] 18 Oct 2017

with 0 < p ≤ 1
Zhiyong Zhou∗, Jun Yu
Department of Mathematics and Mathematical Statistics, Umeå University,
Umeå, 901 87, Sweden
October 19, 2017

Abstract: We study the recovery conditions of weighted mixed ℓ2 /ℓp (0 < p ≤ 1) minimization for block
sparse signal reconstruction from compressed measurements when partial block support information is
available. We show that the block p-restricted isometry property (RIP) can ensure the robust recovery.
Moreover, we present the sufficient and necessary condition for the recovery by using weighted block p-null
space property. The relationship between the block p-RIP and the weighted block p-null space property
has been established. Finally, we illustrate our results with a series of numerical experiments.
Keywords: Compressive sensing; Prior support information; Block sparse; Non-convex minimization.

1

Introduction

Since its advent [3–5, 10], Compressive Sensing (CS) has attracted considerable attentions (see the
monographs [13, 18] for a comprehensive view). CS aims to recover an unknown signal with underdetermined linear measurements. Specifically, the standard CS problem consists in the reconstruction of a
N -dimensional sparse or compressible signal x from a significantly fewer number of linear measurements
y = Ax + e ∈ Rm with m ≪ N and the noise e satisfying kek2 ≤ ε for some known constant ε > 0. In
fact, if the measurement matrix A satisfies the restricted isometry property (RIP) condition, the robust
recovery can be guaranteed by using the ℓ1 minimization (Chapter 6, [18])
min kzk1 , subject to ky − Azk2 ≤ ε.
z

(1)

To obtain better recovery performance, the structures and prior information of signals are incorporated
in the recovery algorithms. In this paper, we consider both cases.
As for the structure, we assume that the unknown signal x is block sparse or nearly block sparse
[11, 12, 14–16], which means that the nonzero entries of x occur in clusters. Block sparse model appears
in many practical scenarios, such as when dealing with multi-band signals [27], in measurements of gene
expression levels [30], and in colour imaging [24]. Moreover, block sparse model can be used to treat
the problems of multiple measurement vector (MMV) [8, 14, 26] and sampling signals that lie in a union
∗

Corresponding author, zhiyong.zhou@umu.se.

1

Pn
of subspaces [2, 14, 27]. With N =
i=1 di , we define the i-th block x[i] of a length-N vector x over
I = {d1 , · · · , dn }. The i-th block is of length di , and the blocks are formed sequentially so that
x = (x1 · · · xd1 xd1 +1 · · · xd1 +d2 · · · xN −dn +1 · · · xN )T .
{z
}
| {z } |
{z
} |

(2)

min kzk2,1 , subject to ky − Azk2 ≤ ε.

(3)

xT [1]

xT [n]

xT [2]

Without loss of generality, we assume that d1 = d2 = · · · = dn = d, implying that N = nd. A vector
x ∈ RN is called block k-sparse over I = {d, · · · , d} if x[i] is nonzero (i.e., kx[i]k2 > 0) for at most k indices
P
i. In other words, by denoting kxk2,0 = ni=1 I(kx[i]k2 > 0), a block k-sparse vector x can be defined by
P
kxk2,0 ≤ k. For any p > 0, we define the mixed ℓ2 /ℓp norm kxk2,p = ( ni=1 kx[i]kp2 )1/p . To make explicit use
of the block structure to achieve better sparse recovery performance, the corresponding extended version
of sparse representation algorithm has been developed, namely the mixed ℓ2 /ℓ1 minimization,
z

It was shown in [14] that if the measurement matrix A satisfies the block RIP condition which generalizes
the conventional RIP notion, then the mixed ℓ2 /ℓ1 -norm recovery algorithm is guaranteed to recover any
block sparse signal, irrespectively of the locations of the nonzero blocks. Furthermore, recovery will be
robust in the presence of noise and modeling errors (i.e., when the vector is not exactly block sparse).
Other existing recovery algorithms include group lasso [39], adaptive lasso [23], iterative reweighted ℓ2 /ℓ1
recovery algorithms [40], block version of the CoSaMP algorithm [12], and the extensions of the CoSaMP
algorithm and of the Iterative Hard Thresholding algorithm [1].
On the other hand, we also consider the case that an estimate of the block support of the signal is
available. The related literatures on signal recovery using partial support or block support information
include [19–22, 28, 29, 31–33, 38]. For an arbitrary signal x ∈ RN defined as (2), let xk be its best approximation with k nonzero blocks, so that xk minimizes kx − gk2,1 over all block k-sparse vectors g. Let T0
be the block support of xk , where T0 ⊂ {1, · · · , n} and |T0 | ≤ k. Let T̃ , the block support estimate, be a
subset of {1, 2 · · · , n} with cardinality |T̃ | = ρk, where 0 ≤ ρ ≤ a for some a > 1 and |T̃ ∩ T0 | = αρk (for
interpretation of ρ and α see Remark 1 in Section 2). To incorporate prior block support information T̃ ,
the weighted mixed ℓ2 /ℓ1 minimization

n
ω ∈ [0, 1], i ∈ T̃
X
wi kz[i]k2 , subject to ky − Azk2 ≤ ε, where wi =
min
(4)
z
1,
i ∈ T̃ c
i=1

is adopted. The main idea is to choose ω such that the ℓ2 norm of the blocks of x that are ”expected” to
be large are penalized less in the weighted objective function.
Moreover, as is shown in many literatures [6, 17, 37], ℓp -minimization with 0 < p < 1 allows exact
recovery with fewer measurements than that by ℓ1 -minimization. Thus, it is natural to adopt the nonconvex
minimization to the setting of block sparse signal reconstruction with prior block support information.
Specifically, we consider the weighted mixed ℓ2 /ℓp (0 < p ≤ 1) minimization problem:

n
ω ∈ [0, 1], i ∈ T̃
X
p
wi kz[i]k2 , subject to ky − Azk2 ≤ ε, where wi =
.
(5)
min
z
1,
i ∈ T̃ c
i=1

2

When there is no prior block support information (ω = 1), the mixed ℓ2 /ℓp (0 < p ≤ 1) minimization
problem has been studied in [34, 35]. And the case that there is partially known signal block support but
with ω = 0 was considered in [20]. We generalize the existing results to incorporating the prior known
block support information with a weight ω ∈ [0, 1]. In summary, the main contributions of our work include
the following aspects. First, we provide the recovery analysis for the weighted mixed ℓ2 /ℓp (0 < p ≤ 1)
minimization by using block p-RIP condition. This result extends the existing literatures [19, 20, 33–35].
Second, we propose the weighted block p-null space property and present the sufficient and necessary
condition for the weighted mixed ℓ2 /ℓp (0 < p ≤ 1) minimization by this new tool. Third, we establish the
relationship between block p-RIP condition and weighted block p-null space property. Finally, we illustrate
our results via a series of simulations.
The paper is organized as follows. In Section 2, we present the sufficient recovery condition by using
block p-RIP. In Section 3, we introduce the notion of weighted block p-null space property (NSP) and
establish the sufficient and necessary condition with this new tool. In Section 4, we establish the relationship
between these two conditions. In Section 5, we conduct some simulations to illustrate the theoretical results.
Section 6 is devoted to the conclusion.

2

Block p-RIP

As for the weighted mixed ℓ2 /ℓp (0 < p ≤ 1) minimization, we can obtain the reconstruction guarantees
by using block p-RIP. We begin with introducing the definition of block restricted p-isometry constant,
which is a natural extension of the conventional restricted p-isometry constant.

Definition 1 ( [7, 20, 34, 35]) Given a measurement matrix A ∈ Rm×N and 0 < p ≤ 1. Then the block
p-restricted isometry constant (RIC) δk|I over I = {d1 , · · · , dn } of order k is defined to be the smallest
positive number such that
(1 − δk|I )kxkp2 ≤ kAxkpp ≤ (1 + δk|I )kxkp2

(6)

for all x ∈ RN that are block k-sparse over I.
For convenience, we write δk for the block p-RIC δk|I whenever there is no confusion. Then, we have
the sufficient condition for the robust recovery result by using (5) with the block p-RIC δk .

Theorem 1 Let x ∈ RN , and xk be its best approximation with k nonzero blocks, supported on block
index set T0 . Let T̃ ⊂ {1, 2, · · · , n} be an arbitrary set. Define ρ and α as before such that |T̃ | = ρk and
|T̃ ∩ T0 | = αρk. Suppose that there exists an a ∈ Z, with a ≥ (1 − α)ρ, a > 1, and the measurement matrix
A satisfies
δak +

a1−p/2
a1−p/2
δ(a+1)k <
− 1,
γ
γ

3

(7)

where γ = ω + (1 − ω)(1 + ρ − 2αρ)1−p/2 for some given 0 ≤ ω ≤ 1. Then the solutions x♯ of problem (5)
obeys
kx♯ − xk2 ≤ C1



ωkx − xk kp2,p + (1 − ω)kxT̃ c ∩T c kp2,p
0

k1/p−1/2

1/p

+ C2 ε,

(8)

for some positive constants C1 and C2 .
Remark 1. Note that this theorem involves two important ratios: ρ determines the ratio of the estimated
block support size to the actual block support of xk (or the block support of x if x is block k-sparse),
while α determines the ratio of the number of block indices in block support of xk that were accurately
0|
.
estimated in T̃ to the size of T̃ . Specifically, α = |T̃|∩T
T̃ |
Remark 2. The constants C1 and C2 are explicitly given by the following expressions:


22/p−1 a1/2−1/p (1 + δak )1/p + (1 − δ(a+1)k )1/p
C1 =
,
[(1 − δ(a+1)k ) − ap/2−1 (1 + δak )γ]1/p
C2 =

21/p m1/p−1/2 (1 + a1/2−1/p γ 1/p )
.
[(1 − δ(a+1)k ) − ap/2−1 (1 + δak )γ]1/p

Remark 3. For Theorem 1 to be held, it is sufficient that A satisfies
δ(a+1)k < δ :=

a1−p/2 − [ω + (1 − ω)(1 + ρ − 2αρ)1−p/2 ]
.
a1−p/2 + [ω + (1 − ω)(1 + ρ − 2αρ)1−p/2 ]

(9)

Next, we illustrate how the slighted stronger sufficient conditions (9) vary with α and ω for p =
0.01, 0.5, 1, respectively. In Figure 1, for each p, we plot δ versus ω for different values of α, where we set
the parameters a = 3 and ρ = 1. We observe that as α increases the sufficient condition on the block p-RIC
becomes weaker (δ getting larger), allowing for a wider class of measurement matrices A. For each p with
α > 0.5, the sufficient condition becomes stronger as ω increases. For instance, when α = 0.7, p = 0.5,
with ω = 0.2 it suffices to have δ = 0.5072, compared with δ = 0.3902 for ω = 1. The opposite conclusion
holds for the case α < 0.5. When α = 0.5, the sufficient condition remains the same for different ω. From
another point of view, as p decreases, the sufficient condition becomes weaker, which reflects the benefits
of using nonconvex minimization.
Remark 4. By setting ω = 1 and a = b2/(2−p) with b > 1, this theorem reduces to Theorem 2.1 in [35].
In addition, by setting ω = 0, α = 0.5 and a = ρ = b2/(2−p) with b > 1, then this theorem goes to Theorem
2 in [20] with s = ak.
Proof. Let x♯ = x + h be a solution of problem (5), where x is the unknown true signal and h is the
approximation error. Throughout the paper, xT will denote the vector equal to x on the block index set
4

p=0.01

0.9

p=0.5

0.8

α=0.1
α=0.3
α=0.5
α=0.7
α=0.9

0.8

p=1

0.6

α=0.1
α=0.3
α=0.5
α=0.7
α=0.9

α=0.1
α=0.3
α=0.5
α=0.7
α=0.9

0.55

0.7

0.5

0.7

0.6

0.6

0.5

Block restricted p-isometry constant

Block restricted p-isometry constant

Block restricted p-isometry constant

0.45

0.5

0.4

0.4

0.35

0.3

0.25
0.4

0.3

0.3

0.2

0.2

0.15

0.2

0.1
0

0.2

0.4

0.6

0.8

1

0.1
0

0.2

Weights (ω)

0.4

0.6

0.8

1

0

0.2

0.4

Weights (ω)

0.6

0.8

1

Weights (ω)

Figure 1: Comparison of the sufficient conditions (9) for the block restricted p-isometry constants with various of α
for p = 0.01, 0.5, 1. We set a = 3 and ρ = 1 for all the figures.

T and zero elsewhere. Then, we have
ωkx♯T̃ kp2,p + kx♯T̃ c kp2,p ≤ ωkxT̃ kp2,p + kxT̃ c kp2,p .
That is,
ωkxT̃ + hT̃ kp2,p + kxT̃ c + hT̃ c kp2,p ≤ ωkxT̃ kp2,p + kxT̃ c kp2,p .
Consequently,
ωkxT̃ ∩T0 + hT̃ ∩T0 kp2,p + ωkxT̃ ∩T c + hT̃ ∩T c kp2,p + kxT̃ c ∩T0 + hT̃ c ∩T0 kp2,p + kxT̃ c ∩T c + hT̃ c ∩T c kp2,p
0

≤

ωkxT̃ ∩T0 kp2,p

+

ωkxT̃ ∩T c kp2,p
0

+

0

kxT̃ c ∩T0 kp2,p

0

+

0

kxT̃ c ∩T c kp2,p .
0

The forward and reverse triangle inequalities implies


ωkhT̃ ∩T c kp2,p + khT̃ c ∩T c kp2,p ≤ khT̃ c ∩T0 kp2,p + ωkhT̃ ∩T0 kp2,p + 2 kxT̃ c ∩T c kp2,p + ωkxT̃ ∩T c kp2,p .
0

0

0

0

Adding and subtracting ωkhT̃ c ∩T c kp2,p on the left hand side, and ωkhT̃ c ∩T0 kp2,p on the right, we obtain
0



ωkhT0c kp2,p + (1 − ω)khT̃ c ∩T c kp2,p ≤ ωkhT0 kp2,p + (1 − ω)khT̃ c ∩T0 kp2,p + 2 ωkxT0c kp2,p + (1 − ω)kxT̃ c ∩T c kp2,p .
0

0

But we can also write

khT0c kp2,p = ωkhT0c kp2,p + (1 − ω)khT̃ c ∩T c kp2,p + (1 − ω)khT̃ ∩T c kp2,p .
0

5

0

Therefore, we have


khT0c kp2,p ≤ ωkhT0 kp2,p + (1 − ω)khT̃ ∩T c kp2,p + (1 − ω)khT̃ c ∩T0 kp2,p + 2 ωkxT0c kp2,p + (1 − ω)kxT̃ c ∩T c kp2,p .
0

0

Let the set T̃α = T0 ∩ T̃ , then we can write khT̃ ∩T c kp2,p + khT̃ c ∩T0 kp2,p = kh(T0 ∪T̃ )\T̃α kp2,p and simplify the
0
bound on


khT0c kp2,p ≤ ωkhT0 kp2,p + (1 − ω)kh(T0 ∪T̃ )\T̃α kp2,p + 2 ωkxT0c kp2,p + (1 − ω)kxT̃ c ∩T c kp2,p .
(10)
0

Next, we decompose hT0c into disjoint block index set Tj , each of Tj (j ≥ 1) consists of ak blocks, where
a > 1. That is, T1 indexes the ak blocks with largest ℓ2 norm of hT0c , T2 indexes the second ak blocks with
P
largest ℓ2 norm of h(T0 ∪T1 )c , and so on. This gives hT0c =
hTj . For each i ∈ Tj (j ≥ 2), it is easy to see
j≥1

that

khTj [i]kp2

khTj−1 kp2,p
khTj−1 [i]kp2 + · · · + khTj−1 [ak]kp2
≤
=
.
ak
ak

Then
khTj [i]k22 ≤

khTj−1 k22,p

(ak)2/p
khTj−1 kp2,p
p
.
khTj k2 ≤
(ak)1−p/2

, khTj k22 ≤

akkhTj−1 k22,p
(ak)2/p

,

Thus,
X
X
X
X
khTj k2,p .
khTj−1 k2,p = (ak)1/2−1/p
kh(T0 ∪T1 )c k2 ≤ k
hTj k2 ≤
khTj k2 ≤ (ak)1/2−1/p
j≥2

j≥1

j≥2

j≥2

Hence,

p
X
X
kh(T0 ∪T1 )c kp2 ≤ (ak)p/2−1  khTj k2,p  ≤ (ak)p/2−1
khTj kp2,p = (ak)p/2−1 khT0c kp2,p .
j≥1

j≥1

Combining the above expression with (10), we get
"
kh(T0 ∪T1 )c kp2 ≤ (ak)p/2−1

#


ωkhT0 kp2,p + (1 − ω)kh(T0 ∪T̃ )\T̃α kp2,p + 2 ωkxT0c kp2,p + (1 − ω)kxT̃ c ∩T c kp2,p .
0

(11)

By Hölder’s inequality it follows that
kAhkpp ≤

m
X
i=1

(|(Ah)i |p )2/p

!p/2

·

m
X
i=1

!1−p/2

1

= m1−p/2 kAhkp2 .

Since x♯ is a solution of problem (5) and ky − Axk2 = kek2 ≤ ε, so we have
kAhk2 = kA(x♯ − x)k2 ≤ kAx − yk2 + kAx♯ − yk2 ≤ 2ε.

6

Thus, kAhkpp ≤ m1−p/2 kAhkp2 ≤ m1−p/2 (2ε)p . Therefore, we obtain
kAhT0 ∪T1 kpp ≤ kAhkpp + kAh(T0 ∪T1 )c kpp ≤ m1−p/2 (2ε)p +

X
kAhTj kpp
j≥2

≤m

1−p/2

X
(2ε) + (1 + δak )
khTj kp2 .
p

j≥2

Moreover, we have

X
X
khTj−1 kp2,p ≤ (ak)p/2−1 khT0c kp2,p .
khTj kp2 ≤ (ak)p/2−1
j≥2

j≥2

Hence
kAhT0 ∪T1 kpp ≤ m1−p/2 (2ε)p + (ak)p/2−1 (1 + δak )khT0c kp2,p


≤ m1−p/2 (2ε)p + 2(ak)p/2−1 (1 + δak ) ωkxT0c kp2,p + (1 − ω)kxT̃ c ∩T c kp2,p
0

p/2−1

+ ω(ak)

(1 +

δak )khT0 kp2,p

p/2−1

+ (1 − ω)(ak)

(1 + δak )kh(T0 ∪T̃ )\T̃α kp2,p .

Noting that |(T0 ∪ T̃ )\ T̃α | = (1+ρ−2αρ)k, we obtain kh(T0 ∪T̃ )\T̃α kp2,p ≤ [(1 + ρ − 2αρ)k]1−p/2 kh(T0 ∪T̃ )\T̃α kp2 .
Since the set T1 contains the ak blocks with largest ℓ2 norm of hT0c with a > 1, and |T̃ \ T̃α | = (1−α)ρk ≤ ak,
it follows that kh(T0 ∪T̃ )\T̃α kp2 ≤ khT0 ∪T1 kp2 , which implies that kh(T0 ∪T̃ )\T̃α kp2,p ≤ [(1 + ρ − 2αρ)k]1−p/2 khT0 ∪T1 kp2 .
In addition, khT0 kp2,p ≤ k1−p/2 khT0 kp2 ≤ k1−p/2 khT0 ∪T1 kp2 . Thus,
(1 − δ(a+1)k )khT0 ∪T1 kp2 ≤ kAhT0 ∪T1 kpp


≤ m1−p/2 (2ε)p + 2(ak)p/2−1 (1 + δak ) ωkxT0c kp2,p + (1 − ω)kxT̃ c ∩T c kp2,p
0

+ ωa

p/2−1

(1 +

δak )khT0 ∪T1 kp2

+ (1 − ω)a

Therefore, if (1 − δ(a+1)k ) − ap/2−1 (1 + δak )γ > 0, that is δak +
khT0 ∪T1 kp2 ≤

p/2−1

1−p/2

(1 + ρ − 2αρ)

a1−p/2
δ(a+1)k
γ

<

a1−p/2
γ

(1 + δak )khT0 ∪T1 kp2 .

− 1, then we have



m1−p/2 (2ε)p + 2(ak)p/2−1 (1 + δak ) ωkxT0c kp2,p + (1 − ω)kxT̃ c ∩T c kp2,p
0

(1 − δ(a+1)k ) − ap/2−1 (1 + δak )γ

,

where γ = ω + (1 − ω)(1 + ρ − 2αρ)1−p/2 . According to (11), we also have


kh(T0 ∪T1 )c kp2 ≤ ap/2−1 γkhT0 ∪T1 kp2 + 2(ak)p/2−1 ωkxT0c kp2,p + (1 − ω)kxT̃ c ∩T c kp2,p
0


p
ap/2−1 γm1−p/2 (2ε)p + 2(ak)p/2−1 (1 − δ(a+1)k ) ωkxT0c k2,p + (1 − ω)kxT̃ c ∩T c kp2,p
0
≤
.
(1 − δ(a+1)k ) − ap/2−1 (1 + δak )γ
From kvkp ≤ 21/p−1 kvk1 for all v ∈ R2 , it follows that
khk2 ≤ khT0 ∪T1 k2 + kh(T0 ∪T1 )c k2


1/p 
p
p
1/p−1/2
1/p
1/2−1/p
1/p
ωkxT0c k2,p + (1 − ω)kxT̃ c ∩T c k2,p
ε + 2 (ak)
(1 + δak )

 2m
0
≤ 21/p−1 

p/2−1
1/p
[(1 − δ(a+1)k ) − a
(1 + δak )γ]
7

(12)




1/p 
p
1/2−1/p γ 1/p m1/p−1/2 ε + 21/p (ak)1/2−1/p (1 − δ
1/p ωkx c kp + (1 − ω)kx
k
2a
)
c
c
T
(a+1)k
T̃ ∩T0 2,p
0 2,p


+ 21/p−1 

p/2−1
1/p
[(1 − δ(a+1)k ) − a
(1 + δak )γ]
≤

1/p


22/p−1 (ak)1/2−1/p (1 + δak )1/p + (1 − δ(a+1)k )1/p ωkxT0c kp2,p + (1 − ω)kxT̃ c ∩T c kp2,p
0

[(1 − δ(a+1)k ) −

+

21/p m1/p−1/2 (1

+

a1/2−1/p γ 1/p )ε

[(1 − δ(a+1)k ) − ap/2−1 (1 + δak )γ]1/p

ap/2−1 (1

= C1



+ δak

)γ]1/p

ωkxT0c kp2,p + (1 − ω)kxT̃ c ∩T c kp2,p
0

k1/p−1/2

1/p

+ C2 ε,

which completes the proof.

Corollary 1 Let A ∈ Rm×N be a measurement matrix, x ∈ RN be a block k-sparse signal supported on
block index set T0 with y = Ax, and 0 < p ≤ 1. Let T̃ ⊂ {1, 2, · · · , n} be an arbitrary set. Define ρ and α
as before such that |T̃ | = ρk and |T̃ ∩ T0 | = αρk. Suppose that there exists an a ∈ Z, with a ≥ (1 − α)ρ,
a > 1, and the measurement matrix A satisfies
δak +

a1−p/2
a1−p/2
δ(a+1)k <
− 1,
γ
γ

(13)

where γ = ω + (1 − ω)(1 + ρ − 2αρ)1−p/2 for some given 0 ≤ ω ≤ 1. Then the unique solution of problem
(5) with ε = 0 is exactly x.
Remark 5. According to the arguments in [20, 35], if we let A be an m × N matrix whose entries are i.i.d
Gaussian random variables with mean zero, then there exist C3 (p) and C4 (p) such that whenever 0 < p ≤ 1
and
m ≥ C3 (p)kd + pC4 (p)k ln(n/k),

(14)

the block p-RIP (7) will hold and the block sparse signal x can be exactly recovered with high probability.
For a given p ∈ (0, 1], C3 (p) and C4 (p) are finite constants, and the second term of (14) has the dominant
impact on the number of measurements in an asymptotic sense. When p → 0, the condition reduces to
m ≥ C3 (0)kd. While, when p = 1, the required number of measurements m ≥ C3 (1)kd + C4 (1)k ln(n/k),
which implies fewer measurements are required with smaller p for exact recovery via weighted mixed ℓ2 /ℓp
minimization than the case that p = 1. This is largely consistent with what we have mentioned in Remark
3, namely, as p decreases, the sufficient condition for the exact recovery becomes weaker. Though we have
only considered the case that d1 = d2 = · · · = dn = d, the results here can be adapted to the case in which
di are not equal via replacing d by the maximal block length max di .
1≤i≤n

3

Weighted Block p-NSP

In this section, we focus on the noise free case, that is e = 0, and the signal x is exactly block k-sparse,
supported on block index set T0 . We obtain the exact recovery condition for the problem (5) with ε = 0
by using weighted block p-null space property. For an index set V ⊂ {1, · · · , n}, we define
Γs (V ) := {U ⊂ {1, · · · , n} : |(V ∩ U c ) ∪ (V c ∩ U )| ≤ s}.
8

Basically, for any index set V , the set (V ∩ U c ) ∪ (V c ∩ U ) indicates the estimate error of U with respective
to V . So Γs (V ) includes all the index set estimates of V that own an error of size s or less.
Definition 2 Let T ⊂ {1, · · · , n} with |T | ≤ k and T̃ ∈ Γs (T ). Assume the block size equals d. A matrix
A ∈ Rm×N is said to have the weighted nonuniform block p-null space property with parameters T and T̃ ,
and constant C if for any vector h : Ah = 0, we have
ωkhT kp2,p + (1 − ω)khS kp2,p ≤ CkhT c kp2,p ,

(15)

where S = (T̃ ∩ T c ) ∪ (T̃ c ∩ T ). In this case, we say A satisfies ω-d-p-NSP(T, T̃ , C).
Next, we define a weighted uniform block p-null space property that leads to a sufficient and necessary
condition for the exact recovery of all block k-sparse signals from compressive measurements using weighted
mixed ℓ2 /ℓp minimization problem.

Definition 3 Assume the block size equals d. A matrix A ∈ Rm×N is said to have the weighted block
p-null space property with parameters k and s, and constant C if for any vector h : Ah = 0, and for every
block index set T ⊂ {1, · · · , n} with |T | ≤ k and S ⊂ {1, · · · , n} with |S| ≤ s, we have
ωkhT kp2,p + (1 − ω)khS kp2,p ≤ CkhT c kp2,p .

(16)

In this case, we say A satisfies ω-d-p-NSP(k, s, C).
Remark 6. Our notations ω-d-p-NSP(T, T̃ , C) and ω-d-p-NSP(k, s, C) are direct extensions of the recent
notations ω-NSP(T, T̃ , C) and ω-NSP(k, s, C) proposed by [25], which corresponds to the special case that
p = 1 and the block size d = 1. That’s to say ω-1-1-NSP(k, s, C) is equivalent to ω-NSP(k, s, C). Consequently, 1-1-1-NSP(k, k, C) is the standard null space property of order k, i.e, NSP(k, C).
The following theorem presents the sufficient and necessary condition for weighted mixed ℓ2 /ℓp minimization problem to recover all block k-sparse signals when the error in the block support estimate is of
size s or less.
Theorem 2 Assume the block size equals d. Given a matrix A ∈ Rm×N , every block k-sparse signal
x ∈ RN , supported on block index set T0 , is the unique solution of the weighted mixed ℓ2 /ℓp , 0 < p ≤ 1
norm minimization problem (5) with ε = 0 and T̃ = Γs (T0 ), if and only if A satisfies ω-d-p-NSP(k, s, C)
for some positive constant C < 1.
Proof. a) ” ⇒ ”. Assume if A does not satisfy ω-d-p-NSP(k, s, C) for any constant C > 1, then there
exists a vector h : Ah = 0 and block index set T with |T | ≤ k and block index set S with |S| ≤ s, such
that AhT = −AhT c and
ωkhT kp2,p + (1 − ω)khS kp2,p ≥ khT c kp2,p .
Define T̃ = (T c ∩ S) ∪ (T ∩ S c ) so that S = (T ∩ T̃ c ) ∪ (T c ∩ T̃ ). Substituting for S and splitting the set
T , we obtain




ω khT ∩T̃ c kp2,p + khT ∩T̃ kp2,p + (1 − ω) khT ∩T̃ c kp2,p + khT c ∩T̃ kp2,p
9

= khT ∩T̃ c kp2,p + ωkhT ∩T̃ kp2,p + (1 − ω)khT c ∩T̃ kp2,p ≥ khT c kp2,p .
Then, we have
ωkhT ∩T̃ kp2,p + khT ∩T̃ c kp2,p ≥ ωkhT c ∩T̃ kp2,p + khT c ∩T̃ c kp2,p .
In other words, the weighted mixed ℓ2 /ℓp norm of the vector hT equals or exceeds that of −hT c . So hT is
not the unique minimizer, which is contradictory to our condition. Thus, the necessity is verified.
b) ” ⇐ ”. Let x♯ be a minimizer of weighted mixed ℓ2 /ℓp , 0 < p ≤ 1 norm minimization problem (5)
with ε = 0 and T̃ = Γs (T0 ) and define h = x♯ − x. Then, by the optimality of x♯ , we have
ωkxT̃ + hT̃ kp2,p + kxT̃ c + hT̃ c kp2,p ≤ ωkxT̃ kp2,p + kxT̃ c kp2,p ,
which is equivalent to
ωkxT̃ ∩T0 + hT̃ ∩T0 kp2,p + ωkxT̃ ∩T c + hT̃ ∩T c kp2,p + kxT̃ c ∩T0 + hT̃ c ∩T0 kp2,p + kxT̃ c ∩T c + hT̃ c ∩T c kp2,p
0

≤

ωkxT̃ ∩T0 kp2,p

ωkxT̃ ∩T c kp2,p
0

+

+

0

0

kxT̃ c ∩T0 kp2,p

+

0

kxT̃ c ∩T c kp2,p .
0

Since x is strictly block k-sparse and supported on the block index set T0 , thus xT0c = 0. Then we have
ωkhT̃ ∩T c kp2,p + khT̃ c ∩T c kp2,p ≤ khT̃ c ∩T0 kp2,p + ωkhT̃ ∩T0 kp2,p .
0

0

Adding and subtracting ωkhT̃ c ∩T c kp2,p on the left hand side, and ωkhT̃ c ∩T0 kp2,p on the right, we obtain
0

ωkhT̃ ∩T c kp2,p + ωkhT̃ c ∩T c kp2,p + khT̃ c ∩T c kp2,p − ωkhT̃ c ∩T c kp2,p
≤

ωkhT̃ ∩T0 kp2,p

+

0

0

0

0

ωkhT̃ c ∩T0 kp2,p

+ khT̃ c ∩T0 kp2,p

− ωkhT̃ c ∩T0 kp2,p .

Therefore,
ωkhT0c kp2,p + (1 − ω)khT̃ c ∩T c kp2,p ≤ ωkhT0 kp2,p + (1 − ω)khT̃ c ∩T0 kp2,p .
0

Finally, by adding (1 −

ω)khT̃ ∩T c kp2,p
0

to both sides, we have

khT0c kp2,p ≤ ωkhT0 kp2,p + (1 − ω)khT̃ ∩T c kp2,p + (1 − ω)khT̃ c ∩T c kp2,p
0

=

ωkhT0 kp2,p

+ (1 −

ω)khS kp2,p ,

0

(17)

by setting S = (T̃ ∩ T0c ) ∪ (T̃ c ∩ T0 ). Note that when |S| ≤ s, the above inequality is in contradiction with
that A satisfies ω-d-p-NSP(k, s, C) for some constant C < 1, unless h = 0. Hence, we have x♯ = x, and the
sufficiency holds.

4

From Block p-RIP to Weighted Block p-NSP

In this part, we establish the relationship between the block p-RIP and weighted block p-NSP, which
tells us that block p-RIP can directly imply the weighted block p-NSP. As a consequence, we can obtain the
exact recovery for every block k-sparse signal via the weighted mixed ℓ2 /ℓp , 0 < p ≤ 1 norm minimization
problem (5) with ε = 0. The relationship is obtained as follows.
10

Theorem 3 Assume the block size equals d and let x ∈ RN be block k-sparse, supported on block index
set T0 . Let T̃ ⊂ {1, 2, · · · , n} be an arbitrary set and define ρ and α as before such that |T̃ | = ρk and
|T̃ ∩ T0 | = αρk. Let s = (1 + ρ − 2αρ)k, then we have T̃ = Γs (T0 ). Suppose that there exists an a ∈ Z,
with a ≥ (1 − α)ρ, a > 1, and the measurement matrix A satisfies
δak +

a1−p/2
a1−p/2
δ(a+1)k <
− 1,
γ
γ

(18)

where γ = ω + (1 − ω)(s/k)1−p/2 for some given 0 ≤ ω ≤ 1. Then A satisfies ω-d-p-NSP(k, s, C) for some
constant C < 1.
Consequently, according to Theorem 2, we have x is the unique solution of problem (5) with ε = 0.
Proof. To show for any vector h : Ah = 0, and for every block index set T ⊂ {1, · · · , n} with |T | ≤ k, and
S ⊂ {1, · · · , n} with |S| ≤ s, we have
ωkhT kp2,p + (1 − ω)khS kp2,p ≤ CkhT c kp2,p ,

(19)

for some constant C < 1, we only need to show (19) holds for T = G0 and S = H0 , where G0 is the block
index set over the k blocks with largest ℓ2 norm of h, H0 is the block index set over the s blocks with
largest ℓ2 norm of h.
Next, we decompose hGc0 into disjoint block index set Gj , each of Gj (j ≥ 1) consists of ak blocks. That
is, G1 indexes the ak blocks with largest ℓ2 norm of hGc0 . G2 indexes the second ak blocks with largest ℓ2
norm of h(G0 ∪G1 )c , and so on.
Since Ah = 0, then we have
kAhG0 ∪G1 kpp ≤ kAh(G0 ∪G1 )c kpp ≤

X

kAhGj kpp ≤ (1 + δak )

khGj kp2 .

j≥2

j≥2

Moreover, we have

X

X
X
khGj−1 kp2,p ≤ (ak)p/2−1 khGc0 kp2,p .
khGj kp2 ≤ (ak)p/2−1
j≥2

j≥2

Thus,
(1 − δ(a+1)k )khG0 ∪G1 kp2 ≤ kAhG0 ∪G1 kpp ≤ (1 + δak )(ak)p/2−1 khGc0 kp2,p .
It implies that
khG0 ∪G1 kp2 ≤

(ak)p/2−1 (1 + δak )
khGc0 kp2,p .
1 − δ(a+1)k

(20)

In addition, khG0 kp2,p ≤ k1−p/2 khG0 kp2 ≤ k1−p/2 khG0 ∪G1 kp2 . Hence,
khG0 kp2,p ≤ k1−p/2 khG0 ∪G1 kp2 ≤

ap/2−1 (1 + δak )
khGc0 kp2,p .
1 − δ(a+1)k

(21)

For the term khH0 kp2,p , we have khH0 kp2,p ≤ s1−p/2 khH0 kp2 . Moreover, if s ≤ k, we have H0 ⊂ G0
and khH0 kp2 ≤ khG0 kp2 ≤ khG0 ∪G1 kp2 . If s > k, then G0 ⊂ H0 . However, since |H0 \ G0 | = s − k =
11

(1 + ρ − 2αρ)k − k = (1 − 2α)ρk ≤ ak, then we also have khH0 kp2 ≤ khG0 ∪G1 kp2 as the block index set G1
contains the ak blocks with largest ℓ2 norm of hGc0 . As a consequence,
khH0 kp2,p ≤ s1−p/2 khH0 kp2 ≤ s1−p/2 khG0 ∪G1 kp2 ≤

(ak/s)p/2−1 (1 + δak )
khGc0 kp2,p .
1 − δ(a+1)k

(22)

Therefore, we obtain
ωkhG0 kp2,p + (1 − ω)khH0 kp2,p ≤ ω
=
Let C =

5

ap/2−1 γ(1+δak )
,
1−δ(a+1)k

ap/2−1 (1 + δak )
(ak/s)p/2−1 (1 + δak )
khGc0 kp2,p + (1 − ω)
khGc0 kp2,p
1 − δ(a+1)k
1 − δ(a+1)k

ap/2−1 γ(1 + δak )
khGc0 kp2,p .
1 − δ(a+1)k

we have C < 1 under the condition of block p-RIP. The proof is completed.

Simulation

In this section, we conduct several simulations to illustrate our presented theoretical results. We adopt
the iteratively reweighted least squares (IRLS) approach to solve the nonconvex optimization problem. We
begin with x(0) = arg min ky − Axk22 , and set γ0 = 1. Then, let x(t+1) be the solution of
min
x

1
1
ky − Axk22 + kW (t) xk22 ,
2λ
2

(23)
(t)

where λ > 0 is a regularization parameter, and the weight matrix W (t) is defined as Wi
4
p(p−2)

ωi

1/p
kωi x(t) [i]k22 )p/4−1/2 )

= diag((γt +

for the i-th block. Then, x(t+1) can be given explicitly as


−1
[A(W (t) )−1 ]T y.
x(t+1) = (W (t) )−1 [A(W (t) )−1 ]T [A(W (t) )−1 ] + λI

The value of γ is decreased according to the rule γt+1 = 0.1γt , and the iteration is continued until kx(t+1) −
x(t) k2 ≤ 10−5 or the iteration times is larger than 2500. In our experiments, the measurement matrix
A is generated as an m × N matrix with entries drawing from i.i.d standard normal distribution. For
a generated block sparse or nearly block sparse signal x, the measurements y = Ax + σz with z being
the standard Gaussian white noise. We consider several different parameter values to demonstrate the
theoretical results. In each experiment, we report the average results over 20 replications. For IRLS, we
set λ = 10−6 in the noise free case (σ = 0), and λ = 10−2 in the noisy case (σ = 0.01). The recovery
performance is assessed by the signal to noise ratio (SNR), which is given by


kxk2
SNR = 20 log 10
.
kx − x♯ k2

5.1

Exactly block sparse case

We first consider the case that x is exactly block k-sparse with k = 20. In this set of experiments,
the signal is of length N = 400, which is generated by choosing k blocks uniformly at random, and then
choosing the nonzero values from the standard normal distribution for these k blocks.
12

Figure 2 illustrates the recovery performance of the weighted ℓ2 /ℓp minimization problem with p = 0.5
and d = 2 in both with and without noise cases. It can be observed that when α = 0.7, the best recovery
is achieved for very small ω whereas a ω = 1 results in the lowest SNR. On the other hand, when α ≤ 0.5,
the performance of the recovery algorithms is better for large ω than that for small ω. The case ω = 0
results in the lowest SNR. And as is expected that in all settings, comparing to the noise free case, we have
a lower SNR in the noisy case.
Figure 3 shows the averaged SNR using weighted mixed ℓ2 /ℓp minimization for different values of the
ratio parameter ρ with fixed p = 0.5 and d = 2. It shows that when α = 0.7, using a larger support
estimate results in better reconstruction. However, in both the noise free and noisy measurements cases,
the recovery performance is more sensitive to the accuracy α of the block support estimate than the ratio
parameter ρ.
In addition, we illustrate the impacts of p and d in Figure 4 for both the noise free and noisy measurements cases. We fix k = 20, α = 0.7 and ω = 0.5. It is evident that as p decreases, the recovery
performance becomes better. And as d increases, more number of measurements are required to obtain
good reconstructions. These are largely consistent with the theoretical results in Section 2.
α =0.3,σ =0

α =0.5,σ =0

60

50

40

40

40

20

30

20
ω=0
ω=0.2
ω=0.5
ω=0.8
ω=1

10

0
60

SNR

50

30

80

100

120

140

160

0
60

80

number of measurements m

120

140

160

0
60

180

α =0.5,σ =0.01

55

45

45

45

40

40

40

35

35

35

30

30

30

20

SNR

50

25

25
20

15
10
5

80

100

120

140

160

5

number of measurements m

0
60

140

160

180

α =0.7,σ =0.01

25

15
ω=0
ω=0.2
ω=0.5
ω=0.8
ω=1

10

180

120

20

15
ω=0
ω=0.2
ω=0.5
ω=0.8
ω=1

100

55

50

0
60

80

number of measurements m

50

SNR

SNR

100

ω=0
ω=0.2
ω=0.5
ω=0.8
ω=1

10

number of measurements m

α =0.3,σ =0.01

55

30

20
ω=0
ω=0.2
ω=0.5
ω=0.8
ω=1

10

180

α =0.7,σ =0

60

50

SNR

SNR

60

80

100

120

140

number of measurements m

160

ω=0
ω=0.2
ω=0.5
ω=0.8
ω=1

10
5

180

0
60

80

100

120

140

160

180

number of measurements m

Figure 2: Performance of weighted mixed ℓ2 /ℓp recovery with p = 0.5 in terms of SNR for exactly block sparse signal
x depending on ω with k = 20, d = 2, while varying the number of measurements m.

5.2

Nearly block sparse case

Next, we generate x with the ℓ2 norm of its blocks decay like i−θ where i ∈ {1, · · · , n} and θ > 1. In
Figure 5, we illustrate the averaged SNR versus the size of the block support estimate ρ as a proportion
of k for θ = 1.5. To calculate α, we set k = 20, i.e., we are interested in the best 20-term block sparse

13

α =0.3,σ =0

45

α =0.5,σ =0

45

40

40

35

35

α =0.7,σ =0

160

140

ω=0
ω=0.2
ω=0.5
ω=0.8
ω=1

120
30

20

ω=0
ω=0.2
ω=0.5
ω=0.8
ω=1

25
20

15

15

10

10

5

5

0
0.4

0
0.4

100

SNR

ω=0
ω=0.2
ω=0.5
ω=0.8
ω=1

25

SNR

SNR

30

80

60

0.8

1

1.2

1.4

0.6

0.8

1

ρ

α =0.3,σ =0.01

40

35

35

30

30

20

10

10

5

5

1

1

1.2

1.4

1.2

1.4

α =0.7,σ =0.01

55

ω=0
ω=0.2
ω=0.5
ω=0.8
ω=1

20
15

0.8

0.8

ρ

50

25

15

0.6

0.6

ω=0
ω=0.2
ω=0.5
ω=0.8
ω=1

45

ω=0
ω=0.2
ω=0.5
ω=0.8
ω=1

25

0
0.4

20
0.4

1.4

α =0.5,σ =0.01

45

40

SNR

SNR

45

1.2

ρ

1.2

0
0.4

1.4

SNR

0.6

40

40

35

0.6

0.8

1

ρ

1.2

30
0.4

1.4

0.6

0.8

ρ

1

ρ

Figure 3: Performance of weighted mixed ℓ2 /ℓp recovery with p = 0.5 in terms of SNR for exactly block sparse signal
x depending on ω with k = 20, d = 2, while varying the size of the block support estimate ρ as a proportion of k.

d=2,σ =0

70

70

70

60

60

60

50

50

50

40

40

30

20

80

100

120

140

160

0
60

20

p=1
p=0.8
p=0.5
p=0.2
p=0.01

10

180

40

30

20

p=1
p=0.8
p=0.5
p=0.2
p=0.01

10

0
60

SNR

80

30

80

number of measurements m

100

120

140

160

0
60

180

50

40

40

40

20

SNR

50

SNR

50

30

30

20
p=1
p=0.8
p=0.5
p=0.2
p=0.01

10

120

140

number of measurements m

160

0
60

140

160

180

30

20
p=1
p=0.8
p=0.5
p=0.2
p=0.01

10

180

120

d=4,σ =0.01
60

100

100

d=2,σ =0.01
60

80

80

number of measurements m

60

0
60

p=1
p=0.8
p=0.5
p=0.2
p=0.01

10

number of measurements m

d=1,σ =0.01

SNR

d=4,σ =0

80

SNR

SNR

d=1,σ =0
80

80

100

120

140

number of measurements m

160

p=1
p=0.8
p=0.5
p=0.2
p=0.01

10

180

0
60

80

100

120

140

160

180

number of measurements m

Figure 4: Performance of weighted mixed ℓ2 /ℓp recovery in terms of SNR for exactly block sparse signal x depending
on p with k = 20, α = 0.7, ω = 0.5, while varying the number of measurements m.

14

approximation. It shows that mediate values of ω (e.g., ω = 0.2 or 0.5) results in the best recovery.
Generally, larger block support estimate favours better reconstruction result. Finally, we illustrate the
impacts of θ and d for different p in Figure 6. For θ = 1.5, we set k = 20, while for θ = 2, we consider
k = 10. It is evident that the recovery performance improves as θ increases, i.e., the block sparsity of
signal increases. Moreover, decreasing p and d improves the recovery performance when other parameters
are fixed.
α =0.3,σ =0

22

α =0.5,σ =0

23

21

22.5

20

α =0.7,σ =0

28

ω=0
ω=0.2
ω=0.5
ω=0.8
ω=1

27
26

ω=0
ω=0.2
ω=0.5
ω=0.8
ω=1

22
25
19

18

SNR

SNR

SNR

21.5

24
23

21
17

16

15

14
0.4

22

ω=0
ω=0.2
ω=0.5
ω=0.8
ω=1

0.6

20.5
21
20

0.8

1

1.2

19.5
0.4

1.4

20

0.6

0.8

ρ

1.2

19
0.4

1.4

0.6

0.8

ρ

α =0.3,σ =0.01

22

1

α =0.5,σ =0.01

23

21

22.5

20

1

1.2

1.4

1.2

1.4

ρ

α =0.7,σ =0.01

27

ω=0
ω=0.2
ω=0.5
ω=0.8
ω=1

26

25

ω=0
ω=0.2
ω=0.5
ω=0.8
ω=1

22
19

17

SNR

SNR

SNR

24
21.5

18

23

21
22

16
20.5
15
14
13
0.4

21

ω=0
ω=0.2
ω=0.5
ω=0.8
ω=1

0.6

20

0.8

1

1.2

1.4

19.5
0.4

20

0.6

0.8

ρ

1

ρ

1.2

1.4

19
0.4

0.6

0.8

1

ρ

Figure 5: Performance of weighted mixed ℓ2 /ℓp recovery in terms of SNR for nearly block sparse signal x with
p = 0.5, m = 80, θ = 1.5, k = 20, d = 2, while varying the size of the block support estimate ρ as a proportion of k.

6

Conclusion

In this paper, we presented the recovery analysis of weighted mixed ℓ2 /ℓp (0 < p ≤ 1) minimization
by using both block p-RIP and weighted block p-null space property. In addition, we established the relationship between these two conditions. A series of simulations were conducted to illustrate our theoretical
results. We largely generalized the existing results [19, 20, 33–35] to incorporating the prior known block
support information with a weight ω ∈ [0, 1]. And from the simulation results, it shows that mediate values
of the weight ω result in the best recovery in most of the cases.
There are some interesting issues left for future work. One is that it might be possible to generalize
ℓ2 -constrained minimization problem considered in this paper to the ℓq -constrained minimization problem
with 2 ≤ q ≤ ∞ (see [9, 32]) and with 0 ≤ q < 2 (see [36]). Another issue that is not addressed here is
to obtain the minimum required number of measurements for perfect recovery directly via weighted block
p-null space property. And the extension to the framework with completely arbitrary weights (see [28])
needs also to be considered.
15

d=1,θ=1.5 with k=20

d=2,θ=1.5 with k=20

d=4,θ=1.5 with k=20

28

30

28

28

26

26

26

24
24

SNR

SNR

22

SNR

24
22

22

20
20

20

18
p=1
p=0.8
p=0.5
p=0.2
p=0.01

18

16
60

80

100

120

140

160

p=1
p=0.8
p=0.5
p=0.2
p=0.01

18

16
60

180

80

number of measurements m

100

120

140

160

p=1
p=0.8
p=0.5
p=0.2
p=0.01

16

14
60

180

80

number of measurements m

d=1,θ=2 with k=10

d=2,θ=2 with k=10

34

34

32

32

30

30

28

28

100

120

140

160

180

number of measurements m

d=4,θ=2 with k=10
34

32

30

26

SNR

SNR

SNR

28

26

26
24

24

24
p=1
p=0.8
p=0.5
p=0.2
p=0.01

22

20
60

80

100

120

140

number of measurements m

160

22

180

20
60

22

p=1
p=0.8
p=0.5
p=0.2
p=0.01

80

100

120

140

number of measurements m

160

p=1
p=0.8
p=0.5
p=0.2
p=0.01

20

180

18
60

80

100

120

140

160

180

number of measurements m

Figure 6: Performance of weighted mixed ℓ2 /ℓp recovery in terms of SNR for nearly block sparse signal x for different
θ and d depending on p with fixed α = 0.7, ω = 0.5, σ = 0.01 for all the cases, while varying the number of
measurements m.

Acknowledgements
This work is supported by the Swedish Research Council grant (Reg.No. 340-2013-5342).

References
[1] Baraniuk, R.G., Cevher, V., Duarte, M.F. and Hegde, C. (2010). Model-based compressive sensing.
IEEE Transactions on Information Theory 56(4) 1982–2001.
[2] Blumensath, T. and Davies, M.E. (2009). Sampling theorems for signals from the union of finitedimensional linear subspaces. IEEE Transactions on Information Theory 55(4) 1872–1882.
[3] Candes, E.J., Romberg, J.K. and Tao, T. (2006). Stable signal recovery from incomplete and inaccurate
measurements. Communications on Pure and Applied Mathematics 59(8) 1207–1223.
[4] Candes, E.J. and Tao, T. (2005). Decoding by linear programming. IEEE Transactions on Information
Theory 51(12) 4203–4215.
[5] Candes, E.J. and Tao, T. (2006). Near-optimal signal recovery from random projections: Universal
encoding strategies?. IEEE Transactions on Information Theory 52(12) 5406–5425.
[6] Chartrand, R. (2007). Exact reconstruction of sparse signals via nonconvex minimization. IEEE Signal
Processing Letters 14(10) 707–710.

16

[7] Chartrand, R. and Staneva, V. (2008). Restricted isometry properties and nonconvex compressive
sensing. Inverse Problems 24 1–14.
[8] Chen, J. and Huo, X. (2006). Theoretical results on sparse representations of multiple-measurement
vectors. IEEE Transactions on Signal Processing 54(12) 4634–4643.
[9] Dirksen, S., Lecué, G. and Rauhut, H. (2016). On the gap between restricted isometry
properties and sparse recovery conditions. IEEE Transactions on Information Theory, (DOI:
10.1109/TIT.2016.2570244).
[10] Donoho, D.L. (2006). Compressed sensing. IEEE Transactions on Information Theory 52(4) 1289–
1306.
[11] Duarte, M.F. and Eldar, Y.C. (2011). Structured compressed sensing: From theory to applications.
IEEE Transactions on Signal Processing 59(9) 4053–4085.
[12] Eldar, Y.C., Kuppinger, P. and Bolcskei, H. (2010). Block-sparse signals: Uncertainty relations and
efficient recovery. IEEE Transactions on Signal Processing 58(6) 3042–3054.
[13] Eldar, Y.C. and Kutyniok, G. (2012). Compressed Sensing: Theory and Applications. Cambridge
University Press.
[14] Eldar, Y.C. and Mishali, M. (2009). Robust recovery of signals from a structured union of subspaces.
IEEE Transactions on Information Theory 55(11) 5302–5316.
[15] Eldar, Y.C. and Rauhut, H. (2010). Average case analysis of multichannel sparse recovery using convex
relaxation. IEEE Transactions on Information Theory 56(1) 505–519.
[16] Elhamifar, E. and Vidal, R. (2012). Block-sparse recovery via convex optimization. IEEE Transactions
on Signal Processing 60(8) 4094–4107.
[17] Foucart, S. and Lai, M.J. (2009). Sparsest solutions of underdetermined linear systems via ℓq minimization for 0 < q ≤ 1. Applied and Computational Harmonic Analysis 26(3) 395-407.
[18] Foucart, S. and Rauhut, H. (2013). A Mathematical Introduction to Compressive Sensing. New York:
Springer-Verlag.
[19] Friedlander, M.P., Mansour, H., Saab, R. and Yilmaz, O. (2012). Recovering compressively sampled
signals using partial support information. IEEE Transactions on Information Theory 58(2) 1122–1134.
[20] He, S., Wang, Y., Wang, J. and Xu, Z. (2016). Block-sparse compressed sensing with partially known
signal support via non-convex minimisation. IET Signal Processing 10(7) 717–723.
[21] Jacques, L. (2010). A short note on compressed sensing with partially known signal support. Signal
Processing 90(12) 3308–3312.
[22] Khajehnejad, M.A., Xu, W., Avestimehr, A.S. and Hassibi, B. (2009). Weighted ℓ1 minimization for
sparse recovery with prior information. In Information Theory, 2009. ISIT 2009. IEEE International
Symposium on (pp. 483-487).
[23] Lv, X., Bi, G. and Wan, C. (2011). The group lasso for stable recovery of block-sparse signal representations. IEEE Transactions on Signal Processing 59(4) 1371–1382.
[24] Majumdar, A. and Ward, R.K. (2010). Compressed sensing of color images. Signal Processing 90(12)
3122–3127.
17

[25] Mansour, H. and Saab, R. (2017). Recovery analysis for weighted ℓ1 -minimization using the null space
property. Applied and Computational Harmonic Analysis 43(1) 23–38.
[26] Mishali, M. and Eldar, Y.C. (2008). Reduce and boost: Recovering arbitrary sets of jointly sparse
vectors. IEEE Transactions on Signal Processing 56(10) 4692–4702.
[27] Mishali, M. and Eldar, Y.C. (2009). Blind multiband signal reconstruction: Compressed sensing for
analog signals. IEEE Transactions on Signal Processing 57(3) 993–1009.
[28] Needell, D., Saab, R. and Woolf, T. (2017). Weighted ℓ1 -minimization for sparse recovery under
arbitrary prior information. Information and Inference, iaw023.
[29] Ince, T., Nacaroglu, A. and Watsuji, N. (2013). Nonconvex compressed sensing with partially known
signal support. Signal Processing 93(1) 338–344.
[30] Parvaresh, F., Vikalo, H., Misra, S. and Hassibi, B. (2008). Recovering sparse signals using sparse
measurement matrices in compressed DNA microarrays. IEEE Journal of Selected Topics in Signal
Processing 2(3) 275–285.
[31] Rauhut, H. and Ward, R. (2016). Interpolation via weighted ℓ1 minimization. Applied and Computational Harmonic Analysis 40(2) 321–351.
[32] Saleh, A.A., Alajaji, F. and Chan, W.Y. (2015). Compressed sensing with non-Gaussian noise and
partial support information. IEEE Signal Processing Letters 22(10) 1703–1707.
[33] Vaswani, N. and Lu, W. (2010). Modified-CS: Modifying compressive sensing for problems with partially known support. IEEE Transactions on Signal Processing 58(9) 4595-4607.
[34] Wang, Y., Wang, J. and Xu, Z. (2013). On recovery of block-sparse signals via mixed ℓ2 /ℓq (0 < q ≤ 1)
norm minimization. EURASIP Journal on Advances in Signal Processing 2013(1):76.
[35] Wang, Y., Wang, J. and Xu, Z. (2014). Restricted p-isometry properties of nonconvex block-sparse
compressed sensing. Signal Processing 104 188–196.
[36] Wen, F., Liu, P., Liu, Y., Qiu, R.C. and Yu, W. (2017). Robust Sparse Recovery in Impulsive Noise
via ℓp -ℓ1 Optimization. IEEE Transactions on Signal Processing 65(1) 105–118.
[37] Xu, Z., Chang, X., Xu, F. and Zhang, H. (2012). ℓ1/2 regularization: A thresholding representation
theory and a fast solver. IEEE Transactions on Neural Networks and Learning Systems 23(7) 1013–1027.
[38] Yu, X. and Baek, S.J. (2013). Sufficient conditions on stable recovery of sparse signals with partial
support information. IEEE Signal Processing Letters 20(5) 539–542.
[39] Yuan, M. and Lin, Y. (2006). Model selection and estimation in regression with grouped variables.
Journal of the Royal Statistical Society: Series B (Statistical Methodology) 68(1) 49–67.
[40] Zeinalkhani, Z. and Banihashemi, A.H. (2015). Iterative reweighted ℓ2 /ℓ1 recovery algorithms for
compressed sensing of block sparse signals. IEEE Transactions on Signal Processing 63(17) 4516–4531.

18

