Stable and robust ℓp-constrained compressive sensing

arXiv:1705.03810v2 [cs.IT] 25 Aug 2017

recovery via robust width property
Zhiyong Zhou∗, Jun Yu
Department of Mathematics and Mathematical Statistics, Umeå University,
Umeå, 901 87, Sweden
August 28, 2017

Abstract: We study the recovery results of ℓp -constrained compressive sensing (CS) with p ≥ 1 via robust
width property and determine conditions on the number of measurements for standard Gaussian matrices
under which the property holds with high probability. Our paper extends the existing results in Cahill
and Mixon (2014) from ℓ2 -constrained CS to ℓp -constrained case with p ≥ 1 and complements the recovery
analysis for robust CS with ℓp loss function.
Keywords: Compressive sensing; Robust width property; Robust null space property; Restricted isometry
property.

1

Introduction

There has been enormous research interest in the field of compressive sensing (CS) since its advent
in [3, 5]. CS aims to recover an unknown signal with underdetermined linear measurements (see [8, 9]
for a comprehensive view). Specifically, let x♮ be some unknown signal, which lies in a finite-dimensional
Hilbert space H, and let Φ : H → Fm be the underdetermined measurement linear operator, where F
P
p 1/p for 1 ≤ p < ∞ and
is either R or C. We denote the usual ℓp norm in Fm as kukℓp = ( m
i=1 |ui | )
kuk∞ = max1≤i≤m |ui |. Then, given the measurements y = Φx♮ + e for some unknown error e ∈ Fm
with kekℓ2 ≤ ε and x♮ is close to a particular subset A ⊆ H that consists of members with some specific
structure, there is a norm k·k♯ corresponding to A such that
△♯,2 (y) := arg min kxk♯ subject to kΦx − ykℓ2 ≤ ε
x

(1)

is a good estimate of the original signal x♮ , provided that the measurement matrix Φ satisfies certain
properties (e.g., robust null space property, restricted isometry property). However, these conditions are
not known to be necessary. Recently, for a broad class of triples (H, A, k·k♯ ), [2] completely characterized
Φ for which
k△♯,2 (y) − x♮ k2 ≤ C0 kx♮ − ak♯ + C1 ε ∀ x♮ ∈ H, e ∈ Fm , kekℓ2 ≤ ε, a ∈ A
∗

(2)

Corresponding author, zhiyong.zhou@umu.se. This work is supported by the Swedish Research Council grant (Reg.No.
340-2013-5342). Mathematics Subject Classification (2010): 94A12, 94A20.

1

holds for any given constants C0 and C1 via robust width property (RWP). Here the k·k2 on the left hand
side above denotes the norm induced by the inner product over H.
But in some certain cases, it is of special interest to use the ℓp -norms with 1 ≤ p ≤ ∞ which is different
from 2, as the loss function for measuring the noise level (see [1, 4, 11, 17, 18]). Hereafter, we will focus on
the solutions of the corresponding ℓp -constrained CS problem:
△♯,p (y) := arg min kxk♯ subject to kΦx − ykℓp ≤ ε.
x

(3)

The cases that taking H to be either RN or CN and k·k♯ = k·kℓ1 , and that taking H to be the Hilbert
space of real (or complex) matrices with inner product hX, Y i = T r(XY ∗ ) and considering the nuclear
norm k·k♯ = k·k∗ have been studied via the corresponding robust null space properties in [4] and [12],
respectively. In this paper, we complement these recovery analysis results via RWP, a kind of weaker
property compared to the robust null space property (NSP) and restricted isometry property (RIP). And
from the other point of view, we simultaneously extend the existing results of RWP for ℓ2 -constrained CS
in [2] to a much more general ℓp -constrained case with p ≥ 1.
The remainder of the paper is organized as follows. In Section 2, we introduce the RWP and give the
equivalent condition for stable and robust recovery results. We discuss the relationship between RWP and
robust NSP in Section 3, and the relationship between RWP and RIP in Section 4. In Section 5, we obtain
the optimal minimum required number of measurements for standard Gaussian matrices via RWP. We
finish in Section 6 with a conclusion.

2

Robust width property

Firstly, we present the definition of RWP which acts as our basic recovery analysis tool. As will be
given below, our newly defined RWP involves a new parameter p and it is obvious that the original RWP
in [2] is a special case of ours with p = 2.
Definition 1 For any p ≥ 1, we say a linear operator Φ : H → Fm satisfies the (p, ρ, α)-RWP over the
unit ♯-ball B♯ if
kxk2 ≤ ρkxk♯
for every x ∈ H such that kΦxkℓp < αkxk2 .
In order to apply the results to various instances of CS, we adopt the definition of CS spaces from [2]
here.
Definition 2 (Definition 1 in [2]) A CS space (H, A, k·k♯ ) with bound L consists of a finite-dimensional
Hilbert space H, a subset A ⊆ H, and a norm k·k♯ with the following properties:
(i) 0 ∈ A.
(ii) For every a ∈ A and v ∈ H, there exists a decomposition v = v1 + v2 such that
ka + v1 k♯ = kak♯ + kv1 k♯ , kv2 k♯ ≤ Lkvk2 .

2

Remark 1 As presented in Section 4 of [2], a variety of examples of CS framework satisfy this framework,
including weighted sparsity [10, 13, 16], block sparsity [6, 7], gradient sparsity [14, 15] and low-rank matrices [12].
Next, we give the main result that completely characterizes the measurement operators Φ for which
the stable and robust recovery results for ℓp -constrained CS are achieved.
Theorem 1 For any p ≥ 1, any CS space (H, A, k·k♯ ) with bound L and any linear operator Φ : H → Fm ,
the following statements are equivalent up to constants:
(a) Φ satisfies the (p, ρ, α)-RWP over B♯ .
(b) For every x♮ ∈ H, y = Φx♮ + e with e ∈ Fm and kekℓp ≤ ε, any solution x⋆ to
min kxk♯ subject to kΦx − ykℓp ≤ ε
x

(4)

satisfies kx⋆ − x♮ k2 ≤ C0 kx♮ − ak♯ + C1 ε for every a ∈ A.
In particular, (a) implies (b) with C0 = 4ρ and C1 = α2 provided ρ ≤ 1/(4L). Also, (b) implies (a) with
ρ = 2C0 and α = 2C1 1 .
When taking p = 2, this theorem goes to Theorem 3 in [2]. Its proof follows from Theorem 3 in [2]
with minor modification. For the sake of completeness, we present the proof here.
Proof. (a) ⇒ (b): Pick a ∈ A and decompose v = x⋆ − x♮ = v1 + v2 according to (ii) in Definition 2 such
that ka + v1 k♯ = kak♯ + kv1 k♯ and kv2 k♯ ≤ Lkvk2 . Then
kak♯ + kx♮ − ak♯ ≥ kx♮ k♯

≥ kx⋆ k♯

= kx♮ + (x⋆ − x♮ )k♯

= ka + (x♮ − a) + v1 + v2 k♯

≥ ka + v1 k♯ − k(x♮ − a) + v2 k♯

≥ ka + v1 k♯ − kx♮ − ak♯ − kv2 k♯

= kak♯ + kv1 k♯ − kx♮ − ak♯ − kv2 k♯ .
Thus kv1 k♯ ≤ 2kx♮ − ak♯ + kv2 k♯ , which implies that
kx⋆ − x♮ k♯ ≤ kv1 k♯ + kv2 k♯ ≤ 2kx♮ − ak♯ + 2kv2 k♯ ≤ 2kx♮ − ak♯ + 2Lkx⋆ − x♮ k2 .

(5)

Assume that kx⋆ − x♮ k2 > C1 ε, since otherwise the desired result holds. Then, we have
kΦx⋆ − Φx♮ kℓp ≤ kΦx⋆ − (Φx♮ + e)kℓp + kekℓp ≤ 2ε <

2
kx⋆ − x♮ k2 = αkx⋆ − x♮ k2
C1

by taking C1 = α2 . Therefore, by (a), it holds that
kx⋆ − x♮ k2 ≤ ρkx⋆ − x♮ k♯ .
3

(6)

Therefore, by substituting (6) into (5), we have
kx⋆ − x♮ k♯ ≤
provided that ρ ≤

1
4L .

2
kx♮ − ak♯ ≤ 4kx♮ − ak♯
1 − 2ρL

Finally, applying (6) again implies that

kx⋆ − x♮ k2 ≤ ρkx⋆ − x♮ k♯ ≤ 4ρkx♮ − ak♯ = C0 kx♮ − ak♯ ≤ C0 kx♮ − ak♯ + C1 ε
with C0 = 4ρ.
(b) ⇒ (a): Pick x♮ such that kΦx♮ kℓp < αkx♮ k2 . Then by setting ε = αkx♮ k2 and e = 0, we observe
that x⋆ = 0 is a feasible solution of (4), and so with a = 0 we obtain
kx♮ k2 = kx⋆ − x♮ k2 ≤ C0 kx♮ k♯ + C1 ε = C0 kx♮ k♯ + αC1 kx♮ k2 .
Thus, we have
kx♮ k2 ≤
by taking α =

3

1
2C1

and ρ = 2C0 .

C0
kx♮ k♯ = ρkx♮ k♯
1 − αC1

Robust NSP implies RWP

In this section, we propose a general version of robust NSP for CS spaces (H, A, k·k♯ ) and establish its
relationship with RWP.
Definition 3 For CS space (H, A, k·k♯ ) with bounds L and p ≥ 1, we say a linear operator Φ : H → Fm
satisfies the robust NSP with respect to ℓp with constants φ > 0 and τ > 0 if for all v ∈ H and a ∈ A
kvk2 ≤ φkv − ak♯ + τ kΦvkℓp

(7)

In fact, this kind of definition of robust NSP is a weaker version compared to the traditional ones we
used before. Several examples are list here.
Example 1 Take H to be CN , A = Σs := {x : kxkℓ0 := card({j ∈ [N ] : xj 6= 0}) ≤ s} and k·k♯ = k·kℓ1 .
Then the traditional robust NSP with respect to ℓp norm of order s with constants 0 < ψ < 1 and
τ > 0 [4, 9] is defined as for any set S ⊂ [N ] with |S| ≤ s and any v ∈ CN ,
ψ
kvS kℓ2 ≤ √ kvS c kℓ1 + τ kΦvkℓp .
s
If we take S to be the index set of s largest (in modulus) entries of v, then for any v ∈ CN we have
kvkℓ2 ≤ kvS kℓ2 + kvS c kℓ2
≤ kvS kℓ2 + kvS c kℓ1

ψ
≤ √ kvS c kℓ1 + τ kΦvkℓp + kvS c kℓ1
s
4

ψ
= ( √ + 1)kvS c kℓ1 + τ kΦvkℓp
s
ψ
≤ ( √ + 1)kv − akℓ1 + τ kΦvkℓp .
s
Therefore, the robust NSP given in Definition 3 holds with φ = ( √ψs + 1). Similar conclusion holds
in the weighted sparsity case. Specifically, for every v ∈ CN and 0 < q ≤ 2, we define kvkw,q =
!1/q
N
P
wj2−q |vj |q
with w = (wj )j∈[N ] being a vector of weights wj ≥ 1. Set kvk♯ = kvkw,1 and
j=1
(
)
P
2
A = Σw,s := x :
wj ≤ s . Then the weighted robust NSP with respective to ℓp norm of or{j:xj 6=0}

der s with constants ψ ∈ (0, 1) and τ > 0 (the case p = 2 see the Definition 4.1 in [16]):

X
ψ
kvS kℓ2 ≤ √ kvS c kw,1 + τ kΦvkℓp , for all v ∈ CN and any set S ⊂ [N ] with w(S) :=
wj2 ≤ s
s
j∈S

will also imply the robust NSP given in Definition 3.
Example 2 Take H to be the Hilbert space of C n1 ×n2 with inner product hX, Y i = T r(XY ∗ ), and consider
the nuclear norm kXk♯ = kXk∗ . Let A denote the sets of matrices with rank at most r. With the Schatten
!1/q
n
P
n
×n
q
1
2
q-norm of X ∈ C
given by kXkp =
σj (X)
(q ≥ 1) where σj (X), j = 1, · · · , n denote the
j=1

singular values of X, then the nuclear norm k·k∗ and the Frobenius norm k·kF correspond to the cases
that q = 1 and q = 2, respectively. We write X = Xr + Xc , where Xr is the best rank r approximation of
X with respect to any Schatten q-norm of X. Then, for p ≥ 1, we say that Φ : Cn1 ×n2 → Cm satisfies the
Frobenius-robust rank NSP with respect to ℓp of order r with constants 0 < ψ < 1 and τ > 0 [12] if for all
M ∈ Cn1 ×n2 , the singular values of M satisfy
ψ
kMr k2 ≤ √ kMc k1 + τ kΦM kℓp .
r
Then, for all M , it is obvious that
kMr k2 ≤ kMr k2 + kMc k2
≤ kMr k2 + kMc k1

ψ
≤ √ kMc k1 + τ kΦM kℓp + kMc k1
r
ψ
≤ ( √ + 1)kMc k1 + τ kΦM kℓp
r
ψ
≤ ( √ + 1)kM − ak1 + τ kΦM kℓp .
r
holds for all a ∈ A. Therefore, the robust NSP given in Definition 3 holds in this specific CS space.
Next, we show that compared to the robust NSP given above, RWP is actually a weaker property.

5

Theorem 2 For any CS space (H, A, k·k♯ ) with bound L, if a linear operator Φ : H → Fm satisfies the
robust NSP with respect to ℓp with constants φ > 0 and τ > 0, then this linear operator Φ satisfies the
1
(p, ρ, α)-RWP over B♯ with ρ = 2φ and α = 2τ
.
Proof. If for any x ∈ H such that kΦxkℓp < αkxk2 , then by applying the robust NSP with respect to ℓp
of Φ, we have
kxk2 ≤ φkx − ak♯ + τ kΦxkℓp ≤ φkx − ak♯ + ατ kxk2
holds for all a ∈ A. Let a = 0 and rearrange the inequality, we obtain that
kxk2 ≤

φ
kxk♯ .
1 − ατ

Thus, kxk2 ≤ ρkxk♯ holds by assuming that ρ = 2φ and α =

4

1
2τ .

A direct proof of RIPp,2 implies RWP

Basically, it’s often inconvenient to show the robust NSP directly for a given matrix. Thus, one usually
works instead with a bit stronger properties, i.e., various versions of RIP. And it’s well known that RIP
implies part (b) in Theorem 1. Then, one could come into conclusion that RIP implies the RWP based on
the equivalence of RWP to the stable and robust recovery result. For the sake of completeness, we will give
a direct proof of RIP implies RWP in this section. In addition, we merely focus on the traditional sparsity
case for CS space here instead of different versions of RIP for different CS spaces. The similar proofs hold
for other cases. To handle the ℓp -constrained CS, the following RIPp,2 [11] is used.
Definition 4 We say Φ satisfies the (µp,2 , s, δ)-RIPp,2 if
µp,2 (1 − δ)kxkℓ2 ≤ kΦxkℓp ≤ µp,2 (1 + δ)kxkℓ2

(8)

for every s-sparse vector x.
It is known that the stable and robust recovery result is guaranteed if Φ satisfies the (µp,2 , s, δ)-RIPp,2
with some small δ. But this RIP condition is strictly stronger than the RWP condition. Next, we are
going to present the fact and proof of that the RIP with a small constant δ does imply the RWP. Before
that, the following lemma which will be used in this proof is provided. It is a direct extension of Lemma
12 in [2] from p = 2 to p ≥ 1.
Lemma 1 Suppose that Φ satisfies the right-hand inequality of (µp,2 , s, δ)-RIPp,2 . Then for every x such
that kxkℓ2 > ρkxkℓ1 , we have
1
(1 + δ)µp,2
√
kx − xS kℓ2 < √ kxkℓ2 , kΦ(x − xS )kℓp <
kxkℓ2 ,
ρ s
ρ s
where S denotes the indices of the s largest (in modulus) entries of x.

6

Proof. Let S0 = S, and for j ≥ 1, Sj denote the indices of the s largest (in modulus) entries of x not
covered by Si for i < j. Then, for all j ≥ 0, it holds that
kxSj+1 kℓ2 ≤

√

s max |xi | ≤
i∈Sj+1

√

1
s min |xi | ≤ √ kxSj kℓ1 .
i∈Sj
s

Therefore, for every x such that kxkℓ2 > ρkxkℓ1 ,
kx − xS kℓ2 ≤

X
1
1
1 X
kxSj kℓ1 = √ kxkℓ1 < √ kxkℓ2 .
kxSj kℓ2 ≤ √
s
s
ρ s
j≥0

j≥1

Similarly, it holds that
kΦ(x − xS )kℓp ≤

X
X
(1 + δ)µp,2
√
kxSj kℓ2 <
kxkℓ2 .
kΦxSj kℓp ≤ (1 + δ)µp,2
ρ s
j≥1

j≥1

Theorem 3 Suppose Φ satisfies (µp,2 , s, δ)-RIPp,2 with δ < 31 . Then Φ satisfies the (p, ρ, α)-RWP over
Bℓ1 with
3
1
ρ = √ , α = ( − δ)µp,2 .
3
s
Proof. The proof procedure follows from the proof of theorem 11 in [2] with minor modification. It will be
proved by contradiction. We assume Φ satisfies the right-hand inequality of (µp,2 , s, δ)-RIPp,2 , but violates
the (p, ρ, α)-RWP, then the proof of the theorem is completed if we can show that Φ necessarily violates
the left-hand inequality of (µp,2 , s, δ)-RIPp,2 .
In fact, if we pick x such that kΦxkℓp < αkxkℓ2 but kxkℓ2 > ρkxkℓ1 , then we have
kΦxS kℓp ≤ kΦxkℓp + kΦ(x − xS )kℓp < αkxkℓ2 +

(1 + δ)µp,2
2
√
kxkℓ2 = (1 − δ)µp,2 kxkℓ2
ρ s
3

(9)

by using Lemma 1 and our specific choices of ρ and α. By adopting Lemma 1 again, it holds that
1
kxkℓ2 ≤ kxS kℓ2 + kx − xS kℓ2 < kxS kℓ2 + kxkℓ2 ,
3
which implies kxkℓ2 < 32 kxS kℓ2 . Therefore, we have kΦxS kℓp < 32 (1 − δ)µp,2 kxkℓ2 = (1 − δ)µp,2 kxS kℓ2 . This
is the desired result and completes the proof.

5

Recovery results via RWP

In this section, we will provide the recovery results for ℓp -constrained CS directly via RWP and find the
required minimum number of measurements for standard Gaussian matrices. We take H = RN and F = R
at the remainder of this section. To obtain the main result, it will be much more convenient to adopt the
contrapositive statement of (p, ρ, α)-RWP: for any p ≥ 1, a linear operator Φ : RN → Rm satisfies the
(p, ρ, α)-RWP over Bℓ1 if and only if kΦxkℓp ≥ αkxkℓ2 for every x ∈ RN such that kxkℓ2 > ρkxkℓ1 . Then,
by scaling, (p, ρ, α)-RWP is further equivalent to having kΦxkℓp ≥ α for every x ∈ RN such that kxkℓ2 = 1
and kxkℓ1 < ρ−1 . Taking T = ρ−1 Bℓ1 ∩ SN −1 where SN −1 denotes the unit sphere in RN , we have the
following lemma:
7

Lemma 2 A linear operator Φ : RN → Rm satisfies (p, ρ, α)-RWP over Bℓ1 if and only if kΦxkℓp ≥ α for
every x ∈ T .
Let X1 , · · · , Xm be i.i.d. copies of a random vector X in RN . Then we have the following key lemma
concerning a lower bound for empirical processes:
Lemma 3 (Lemma III.1. in [4]) Fix 1 ≤ p < ∞, let F be a class of function from RN into R. Consider
m
1 P
QF (u) = inf P (|f (X)| ≥ u) and Rm (F) = E sup | m
εi f (Xi )|, where {εi }i≥1 is a Rademacher sequence.
f ∈F

f ∈F

i=1

2

Let u > 0 and t > 0, then, with probability at least 1 − 2e−2t ,



m
t
4
1 X
p
p
|f (Xi )| ≥ u QF (2u) − Rm (F) − √
inf
f ∈F m
u
m
i=1

With the above two lemmas being applied, the main recovery result for standard Gaussian matrices is
provided as follows:
Theorem 4 Take ρ > 0 and Let Φ be an m × N standard Gaussian matrix. Define the Gaussian width of
T as w(T ) = E supx∈T hg, xi, where g has i.i.d. N (0, 1) entries. For any p ≥ 1, set α = c1 m1/p and if
m ≥ c0 w(T )2 ,
then Φ satisfies the (p, ρ, α)-RWP over Bℓ1 with probability exceeding 1 − 2e−c2 m .
Proof. According to Lemma 2, it suffices to show that


P inf kΦxkℓp ≥ α ≥ 1 − 2e−c2 m .
x∈T

We write
inf kΦxkℓp = inf

x∈T

x∈T

m
X
i=1

|hXi , xi|p

!1/p

,

where Xi denotes the i-th row of Φ.
Firstly, we suppose 1 ≤ p < ∞, then applying Lemma 3 with F = {h·, xi : x ∈ T }, we obtain that
inf kΦxkℓp = inf

x∈T

x∈T

m
X
i=1

p

|hXi , xi|

!1/p

≥m

1/p



4
t
u QF (2u) − Rm (F) − √
u
m

1/p

.

(10)

2

holds with probability at least 1 − 2e−2t . Next, we estimate the small ball probability QF (2u) and the
expected Rademacher supremum Rm (F) respectively. Since for any x ∈ SN −1 , kxkℓ2 = 1, therefore
P (|hXi , xi| ≥ u) = P (|G| ≥ u),
where G is a standard Gaussian real-valued random variable. Hence, it holds that
QF (2u) ≥ P (|G| ≥ 2u).
8

(11)

In addition, let V =

√1
m

m
P

εi Xi , then V is a standard Gaussian vector. Then we have

i=1

1
1
Rm (F) = √ E suphV, xi = √ w(T ).
m x∈T
m

Now pick u⋆ small enough such that the right side of (11) is bigger than 12 and t =

2
c1 p
4
−
(
2 21 − u⋆ √
)
, then with probability exceeding 1 − 2e−c2 m it holds that
u⋆
c0


4 1
t
1
√ w(T ) − √
−
2 u⋆ m
m
r 1/p

1
4
c2
≥ m1/p u⋆
− √ −
2 u⋆ c0
2

inf kΦxkℓp ≥ m1/p u⋆

x∈T

p c2 m
2

with c2 =

1/p

=: c1 m1/p = α.

Finally, when p = ∞, since kΦxkℓlog m ≤ ekΦxkℓ∞ , hence
P ( inf kΦxkℓ∞ ≥ c1 ) ≥ P ( inf kΦxkℓlog m ≥ c1 e).
x∈T

x∈T

Thus, the result follows from the already proved case that p = log m and the proof is completed.
To further compute the lower bound of the required number of measurements m, we need the following
upper bound for the Gaussian width of set T :
Lemma 4 (Lemma 16 in [2]) There exists an absolute constant c such that
p
√
w( sBℓ1 ∩ SN −1 ) ≤ c s log(eN/s)

(12)

for every positive integer s.

Then, the order of the minimum required number of measurements m for standard Gaussian matrices
to guarantee the stable and robust recovery result with high probability is established here. A similar
result is obtained in Theorem III.3 of [4] via robust NSP. Since it’s shown in Section 3 that RWP is weaker
than robust NSP, thus we can weaken the condition of the required minimum m up to constants although
it seems that the obtained orders are the same and optimal via both methods.
Corollary 1 Let Φ be an m × N standard Gaussian matrix. Fix 1 ≤ p ≤ ∞ and 0 < η < 1. There exists
some constants {C, D, C ′ , D ′ } such that if
m ≥ Cs log(eN/s) + D log(2η −1 ),
then with probability exceeding 1 − η, for every x♮ ∈ RN , y = Φx♮ + e with e ∈ Rm and kekℓp ≤ ε, any
solution x⋆ to
min kxkℓ1 subject to kΦx − ykℓp ≤ ε
x

satisfies kx⋆ − x♮ kℓ2 ≤

C′
√
σ (x♮ )1
s s

+

D′
ε,
m1/p

where σs (x♮ )1 =
9

inf kx♮ − zkℓ1 .

kzkℓ0 ≤s

(13)

Proof. Take the CS space (H, A, k·k♯ ) with bound L to be the traditional sparse space with H = RN ,
′
1
with 0 < C ′ ≤ 1 and
A = Σs and k·k♯ = k·kℓ1 . Then as given in [2], we have L = √1s . Set ρ = 4C√s ≤ 4√
s
α = D2′ m1/p , then the desired result follows from Theorem 1 if the (p, ρ, α)-RWP over Bℓ1 of Φ is verified.
In fact, by adopting Theorem 4 and Lemma 4, this holds when m ≥ Cs log(eN/s) + D log(2η −1 ) with C
and D being appropriately chosen.

6

Conclusion

In this paper, we studied the equivalent RWP condition to guarantee the stable and robust recovery
result for ℓp -constrained CS procedure. We proposed a general version of robust NSP and verified that both
robust NSP and RIP imply RWP. Finally, the specific recovery condition for standard Gaussian matrices
was established via RWP and the optimal order of the minimum required number of measurements was
obtained. The present paper extends the CS recovery analysis results via RWP in [2] from ℓ2 -constrained
to ℓp -constrained case with p ≥ 1, and also largely complements the existing theoretical results for robust
CS with ℓp loss function, see [1, 4, 11, 12, 17, 18], and among others.

References
[1] Allen-Zhu, Z., Gelashvili, R., and Razenshteyn, I. (2016). Restricted isometry property for general
p-norms. IEEE Transactions on Information Theory 62(10) 5839–5854.
[2] Cahill, J., and Mixon, D.G. (2014). Robust width: A characterization of uniformly stable and robust
compressed sensing. arXiv preprint arXiv:1408.4409.
[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] 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).
[5] Donoho, D.L. (2006). Compressed sensing. IEEE Transactions on Information Theory 52(4) 1289–1306.
[6] Duarte, M.F., and Eldar, Y.C. (2011). Structured compressed sensing: From theory to applications.
IEEE Transactions on Signal Processing 59(9) 4053–4085.
[7] 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.
[8] Eldar, Y.C., and Kutyniok, G. (2012). Compressed Sensing: Theory and Applications. Cambridge
University Press.
[9] Foucart, S., and Rauhut, H. (2013). A Mathematical Introduction to Compressive Sensing. New York:
Springer-Verlag.
[10] 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.

10

[11] Jacques, L., Hammond, D.K., and Fadili, J.M. (2011). Dequantizing compressed sensing: When oversampling and non-gaussian constraints combine. IEEE Transactions on Information Theory 57(1) 559–
571.
[12] Kabanava, M., Kueng, R., Rauhut, H., and Terstiege, U. (2016). Stable low-rank matrix recovery via
null space properties. Information and Inference 5(4) 405–441.
[13] 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.
[14] Needell, D., and Ward, R. (2013). Near-optimal compressed sensing guarantees for total variation
minimization. IEEE Transactions on Image Processing 22(10) 3941–3949.
[15] Needell, D., and Ward, R. (2013). Stable image reconstruction using total variation minimization.
SIAM Journal on Imaging Sciences 6(2) 1035–1058.
[16] Rauhut, H., and Ward, R. (2016). Interpolation via weighted ℓ1 minimization. Applied and Computational Harmonic Analysis 40(2) 321–351.
[17] 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.
[18] 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.

11

