1

Uniform Recovery Bounds for Structured Random
Matrices in Corrupted Compressed Sensing

arXiv:1706.09087v3 [] 7 Feb 2018

Peng Zhang, Lu Gan, Cong Ling and Sumei Sun

Abstract—We study the problem of recovering an s-sparse
signal x⋆ ∈ Cn from corrupted measurements y = Ax⋆ +z⋆ +w,
where z⋆ ∈ Cm is a k-sparse corruption vector whose nonzero
entries may be arbitrarily large and w ∈ Cm is a dense noise
with bounded energy. The aim is to exactly and stably recover
the sparse signal with tractable optimization programs. In this
paper, we prove the uniform recovery guarantee of this problem
for two classes of structured sensing matrices. The first class
can be expressed as the product of a unit-norm tight frame
(UTF), a random diagonal matrix and a bounded columnwise orthonormal matrix (e.g., partial random
√ circulant matrix).
When the UTF is bounded (i.e. µ(U) ∼ 1/ m), we prove that
with high probability, one can recover an s-sparse signal exactly
and stably by l1 minimization programs even if the measurements
are corrupted by a sparse vector, provided m = O(s log2 s log 2 n)
and the sparsity level k of the corruption is a constant fraction
of the total number of measurements. The second class considers
randomly sub-sampled orthonormal matrix (e.g., random Fourier
matrix). We prove the uniform recovery guarantee provided that
the corruption is sparse on certain sparsifying domain. Numerous
simulation results are also presented to verify and complement
the theoretical results.
Index Terms—Compressed sensing, corruption, dense noise,
unit-norm tight frames.

I. I NTRODUCTION
The theory of compressed sensing has been widely studied and applied in various promising applications over the
recent years [1]–[5]. It provides an efficient way to recover a
sparse signal from a relatively small number of measurements.
Specifically, an s-sparse signal x⋆ is measured through
y = Ax⋆ + w,

(1)

where A ∈ Cm×n is referred to as the sensing matrix,
y ∈ Cm is the measurement vector and w ∈ Cm represents
the noise vector with the noise level kwk2 ≤ ε. It has been
shown that if A satisfies the restricted isometry property (RIP)
and ε is small, the recovered signal x̂ obtained by l1 norm
minimization is close to the true x⋆ , i.e. kx̂ − x⋆ k ≤ Cε with
C being a small numerical constant. Many types of sensing
matrices have been proven to satisfy the RIP condition. For
P. Zhang was with the Department of Electrical and Electronic Engineering, Imperial College London, London, SW7 2AZ, UK (e-mail:
p.zhang12@imperial.ac.uk). He is now with the Institute for Infocomm
Research, A∗ STAR, Singapore, 138632, Singapore (e-mail: zhangp@i2r.astar.edu.sg).
C. Ling is with the Department of Electrical and Electronic Engineering,
Imperial College London, London, SW7 2AZ, UK (e-mail: cling@ieee.org) .
L. Gan is with the College of Engineering, Design and Physical Science,
Brunel University, London, UB8 3PH, UK (e-mail: lu.gan@brunel.ac.uk).
S. Sun is with the Institute for Infocomm Research, A∗ STAR, Singapore,
138632, Singapore (e-mail: sunsm@i2r.a-star.edu.sg).

example, random Gaussian/Bernoulli matrices satisfy the RIP
with high probability if m ≥ O(s log(n/s)) [1], [3], whereas
structured sensing matrices consisting of either randomly
subsampled orthonormal matrix [6] or modulated unit-norm
tight frames [7] have the RIP with high probability when m
is about O(s log4 n)1 .
This standard compressed sensing problem has been generalized to cope with the recovery of sparse signals when some
unknown entries of the measurement vector y are severely
corrupted. Mathematically, we have
y = Ax⋆ + z⋆ + w,
⋆

(2)

m

where z ∈ C is an unknown sparse vector. To reconstruct
x⋆ from the measurement vector y, the following penalized
l1 norm minimization has been proposed:
min kxk1 + λkzk1
x,z

s.t.

ky − (Ax + z)k2 ≤ ε. (3)

In [10], it was shown that random Gaussian matrices can
provide uniform recovery guarantees to this problem (3). In
other words, a single random draw of a Gaussian matrix A is
able to stably recover all s-sparse signals x⋆ and all k-sparse
corruptions z⋆ simultaneously with high probability. On the
other hand, for structured sensing matrices, the nonuniform
recovery guarantees2 can be proved for randomly subsampled
orthonormal matrix [11] and its generalized model - bounded
orthonormal systems3 [10]. Very recently, the uniform recovery guarantee for bounded orthonormal systems is shown in
[13].
In this paper, we prove the uniform recovery guarantee for
two different corrupted sensing models. In the first model, the
measurement matrix is based on randomly modulated unitnorm frames [7] and the corruption is sparse on the identity
basis. It is noted that the measurement matrix in the first model
does not consist of a random subsampling operator, e.g., the
partial random circulant matrix [14]. For the second model,
we consider
y = Ax⋆ + Hz⋆ + w,

(4)

where A represents a randomly subsampled orthonormal matrix, and the corruption Hz⋆ is assumed to be sparse on
1 Recent works [8] [9] for subsampled Fourier matrices show that the factor
log4 n can be reduced to log3 n.
2 A nonuniform recovery result only states that a fixed pair of sparse signal
and sparse corruption can be recovered with high probability using a random
draw of the matrix. Sometimes, the signs of the non-zero coefficients of the
sparse vector (and corruption) can be chosen at random to further simplify
arguments. Uniform recovery is stronger than nonuniform recovery. (see [5,
Chapter 9.2] [6, Section 3.1] for more details.)
3 See [12] for the construction of the generalized model.

2

certain bounded domain (e.g., a discrete Fourier transform
(DFT) matrix). Our results imply that many structured sensing
matrices can be employed in the corrupted sensing model
to ensure the exact and stable recovery of both x⋆ and z⋆ ,
even when the sparsity of the corruption is up to a constant
fraction of the total number of measurements. Thanks to
the uniform recovery guarantee, our results can address the
adversarial setting, which means that exact and stable recovery
is still guaranteed even when x⋆ , z⋆ and w are selected
given knowledge of the sensing matrix A. In addition, our
analysis results are also applicable to demonstrate the recovery
guarantee when the corrupted sensing problem is solved via
nonconvex optimization.
A. Potential Applications
The problem of recovering sparse signal x⋆ and sparse
corruption z⋆ from the measurement vector y arise from many
applications, where the compressed measurements may be
corrupted by impulse noise.
For example, in a sensor network, each sensor node measures the same signal x⋆ independently before sending the
outcome to the center hub for analysis. In this setting, each
sensor makes the measurement hai , x⋆ i, and the resultant
measurement vector is Ax⋆ by arranging each ai as the rows
of A [11], [15]. However, in practice, some sensor readings
can be anomalous from the rest. These outliers could be caused
by individually malfunctioned sensors, or due to some unusual
phenomena or event happening in certain areas of the network
[16] [17]. This anomaly effect can be modeled by a sparse
vector z⋆ . Mathematically, we have y = Ax⋆ + z⋆ + w,
where z⋆ represents the outlier regions and w stands for
possible small noise in the data transmission. Our results make
it possible to recover both the underlying signal and detect the
outlier regions simultaneously, which could be very useful for
network monitoring.
Another application of sparse signal recovery from sparsely
corrupted measurements is error correction in joint sourcechannel coding. In [11], [18], [19], compressed sensing has
been exploited as a joint source-channel coding strategy for
its efficient encoding and robust error correcting performance.
For a signal f that is sparse in the domain Ψ, i.e., f = Ψx⋆ ,
it can be encoded by a linear projection y = Φf = Ax⋆
with A = ΦΨ. Existing works have investigated the situations
where the encoded signal y is sent through either an erasure
channel [18] or a gross error channel [11], [19]. Our results
can not only be applied in these scenarios, but also provide
a new design on the encoding matrix with uniform recovery
guarantee.
In some scenarios, the measurement noise may be sparse or
compressible in some sparsifying basis. One example is the
recovery of video or audio signal that are corrupted by narrowband interference (NBI) due to improper designed equipment
[20], [21]. Electric hum as a typical impairment is sparse
in the Fourier basis. Another example is the application of
compressed sensing to reduce the number of samples in convolution systems with deterministic sequences (e.g., m-sequence,
Golay sequence). Such convolution systems are widely used in

communications, ultrasound and radar [22], [23]. In practice,
the measurements may be affected by frequency domain
interference or multi-tone jamming [24]. For instance, in CSbased OFDM channel estimation [25]–[28], suppose x is the
channel response and that the pilot sequence g is constructed
from Golay sequences, thep
time-domain received signal can be
n
RΩ′ F∗ diag(g)Fx + w, where
represented as [28], y = m
′
RΩ is a random subsampling operator and F denotes the
DFT matrix. The recovery performance can be guaranteed
by noticing that the sensing model is a subsampled version
of the orthonormal matrix F∗ diag(g)F. However, in OFDMbased powerline communications, the NBI due to intended
or unintended narrow-band signals can severely contaminate
the transmitted OFDM signal. The time-domain NBI vector is
sparse in the Fourier basis [29], [30]. Our results cover these
settings, and therefore, provide a CS-based method to jointly
estimate the signal of interest and the NBI.
B. Notations and Organization of the paper
For an n-element vector a, we denote by ai , (i ∈ [n] =
{0, ..., n − 1}), the i-th element of this vector. We represent a
sequence of vectors by a0 , ..., an−1 and a column vector with
q ones by 1q . The sparsity of a vector can be measured by its
best s-term approximation error,
σs (a)p =

inf ka − ãkp ,

kãk0 ≤s

where k · kp is the standard lp norm on vectors. For a
matrix A, Ajk denotes the element on its j-th row and kth column. The vector obtained by taking the j-th row (k-th
column) of A is represented by A(j,:) (A(:,k) ). We denote by
A0 , ..., An−1 a sequence of matrices. A−1 and A∗ represent
the inverse and the conjugate transpose of A. The Frobenius
norm and the
p operator norm of matrix A are denoted by
kAkF =
tr(A∗ A) and kAk2→2 = supkxk2 =1 kAxk2
respectively. We write A . B if there is an absolute constant
c such that A ≤ cB. We denote A ∼ B if c1 A ≤ B ≤ c2 A
for absolute constants c1 and c2 .
The coherence µ(A) of an ñ × n matrix A describes the
maximum magnitude of the elements of A, i.e., µ(A) =
max1≤j≤ñ |Ajk |. For a unitary matrix Ψ ∈ Cn×n , we have
√1
n

1≤k≤n

≤ µ(Ψ) ≤ 1.
The rest of the paper is organized as follows. We start by
reviewing some key notions and results in compressed sensing
in Section II. In Section III, we prove the uniform recovery
guarantee for two classes of structured random matrices. In
Section IV, we conduct a series of simulations to reinforce
our theoretical results. Conclusion is given in Section V. We
defer most of the proofs to the Appendices.
II. P RELIMINARIES
A. RIP and structured sensing matrices
The restricted isometry property (RIP) is a sufficient condition that guarantees uniform and stable recovery of all s-sparse
vectors via nonlinear optimization (e.g. l1 -minimization). For a

3

matrix A ∈ Cm×n and s < n, the restricted isometry constant
δs is defined as the smallest number such that
(1 − δs )kxk22 ≤ kAxk22 ≤ (1 + δs )kxk22 ,
holds for all s-sparse vectors x. Alternatively, the restricted
isometry constant of A can be written as
δs = sup
x∈Ds,n

kAxk22 − kxk22 ,

(5)

where Ds,n = {x ∈ Cn : kxk2 ≤ 1, kxk0 ≤ s}.
Among the many structured sensing matrices that satisfy the
RIP, two classes have been found to be applicable in various
scenarios. One is the randomly subsampled orthonormal systems [6], which encompass structured sensing matrices like
partial random Fourier [2], convolutional CS [28], [31] and
spread spectrum [32]. The other is the UDB framework which
consists of a unit-norm tight frame (UTF), a random diagonal
matrix and a bounded column-wise orthonormal matrix [7].
Popular sensing matrices under this framework include partial
random circulant matrices [14], random demodulation [33],
random probing [34] and compressive multiplexing [35].

B. Recovery Condition
We review the definition of generalized RIP, which is
useful to establish robustness and stability of the optimization
algorithm.
Definition II.1. [10, Definition 2.1] For any matrix Θ ∈
Cr×(n+m) , it has the (s, k)-RIP with constant δs,k if δs,k is
the smallest value of δ such that
(1 −

δ)(kxk22

+

kzk22 )

 
x
≤ Θ
z

2
2

≤ (1 + δ)(kxk22 + kzk22 )
(6)

holds for any x ∈ Cn with kxk0 ≤ s and any z ∈ Cm with
kzk0 ≤ k.
Here, the generalized RIP is termed as the (s, k)-RIP for
convenience. We note that the (s, k)-RIP is more stringent
than the conventional RIP. In other words, the fact that a
sensing matrix A satisfies the RIP does not mean that the
associated matrix Θ = [A, I] would satisfy the (s, k)-RIP.
The recovery performance of the penalized optimization (3)
can be guaranteed by the following result.
⋆

⋆

Theorem II.2. [13, Theorem 3.7] Suppose y = Ax +z +w
and Θ = [A, I] ∈ Cm×(n+m) has the (2s, 2k)-RIP constant
δ2s,2k satisfying
δ2s,2k < r

1+

1


1
√
2 2

+

√ 2
η

2

s+λ k
⋆
∈ Cn , z⋆ ∈ Cm , and
with η = min{s,λ
2 k} . Then for x
m
w ∈ C with kwk2 ≤ ε, the solution (x̂, ẑ) to the penalized
optimization problem (3) satisfies

kx̂ − x⋆ k1 + kẑ − z⋆ k1 ≤ c1 (σs (x)1 + λσk (z))
p
+ c2 s + λ2 kε

  σ (x)

σ (z)
s
√ 1 + k√ 1
kx̂ − x⋆ k2 + kẑ − z⋆ k2 ≤ c3 1 + η 1/4
s
k


1/4
ε,
+ c4 1 + η
where the constants c1 , c2 , c3 , c4 depend on δ2s,2k only.
We note that similar theorem has been proven in [10] when
both the signal and corruption are vectors with exact sparsity.
The above result not only relaxes the requirement on the
(2s, 2k)-RIP constant, but also guarantees stable recovery of
inexactly sparse signals and corruptions. Therefore, for either
sparse or compressible signals and corruptions, the key to
establish the recovery guarantee for a sensing matrix is to
prove the (s, k)-RIP.
III. M AIN R ESULTS
In this section, we prove the (s, k)-RIP for two classes of
structured sensing matrices. This result can then be combined
with Theorem II.2 to prove the recovery guarantee. In addition,
the extension to the recovery via nonconvex optimization is
presented. Last but not least, we compare the main theorems
to existing literature where relevant.
A. Randomly modulated unit-norm tight frames
We prove the uniform recovery guarantees for the class
of structured sensing matrices that can be written as A
=
e where U ∈ Cm×ñ is a UTF with µ(U) ∼ 1/√m,
UDB,
D = diag(ξ) is a diagonal matrix with ξ being a lengthñ random vector with independent, zero-mean, unit-variance,
e ∈ Cñ×n , ñ ≥ n, represents
and L-subgaussian entries, and B
e ∗B
e = I.
a column-wise orthonormal matrix, i.e. B
The following result presents a bound on the required number of measurements m such that the corresponding matrix
Θ has the (s, k)-RIP constant satisfying δs,k ≤ δ for any
δ ∈ (0, 1).
Theorem III.1. Suppose y = Ax⋆ + z⋆ + w with√ Θ =
e and µ(U) ∼ 1/ m. If,
[A, I] ∈ Cm×(n+m) , A = UDB
for δ ∈ (0, 1),
e log2 s log2 ñ,
m ≥ c5 δ −2 sñµ2 (B)

m ≥ c6 δ −2 k log2 k log2 ñ,

where c5 and c6 are some absolute constants, then with
2
probability at least 1 − 2ñ− log s log ñ , the (s, k)-RIP constant
of Θ satisfies δs,k ≤ δ.
Proof. The (s, k)-RIP constant δs,k can be equivalently expressed as
  2
x
Θ
δs,k = sup
(7)
− kxk22 − kzk22 ,
z 2
(x,z)∈T

4

where T := {(x, z) : kxk22 + kzk22 = 1, kxk0 ≤ s, kzk0 ≤
k, x ∈ Cn , z ∈ Cm }. With Θ = [A, I], the RIP-constant can
be further reduced to
δs,k = sup
(x,z)∈T

≤ sup

(x,z)∈T

|

kAxk22 + kzk22 + 2hAx, zi − kxk22 − kzk22
kAxk22 − kxk22 + 2 sup |hAx, zi|
{z

}

δ1

|

(x,z)∈T

{z
δ2

(8)

}

Our aim is to derive bounds on the number of measurements
m such that for any δ ∈ (0, 1) the RIP-constant δs,k is upper
bounded by δ. We have
kAxk22 − kxk22

δ1 ≤ sup

x∈Ds,n

(9)

with supx∈Ds,n kAxk22 − kxk22 being the restricted isometry
constant in the standard RIP definition (5). Then, by [7,
Theorem III.2], we reach the following result.
Suppose, for any δ ∈ (0, 1),
2
e
m ≥ 4c1 δ −2 sñµ2 (B)(log
s log2 ñ),

then δ1 ≤ δ/2 holds with probability at least 1 −
2
ñ−(log ñ)(log s) .
Therefore, proof of the (s, k)-RIP is reduced to bounding
the inner product term δ2 .
e zi| = 2 sup |z∗ UDBx|
e
δ2 = 2 sup |hUDBx,
(x,z)∈T

(x,z)∈T

e
= 2 sup |z Udiag(Bx)ξ|
= 2 sup |hv, ξi|,
∗

(x,z)∈T

(10)

v∈Av

∗
e
where v = (z∗ Udiag(Bx))
, and

Av := {v : kxk22 + kzk22 = 1, kxk0 ≤ s, kzk0 ≤ k}.

(11)

The following lemma is proved in Appendix A.
Lemma III.2. Suppose ξ is a length-ñ random vector with
independent, zero-mean, unit-variance, and L-subgaussian
entries. For any δ ∈ (0, 1), if
e log2 s log2 ñ
m ≥ c5 δ −2 sñµ2 (B)

m ≥ c6 δ −2 k log2 k log2 ñ,

then supv∈Av |hv, ξi| ≤ δ/2 holds with probability exceeding
1 − exp(− log2 s log2 ñ), where c5 and c6 are some constants
depending only on L.
Combining (10) with Lemma III.2, we have, for any
τ > 0, δ2 ≤ cδ holds with probability exceeding 1 −
exp(− log2 s log2 ñ) for some constant c.
Finally, Theorem III.1 can be obtained by combining
the above results. Suppose, for any δ ∈ (0, 1), m ≥
2
e
c5 δ −2 sñµ2 (B)(log
s log2 ñ), m ≥ c6 δ −2 k log2 m log2 ñ and
√
µ(U ) ∼ 1/ m, then we have δs,k ≤ δ1 + δ2 ≤ δ with
probability exceeding
1 − ñ−(log ñ log

2

s)

= 1 − ñ−(log ñ log

= 1 − 2ñ− log

2

− exp(−c log2 s log2 ñ)

2

s)

s log ñ

− ñ−c log

2

s log ñ

The uniform recovery guarantee can be obtained by combining Theorem II.2 and III.1.
e is a bounded
A few remarks are in order. First, when B
√
e
column-wise orthonormal matrix, i.e., µ(B) ∼ 1/ ñ, the
bound on the sparsity of x⋆ can be relaxed to kx⋆ k0 ≤
Cm/(log2 ñ log2 m). The sparsity kz⋆ k0 is always a constant
fraction of the total number of measurements m regardless
e When kwk2 = 0,
the magnitude of the coherence µ(B).
Theorem III.1 implies that a sparse signal can be exactly
recovered by tractable l1 minimization even if some parts of
the measurements are arbitrarily corrupted.
Second, the proposed class of structured sensing matrices
is equivalent to the UDB framework
√ [7] but with an additional requirement of µ(U) ∼ 1/ m. The UDB framework
has been proved to support uniform recovery guarantees for
conventional CS problem, while with the extra condition it
is now shown to provide uniform recovery guarantees for the
CS with sparse corruptions problem. Theorem III.1 holds for
many existing and new structured sensing matrices as long as
e
they can be decomposed into A = UDB.
One application of the UDB framework is to simplify
the mask design in double random phase encoding (DRPE)
for optical image encryption. Consider an image f that is
sparse in the domain Ψ, i.e., f = Ψx⋆ , DRPE is based
on random masks placed in the input and Fourier planes
of the optical system [36], [37] . p
Mathematically, the mean
∗
surements can be written as y =
m RΩ F Λ1 FΛ2 f + w,
n
m
where RΩ : C → C represents an arbitrary/deterministic
subsampling operator with Ω being the set of selected row
indices, Λ1 and Λ2 are random diagonal matrices. By the
UDB framework, the random diagonal matrix Λ2 can be
replaced by a deterministic diagonal matrix constructed from a
Golay sequence g. The reason is that the measurement model
p
n
RΩ F∗ Λ1 Fdiag(g)Ψx⋆ can be decomposed into a UTF
pm
n
∗
m RΩ F , a random diagonal matrix Λ1 , and a orthonormal
matrix Fdiag(g)Ψ whose coherence is proven to be bounded
for many orthonormal transforms Ψ, e.g., DCT, Haar wavelet
[7, Lemma IV.2]. When the measurements are corrupted by
impulse noise due to detector plane impairment, our theorem
above provides a recovery guarantee on the image.
Furthermore, the UDB framework emcompasses some popular structured sensing matrices, e.g., partial random circulant
matrices [14] and random probing [34]. To elaborate, consider
the partial random circulant matrices
1
A = √ R Ω Cǫ
m
where Cǫ denotes the circulant matrix generated from ǫ.
Suppose ǫ = F∗ ξ, where F is a normalized DFT matrix and ξ
is a length-n random vector with independent, zero-mean, unitvariance,
entries. Let D = diag(ξ),
p nwe have∗
p nand sub-Gaussian
RΩ F∗ DF. It can be observed that U = m
RΩ F
A= m
is a UTF and B = F is a unitary matrix. Hence, Theorem
III.1 implies that any sparse signal x and sparse corruption
z can be faithfully recovered from the measurement model
y = √1m RΩ Cǫ x⋆ + z⋆ + w by the penalized recovery

5

algorithm. The sparse recovery from partial random circulant
measurements can be applied in many common deconvolution
tasks, such as radar [38] and coded aperture imaging [39]. In
practice, where the measurements can be corrupted by impulsive noise due to bit errors in transmission, faulty memory
locations, and buffer overflow [40], our theorem guarantees
the recovery of both the signal of interest and the corruption.
In some situations, the proposed framework can still provide
reliable recovery guarantee even if the corruption is sparse in
some basis. Suppose the corruption is sparse under some fixed
and known orthonormal transformation H, i.e. H∗ H = I. We
consider the measurement model
y = Ax⋆ + Hz⋆ + w.

(12)

It is clear that this setting can be reduced to
H∗ y = H∗ Ax⋆ + z⋆ + H∗ w.

(13)

e := UD
b B,
e where U
b = H∗ U
Notice that H∗ A = H∗ UDB
is still a UTF
due to the orthogonality of H. Therefore, if
b ∼ 1/√m, Theorem III.1 still holds in this measurement
µ(U)
model.
B. Randomly sub-sampled orthonormal system
Next, we consider the corrupted sensing measurement
model for randomly sub-sampled orthonormal system. We
prove the uniform recovery guarantee for such matrices provided that the corruption is sparse on certain sparsifying
domain. Suppose λ ∈ Rn is a random Bernoulli vector
with i.i.d. entries such that P(λi = 1) = m
n ∀i ∈ [n] and
Ω′ = {i : λi = 1} with |Ω′ | = M , the random sampling
operator RΩ′ ∈ RM×n is a collection of the i-th row of an ndimensional identity matrix for all i ∈ Ω′ . Here, M is random
with mean value m. The observation model is
y = Ax⋆ + Hz⋆ + w,
p

(14)

n
where A = M
RΩ′ G, G ∈ Cn×n is an orthonormal
√ basis
M×M
and H ∈ C
is a unitary matrix with µ(H) ∼ 1/ M .
From our analysis in previous subsection, the uniform
recovery performance can be guaranteed as long as the associated matrix Θ satisfies the (s, k)-RIP. Since the matrix A
satisfies the standard RIP, the problem of proving the (s, k)RIP is again reduced to bounding the inner product term
sup(x,z)∈T |hAx, Hzi|. Detail proof of the following result
is given in Appendix B.

When
G is a bounded orthonormal basis, i.e., µ(G) ∼
√
1/ n, the bound on the sparsity of x⋆ can be relaxed to
m ≥ O(δ −2 s log2 s log2 n, δ −2 k log2 k log2 n), which implies
that a sparse signal can be exactly recovered by tractable l1
minimization even if the measurements are affected by corruption sparse on some bounded domain. A bounded orthonormal
basis can include the Fourier transform or the Hadamard
transform. In addition, in CS-based OFDM where the pilot is
generated from a Golay sequence and a random subsampler is
employed at the receiver (Section I-A), the effective orthonor√
mal basis is also bounded, i.e., µ(F∗ diag(g)F) ∼ 1/ n [28].
C. Nonconvex optimization
We have shown the (s, k)-RIP for two popular classes
of structured sensing matrices, and proven the performance
guarantee for the recovery of the sparse signal and corruption
via the l1 -norm minimization algorithm (3). However, our
(s, k)-RIP analysis on the structured sensing matrices is also
applicable to proving the recovery guarantee for nonconvex
optimization. Consider the following formulation of the problem
y = Ax⋆ + Hz⋆ ,

(15)

It was demonstrated in [41] that the unique minimizer of the
lp minimization problem (0 < p < 1)
min kxkpp + νkzkpp
x,z

s.t.

Ax + Hz = y,

(16)

is exactly the pair (x⋆ , z⋆ ) if the combined matrix [A, H]
satisfies the (s, k)-RIP, where ν is the regularization parameter.
In addition, the lp minimization approach still provides stable
recovery even when there is additional dense noise as long as
the (s, k)-RIP holds [41], [42]. The lp minimization problem
can be numerically solved via an iteratively reweighted least
squares (IRLS) method [43]. However, [41] only considers
the sensing model with A being random Gaussian matrices
and H being an identity matrix. With our (s, k)-RIP analysis,
many structured sensing matrices can be employed to provide
exact/stable recovery performance for this corrupted sensing
problem via lp minimization.
D. Comparison with related literature

In this part, we compare our main results with related
literature.
1) Sparse signal, sparse corruption: [10] proved that
sensing matrices with independent Gaussian entries provide
Theorem III.3. Suppose y p
= Ax⋆ + Hz⋆ + w with √
Θ = uniform recovery guarantee for corrupted CS by solving (3) for
n
M×(n+M)
RΩ′ G and µ(H) ∼ 1/ M . all vectors x⋆ and z⋆ satisfying kxk0 ≤ αm/(log(n/m) + 1)
[A, H] ∈ C
,A= M
If, for δ ∈ (0, 1),
and kz⋆ k0 ≤ αm. The difference is that our theorems come
with a tighter requirement on the sparsity of x⋆ and the
m ≥ max(c7 δ −2 snµ2 (G) log2 s log2 n, c8 δ 2 s log4 n, 2c9 log n), sparsity of z⋆ , which is a compensation on the employment
m ≥ c10 δ −2 knµ2 (G) log2 k log2 n,
of structured measurements.
2
[10] also proved the recovery guarantee for structured
m ≤ c11 δ n,
sensing matrices that belong to the framework proposed
where {ci }i=7,...,11 are constants, then with probability at least in [12]. Here, faithful recovery is guaranteed provided that
2
1−2ñ− log s log n −n−c9 , the (s, k)-RIP constant of Θ satisfies kxk0 ≤ αm/(µ2 log2 n) and kz⋆ k0 ≤ βm/µ2 , where µ is the
δs,k ≤ δ.
coherence of the sensing matrix. [11] considered the corrupted

6

CS with sensing matrices that are randomly subsampled orthonormal matrix, and proved similar results. It is noted that
the requirements on the sparsity of x⋆ in these works seem less
strict than that in our results. However, in both [10] and [11],
performance guarantees of their structured sensing matrices
rely on the assumption that the support set of x⋆ or z⋆ is
fixed and the signs of the signal are independently and equally
likely to be 1 or −1 [10, Section 1.3.2] [11, Section II.B]
(i.e. a nonuniform recovery guarantee). While in our theorem,
two classes of structured sensing matrices (including randomly
subsampled orthgonal matrix) are shown to provide uniform
recovery guarantee for corrupted CS.
We note that recently the uniform recovery guarantee for
bounded orthonormal systems is proven in [13]. The bounded
orthonormal systems is more general than the random subsampled orthonormal matrix considered in our second class.
However, the corruption models are different: the corruption
vector in [13] is sparse in time domain, whereas our theorem
considers
corruption in sparsifying domain with µ(H) ∼
√
1/ M . Due to this difference in the corruption model, the
techniques used to prove the (s, k)-RIP (specifically, bound the
inner product sup(x,z)∈T |hAx, Hzi|) are essentially different.
2) Structured signal, structured corruption: In a recent
work [44], sensing with random Gaussian measurements for
general structured signals and corruptions (including sparse
vectors, low rank matrix, sign vectors and etc) has been
proven. However, our study departs from it in the following aspects: [44] proved a nonuniform recovery guarantee
for the recovering of sparse signals from sparse corruptions
and dense noise. In our paper, we established a uniform
recovery guarantee for the corresponding problem. Moreover,
[44] considered random Gaussian matrices, while we propose
structured sensing matrices.
We have shown that a large class of structured sensing
matrices can provide faithful recovery for the sparse sensing
with sparse corruption. Whether such structured measurements
can be applied in a general corrupted sensing problem (e.g.
structured signal with structured corruption) is still open.
Extension of our measurement framework to the general
corrupted sensing problem is interesting for further study.
Other works related to the recovery of signals from corrupted measurements include [20], [45]–[51]. However, their
models are different from the one in our paper.
Remark III.4. We note that the value
p of the regularization
parameter can be chosen as λ = s/k. In practice, when
no a priori knowledge on the sparsity levels of the signal and
the corruption is available, λ can usually be taken by cross
validation. On the other hand, if it is known a priori that
the corruption (the signal) is very sparse, one can increase
(decrease) the value of λ to improve the overall recovery performance. Similar discussion on the theoretical and practical
settings of the regularization parameter has also been noted in
[10, Section 1.3.3], [11, Section II.E, Section VII], [44, Section
III.B]. In addition, an iteratively reweighted l1 minimization
method can be used to adaptively improve the setting of λ in
practice [13].

IV. N UMERICAL S IMULATIONS
In this section, we verify and reinforce the theoretical
results of Section III with a series of simulations. We present
experiments to test the recovery performance of the penalized
recovery algorithm for the proposed structured sensing matrices. In each experiment, we used the CVX Matlab package
[52], [53] to specify and solve the convex recovery programs.
Two different ways of generating sparse vectors are considered:
• Gaussian setting: the nonzero entries are drawn from
a Gaussian distribution and their locations are chosen
uniformly at random,
• Flat setting: the magnitudes of nonzero entries are 1 and
their locations are chosen uniformly at random.
A. Penalized Recovery
This experiment is to investigate the empirical recovery
performance of the penalized recovery algorithm (3) when
the dense noise is zero. Here, the sensing matrix (Mtx-I)
A = UDB of size m × n with m = 256 and n = 512
is constructed as below.
1) Arbitrarily select m = 256 rows from a 512 × 512
Hadamard matrix√to form a new matrix, which is then
normalized by 1/ m to form the UTF U.
2) The diagonal entries of the diagonal matrix D are i.i.d.
Bernoulli random variables.
3) B is a normalized Hadamard matrix.
We vary the signal sparsity and the corruption sparsity with
s ∈ [1, 100] and k ∈ {10, 20, 30}. For each pair of (s, k),
we draw a sensing matrix as described above and perform the
following experiment 100 times:
1) Generate x⋆ with sparsity s by the Gaussian setting
2) Generate z⋆ with sparsity k by the Gaussian setting
3) Solve (3) by setting λ = 1
4) Declare success if4
kx̂ − x⋆ k2 /kx⋆ k2 + kẑ − z⋆ k2 /kz⋆ k2 < 10−3
The fraction of successful recovery averaged over the 100 iterations is presented in Fig. 1a. To demonstrate the performance
for signals and corruptions that do not have i.i.d. signs, the
experiment is repeated by generating the sparse vectors x⋆
and z⋆ based on the Flat setting as shown in Fig. 1b. It can be
seen that in both scenarios the performance improves as the
sparsity of the corruption decreases.
Next, we demonstrate the performance of the penalized recovery algorithm when the sensing matrix is from a randomly
subsampled orthonormal matrix. The sensing matrix (Mtx-II)
A is a collection of randomly selected M = 256 rows
p from
a 512 × 512 Hadamard matrix, and normalized by n/M .
The corruption is Hz, where H is an M × M normalized
Hadamard matrix. For each pair of (s, k), we repeat the above
steps 100 times to obtain the probability of success (see Fig.
2). It is noted that the recovery performance of Mtx-I is better
than that of Mtx-II. This seems consistent with our theoretical
analysis as the random subsampled orthonormal matrix shows
4 This

criterion indicates that both x⋆ and z⋆ have been faithfully recovered.

7

1

1
k=10
k=20
k=30

0.8
Probability of success

Probability of success

0.8

k=10
k=20
k=30

0.6

0.4

0.2

0.6

0.4

0.2

0

0
0

20

40

60

80

100

0

20

Signal sparsity

40

60

80

100

Signal sparsity

(a) Gaussian Setting

(b) Flat Setting

Fig. 1. Probability of success as a function of the signal sparsity s using penalized recovery with signal dimension n = 512, number of measurements
m = 256, and the corruption sparsity k = {10, 20, 30} for Mtx-I.

1

1
k=10
k=20
k=30

0.8
Probability of success

Probability of success

0.8

k=10
k=20
k=30

0.6

0.4

0.2

0.6

0.4

0.2

0

0
0

20

40

60

80

100

0

20

Signal sparsity

40

60

80

100

Signal sparsity

(a) Gaussian Setting

(b) Flat Setting

Fig. 2. Probability of success as a function of the signal sparsity s using penalized recovery with signal dimension n = 512, number of measurements
m = 256, and the corruption sparsity k = {10, 20, 30} for Mtx-II.

more stringent recovery condition than the UDB framework
(see Theorem III.1 and III.3). However, since the (s, k)-RIP
is a sufficient condition for the recovery guarantee, it may not
fully reflect the performance gap between the two classes of
structured sensing matrices. Further investigation based on a
necessary and sufficient condition for the recovery guarantee
of the corrupted CS problem is a difficult, but interesting open
question.

B. Stable recovery
We study the stability of the penalized recovery algorithms
when the dense noise is nonzero, i.e., ε 6= 0, and compare
the performance of structured sensing matrix (Mtx-I) with
random Gaussian sensing matrix. In this experiment, the 256by-512 sensing matrix (Mtx-I) is constructed as in previous
subsection. We fix the signal and corruption sparsity levels at
s = 10 and k = 10 respectively. The dense noise w consists
of i.i.d. Bernoulli entries with amplitude ε. We vary the noise
level with ε ∈ [0, 0.1], and perform the following experiment
100 times for each ε:

8

of the set. For a metric space (T, d), the covering number
N (T, d, u) is the minimal number of open balls of radius u
needed to cover (T, d). A subset T of T is called a u-net of
T if every point x ∈ T can be approximated to within u by
some point x̄ ∈ T , i.e., d(x, x̄) ≤ u. The minimal cardinality
of T is equivalent to the covering number N (T, d, u). The pth moment (or the Lp -norm) of a random variable is denoted
by kXkLp = (E|X|p )1/p .
We aim to upper bound the variable ∆ := supv∈Av |hv, ξi|
which is the supremum of a stochastic process with the index
set Av . To complete the proof, we require the following
important result due to Krahmer et al.:

3
p-rec Mtx-I
p-rec Gaussian
noncvx Mtx-I
noncvx Gaussian

Recovery error

2.5

2

1.5

1

0.5

0
0

0.02

0.04

0.06

0.08

0.1

Noise level

Theorem A.1. [14, Theorem 3.5 (a)] Let A be a set of
matrices, and let ξ be a random vector whose entries ξj are
independent, mean 0, variance 1, and L-subgaussian random
variables. Set
dF (A) = sup kSkF ,

d2→2 (A) = sup kSk2→2 ,

S∈A

Fig. 3. Empirical recovery error versus the noise level ε.

S∈A

1) Generate x⋆ with s = 10 by the Gaussian setting
2) Generate z⋆ with k = 10 by the Gaussian setting
3) Solve penalized recovery (p-rec) algorithm (3) by setting
λ=1
4) Record the empirical recovery error kx̂ − x⋆ k2 + kẑ −
z⋆ k2
An average recovery error is then obtained for each ε. Fig. 3
depicts the average error with varying noise levels. The results
in Theorems II.2 and III.1 imply that the recovery errors are
bounded by the noise level ε up to some constants. Fig. 3
clearly shows this linear relationship. In addition, we repeat the
above experiments with an iteratively reweighted least squares
approach [43] using p = 0.5. As shown in Fig. 3, the structured
sensing matrix is still able to exhibit stable performance by the
nonconvex optimization algorithm.
V. C ONCLUSION
We have studied a generalized CS problem where the
measurement vector is corrupted by both sparse noise and
dense noise. We have proven that structured random matrices
encompassed in the UDB framework or the randomly subsampled orthonormal system can satisfy the sufficient condition,
i.e., the (s, k)-RIP. These structured matrices can therefore be
applied to provide faithful recovery of both the sparse signal
and the corruption by the penalized optimization algorithm as
well as the nonconvex optimization algorithm. Our simulations
have clearly illustrated and reinforced our theoretical results.
A PPENDIX A
P ROOF OF L EMMA III.2
Throughout the proof in this and the following sections, C
and c denote an absolute constant whose values may change
from occurrence to occurrence.
A metric space is denoted by (T, d), where T is a set
and d is the notion of distance (metric) between elements

S∈A

NA (ξ) := sup kSξk2 ,

E = γ2 (A, k · k2→2 ) + dF (A).

Then, for every p ≥ 1,
kNA (ξ)kLp ≤ C(E +

√
pd2→2 (A)),

(17)

where C is a constant depends only on L.
Here, NA (ξ) represents the supremum of certain stochastic
processes indexed by a set of matrices A. The above Proposition implies that NA (ξ) can be bounded by three parameters:
the suprema of Frobenius norms dF (A), the suprema of
operator norms d2→2 (A) and a γ2 -functional γ2 (A, k · k2→2 ),
which can be bounded in terms of the covering numbers
N (A, k · k2→2 , u) as below.
γ2 (A, k · k2→2 ) ≤ c

Z

0

d2→2 (A)

p
log N (A, k · k2→2 , u) du,

where the integral is known as Dudley integral or entropy
integral [54].
We can transfer the estimates on the moment (17) to a tail
bound by the standard estimate due to Markov’s inequality
(see [5, Proposition 7.15]).
Proposition A.2. Following the definitions in Theorem A.1,
for t ≥ 1,
P(NA (ξ) ≥ CE + Cd2→2 (A)t) ≤ exp(−t2 ).

(18)

It can be observed that ∆ can be expressed in the form
of NA (ξ), where S and A are replaced with v and Av ,
respectively. Now, we only need to estimate the parameters
dF (Av ), d2→2 (Av ) and γ2 (Av , k · k2→2 ) before bounding ∆
by using Theorem A.2. Since Av is a set of vectors, we have
dF (Av ) = d2→2 (Av ) and γ2 (Av , k · k2→2 ) = γ2 (Av , k · k2 ).
For any vector x ∈ Ds,n , we denote by xs the lengths vector that retains only the non-zero elements in x. And
correspondingly for any vector b ∈ Cn , we denote by bs
the length-s vector that retains only the elements that have

9

the same indexes as those of the non-zero elements in x. We
have, for any v ∈ Av ,
∗
e
e
kvk2 = kz∗ Udiag(Bx)k
2 ≤ kz Uk2 kBxk∞
r
ñ
e (j,:) , xi|}
=
kzk2 max{|hB
m
j∈[ñ]
r
ñ
e s , xs i|}
kzk2 max{|hB
=
(j,:)
m
j∈[ñ]
r
r
ñ e √
1 ñ e √
µ(B) skxk2 kzk2 ≤
µ(B) s,
≤
m
2 m

where the last inequality is due to

kxk22 +kzk22

dF (Av ) = d2→2 (Av ) ≤

1
2

r

e
e − z̄∗ Udiag(Bx̄)k
kv − v̄k2 = kz∗ Udiag(Bx)
2
∗
∗
e
e
= kz Udiag(Bx) − z Udiag(Bx̄)

e − z̄∗ Udiag(Bx̄)k
e
+ z∗ Udiag(Bx̄)
2
∗
∗
e
e
≤ kz Udiag(B(x − x̄))k2 + k(z − z̄) Udiag(Bx̄)k
2

= 1. Therefore,

ñ e √
µ(B) s.
m

(19)

∗
e
e
kvk2 = kz∗ Udiag(Bx)k
2 ≤ kz Uk∞ kBxk2
√
1
≤ µ(U) k.
2

This provides another upper bound
√
1
µ(U) k.
2

(20)

We note that both (19) and (20) are valid bounds, and
they are not comparable to each other since the relationship
between s and k is unknown. It will be clear later that both
bounds are useful for computing the entropy integrals. In
particular, (19) and (20) are used for computing I1 and I2
respectively (as in (23)).
Next, we bound γ2 -functional γ2 (Av , k · k2 ) by estimating
the covering numbers N (Av , k · k2 , u). The derivation is
divided into two steps.
Step 1. Decompose N (Av , k · k2 , u). Let D1 = {x ∈ Cn :
kxk22 ≤ 1, kxk0 ≤ s} and define the semi-norm k · kK1 as
e
kxkK1 = kUdiag(Bx)k
2→2

∀x ∈ Cn .

(21)

For the metric space (D1 , k · kK1 ), we take D1 to be a u2 -net
of D1 with |D1 | = N (D1 , k · kK1 , u2 ). Let D2 = {z ∈ Cm :
kzk22 ≤ 1, kzk0 ≤ k} and define the semi-norm k · kK2 as
e ∗ diag(U∗ z)k2→2
kzkK2 = kB

∀z ∈ Cm .

e − x̄))k2 + kx̄∗ B
e ∗ diag(U∗ (z − z̄))k2
= kz∗ Udiag(B(x
e − x̄))k2→2
≤ kzk2 kUdiag(B(x
(a)

e ∗ diag(U∗ (z − z̄))k2→2
+ kx̄k2 kB

≤ kx − x̄kK1 + kz − z̄kK2 ≤ u,

Following the same steps, we can alternatively obtain, for
any v ∈ Av ,

dF (Av ) = d2→2 (Av ) ≤

∗
e
For any v = (z∗ Udiag(Bx))
∈ Av , there exist v̄ =
∗
e
¯
(z̄ Udiag(Bx̄)) ∈ Av with x̄ ∈ D1 and z̄ ∈ D2 obeying
kx − x̄kK1 ≤ u2 and kz − z̄kK2 ≤ u2 . This gives
∗

(22)

For the metric space (D2 , k · kK2 ), we take D2 to be a u2 -net
of D2 with |D2 | = N (D2 , k · kK2 , u2 ).
∗
e
: x̄ ∈ D1 , z̄ ∈ D2 } and
Now, let Av = {(z̄∗ Udiag(Bx̄))
remark that |Av | ≤ |D1 ||D2 |. It remains to show that for all
v ∈ Av , there exists v̄ ∈ A¯v with kv − v̄k2 ≤ u.

where (a) is due to the fact that kzk2 ≤ 1 and kx̄k2 ≤ 1.
Hence,
N (Av , k · k2 , u) ≤ |Av |
≤ N (D1 , k · kK1 , u/2)N (D2 , k · kK2 , u/2).
The γ2 -functional γ2 (Av , k · k2 ) can now be estimated by
Z d2→2 (A) p
γ2 (Av , k · k2 ) ≤ c
log N (Av , k · k2 , u)du
0
Z d2→2 (A) p
.
log N (D1 , k · kK1 , u/2) du
0
{z
}
|
+

Z

|0

I1

d2→2 (A)

p
log N (D2 , k · kK2 , u/2) du .
{z
}
I2

(23)

Step 2. Estimate the covering numbers N (D1 , k · kK1 , u/2)
and N (D2 , k·kK2 , u/2) and the entropy integrals. We estimate
each covering number in two different ways. For small value of
u, we use a volumetric argument. For large value of u, we use
the Maurey method ( [14, Lemma 4.2], or [5, Problem 12.9]).
Then, the resultant covering number estimates can be used to
compute the entropy integrals I1 and I2 . Similar techniques
on the covering number estimation and the entropy integral
computation have been used in the CS literature, i.e., [6], [7],
[14], [55].
From [7, Equation (28)] and (19), we have
r
sñ e
I1 .
µ(B)(log s)(log ñ).
(24)
m
It remains to estimate N (D2 , k · kK2 , u/2) and compute I2 .
1) small u. We observe that D2 is a subset of the union of
m
k
k unit Euclidean balls B2 ,
B2k := {z ∈ Cm : kzk2 ≤ 1, |supp(z)| ≤ k}.

For any z ∈ D2 ,

(25)

e ∗ diag(U∗ z)k2→2 ≤ kU∗ zk∞ ≤ max |hU(:,i) , zi|
kzkK2 = kB
i∈[n]
r
√
k
kzk2 ,
(26)
≤ µ(U)kzk1 ≤ µ(U) kkzk2 ≤
m

10

where the last step is due to the assumption that µ(U) ∼ √1m .
Therefore,
 
m
N (B2k , k · kK2 , u/2)
N (D2 , k · kK2 , u/2) ≤
k
r
 
k
m
k
k · k2 , u/2)
≤
N (B2 ,
m
k
r
k 1 k
em k
) (1 + 4
) ,
(27)
≤(
k
mu
where the last inequality is an application of [6, Proposition
10.1] and [5, Lemma C.5].
√
√ 2) large u. For any z ∈ D2 , we have kzk1 ≤ kkzk2 ≤
k, which gives
√
√
D2 ⊂ kB1m := {z ∈ Cm : kzk ≤ k}.
Then,

√
N (D2 , k · kK2 , u/2) ≤ N ( kB1m , k · kK2 , u/2)
√
= N (B1m , k · kK2 , u/(2 k)).
√
Based on the Maurey method, for 0 < u < 21 µ(U) k, the
covering number can be estimated by [6, Lemma 8.3]
√
p
p
log N (D2 , k · kK2 , u/2) . kµ(U) log ñ log mu−1
r
kp
log ñ log mu−1 . (28)
≤
m
We note that the estimation based on Maurey method
depends on the range of the parameter u (see [6, Lemma 8.3]),
which is the reason why we employ different bounds ((19) and
(20)) when computing the entropy integrals I1 and I2 .
We now combine the results (27) and (28) to estimate the
qen1
1
,
tropy integral I2 : we apply the first bound for 0 < u ≤ 10 m
q
q
1
k
1
1
and the second bound for 10 m < u ≤ d2→2 (Av ) = 2 m .
It reveals that
r
k
I2 .
log ñ log k.
(29)
m
Combine (23), (24) and (29)
r
sñ e
µ(B)(log s)(log ñ)
γ2 (Av , k · k2 ) .
mr
k
log ñ log k.
(30)
+
m
Finally, we are ready to complete the proof by applying
Proposition A.2. For the assumption on m and p, δ ∈ (0, 1),
e log2 s log2 ñ
m ≥ c1 δ −2 sñµ2 (B)

m ≥ c2 δ

−2

2

⋆
⋆
Recall
p nthat in the measurement model y = Ax +Hz +w,
′
A =
M RΩ G is a randomly sub-sampled unitary√matrix
M×M
and H ∈ C
is a unitary matrix with µ(H) ∼ 1/ M .
The following Lemma from [56] is needed.

Lemma B.1 (Theorem 3.3 [56]). For the matrix A =
p
n
′
m RΩ G, if for δ ∈ (0, 1),
m ≥ cδ −2 s log4 n,
then with probability at least 1 − n− log
isometry constant δs of A satisfies δs ≤ δ.

k log k log ñ,

δs,k ≤ sup

δ
, γ2 (Av , k · k2 ) . δ.
dF (Av ) = d2→2 (Av ) .
log s log ñ
By substituting the above results into Proposition A.2 (let t =
log s log ñ), one obtains
(31)

v∈Av

The proof is completed by incorporating the constant c into
c1 , c2 .

3

n

the restricted

(x,z)∈T

|

kAxk22 − kxk22 + 2 sup |hAx, Hzi|,
{z

}

δ1

|

(x,z)∈T

{z
δ2

}

(33)

where T := {(x, z) : kxk22 + kzk22 = 1, kxk0 ≤ s, kzk0 ≤
k, x ∈ Cn , z ∈ Cm }.
By Lemma B.1, we have δ1 ≤ δ/2 holds with probability
3
1 − n− log n for any δ ∈ (0, 1) if m ≥ cδ −2 s log4 n.
n
Define
q a random vector d ∈ C with i.i.d. entries satisfying

∗
′
λi = m(n−m)
di + m
n2
n . Assume Λ = diag(λ) and H RΩ =
′
U . We have,

r
n
δ2 = 2 sup |h
RΩ′ Gx, Hzi|
M
(x,z)∈T
r
n ∗ ′
z U ΛGx
= 2 sup
M
(x,z)∈T
r
n ∗ ′
= 2 sup
z U diag(Gx)λ
M
(x,z)∈T
r
1 n ∗ ′
z U diag(Gx)d
≤ 2 sup
M
(x,z)∈T 2
{z
}
|
(x,z)∈T

we have, by (19),

(32)

The (s, k)-RIP associated with Θ = [A, H] can be bounded
by

+ 2 sup

2

P( sup |hv, ξi| ≤ cδ) ≥ 1 − exp(− log2 s log2 ñ).

A PPENDIX B
P ROOF OF T HEOREM III.3

|

r

t1

m2 ∗ ′
z U Gx ,
Mn
{z
}
t2

q

≤ 21
where the last inequality is due to the fact that m(n−m)
n2
for any m ≤ n.
Since λ is a random Bernoulli vector with i.i.d. entries,
by construction d is a length-n random vector with independent, zero-mean, unit-variance, and L-subgaussian entries. Hence, the bound for t1 can be formulated as the
supremum of a stochastic process with the index Ar , where

11

pn ∗ ′
2
2
r =
M z U diag(Gx) and Ar := {r : kxk2 + kzk2 =
1, kxk0 ≤ s, kzk0 ≤ k}. For any r ∈ Ar ,
r
n ∗ ′
kz U diag(Gx)k2
krk2 =
M
r
n ∗ ∗
≤
kz H RΩ′ k2 kGxk∞
M
r
n
kzk2 max{|hG(j,:) , xi|}
=
M
j∈[n]
r
√
1 n
≤
µ(G) s,
2 M
r
n ∗ ′
kz U diag(Gx)k2
krk2 =
M
r
n ∗ ∗
≤
kz H k∞ kRΩ′ Gxk2
M
r
√
n
µ(H) kkG(Ω′ ,:) xk2
≤
M
√
1√
nµ(G)µ(H) k.
≤
2
Therefore,
r
√
1 n
µ(G) s,
dF (Ar ) ≤
2 M
√
1√
nµ(G)µ(H) k.
dF (Ar ) ≤
2
By following the same proof steps as in Appendix A, we
have
P( sup |hr, di| ≤ cδ) ≥ 1 − exp(− log2 s log2 n)

(34)

r∈Ar

provided that
M ≥ cδ −2 snµ2 (G) log2 s log2 n

M ≥ cδ −2 knµ2 (G) log2 k log2 n.

Bernstein’s inequality [57, Theorem A.1.13] gives, for any
ν > 0,


mν 2
P(M > (1 − ν)m) ≥ 1 − exp −
.
(35)
2
Hence, if
1
cδ −2 snµ2 (G) log2 s log2 n
1−ν
1
cδ −2 knµ2 (G) log2 k log2 n,
m≥
1−ν

m≥

then

P( sup |hr, di| ≤ cδ) ≥ 1 − exp(− log2 s log2 n)
r∈Ar


mν 2
− exp −
.
2
q
′ log n
, the above
By assuming m ≥ 2c′ log n and ν = 2c m
probability of success can be written as
P( sup |hr, di| ≤ cδ) ≥ 1 − n− log
r∈Ar

2

s log n

′

− n−c .

(36)

For the second term, we have
t2 = sup
(x,z)∈T
2

m2 ∗ ′
z U Gx
Mn

m
kzk2 kxk2
Mn
2
1 m
,
≤
2 Mn
≤

where the last inequality is due to kxk22 +kzk22 = 1. Therefore,
t2 ≤ δ/2 for any δ ∈ (0, 1) if M ∼ m and m ≤ δn.
By Bernstein’s inequality, this condition can be satisfied with
′
probability exceeding 1−n−c as long as m ≤ cδ 2 n. Theorem
III.3 is proved by combining the above results.
R EFERENCES
[1] E. Candes, J. Romberg, and T. Tao, “Robust uncertainty principles: Exact
signal reconstruction from highly incomplete frequency information,”
IEEE Trans. Inf. Theory, vol. 52, no. 2, pp. 489–509, Feb 2006.
[2] E. Candes and T. Tao, “Near-optimal signal recovery from random
projections: Universal encoding strategies?” IEEE Trans. Inf. Theory,
vol. 52, no. 12, pp. 5406 –5425, Dec. 2006.
[3] D. L. Donoho, “Compressed sensing,” IEEE Trans. Inf. Theory, vol. 52,
no. 4, pp. 1289–1306, Apr. 2006.
[4] Y. C. Eldar and G. Kutyniok, Compressed sensing: theory and applications. Cambridge University Press, 2012.
[5] S. Foucart and H. Rauhut, A mathematical introduction to compressive
sensing. Springer, 2013.
[6] H. Rauhut, “Compressive sensing and structured random matrices,”
Theoretical foundations and numerical methods for sparse recovery,
vol. 9, pp. 1–92, 2010.
[7] P. Zhang, L. Gan, S. Sun, and C. Ling, “Modulated unit-norm tight
frames for compressed sensing,” IEEE Trans. Signal Process., vol. 63,
no. 15, pp. 3974–3985, Aug 2015.
[8] J. Bourgain, “An improved estimate in the restricted isometry problem,”
in Geometric Aspects of Functional Analysis. Springer, 2014, pp. 65–
70.
[9] I. Haviv and O. Regev, “The restricted isometry property of subsampled fourier matrices,” in Geometric Aspects of Functional Analysis.
Springer, 2017, pp. 163–179.
[10] X. Li, “Compressed sensing and matrix completion with constant
proportion of corruptions,” Constructive Approximation, vol. 37, no. 1,
pp. 73–99, 2013.
[11] N. Nguyen and T. Tran, “Exact recoverability from dense corrupted
observations via l1 -minimization,” IEEE Trans. Inf. Theory, vol. 59,
no. 4, pp. 2017–2035, April 2013.
[12] E. J. Candes and Y. Plan, “A probabilistic and RIPless theory of
compressed sensing,” IEEE Trans. Inf. Theory, vol. 57, no. 11, pp. 7235–
7254, 2011.
[13] B. Adcock, A. Bao, A. Narayan et al., “Compressed sensing with
sparse corruptions: Fault-tolerant sparse collocation approximations,”
arXiv preprint arXiv:1703.00135, 2017.
[14] F. Krahmer, S. Mendelson, and H. Rauhut, “Suprema of chaos processes
and the restricted isometry property,” Communications on Pure and
Applied Mathematics, 2014.
[15] J. Haupt, W. U. Bajwa, M. Rabbat, and R. Nowak, “Compressed sensing
for networked data,” IEEE Signal Process. Mag., vol. 25, no. 2, pp. 92–
101, 2008.
[16] C. Franke and M. Gertz, “ORDEN: Outlier region detection and exploration in sensor networks,” in Proceedings of the 2009 ACM SIGMOD
International Conference on Management of data. ACM, 2009, pp.
1075–1078.
[17] Y. Zhang, N. Meratnia, and P. Havinga, “Outlier detection techniques for
wireless sensor networks: A survey,” Commun. Surveys Tuts., vol. 12,
no. 2, pp. 159–170, 2010.
[18] Z. Charbiwala, S. Chakraborty, S. Zahedi, Y. Kim, M. Srivastava,
T. He, and C. Bisdikian, “Compressive oversampling for robust data
transmission in sensor networks,” in INFOCOM, 2010 Proceedings
IEEE, March 2010, pp. 1–9.
[19] Z. Li, F. Wu, and J. Wright, “On the systematic measurement matrix
for compressed sensing in the presence of gross errors,” in Data
Compression Conference (DCC), 2010. IEEE, 2010, pp. 356–365.

12

[20] J. N. Laska, M. Davenport, R. G. Baraniuk et al., “Exact signal recovery
from sparsely corrupted measurements through the pursuit of justice,” in
Signals, Systems and Computers, 2009 Conference Record of the FortyThird Asilomar Conference on. IEEE, 2009, pp. 1556–1560.
[21] C. Studer, P. Kuppinger, G. Pope, and H. Bolcskei, “Recovery of sparsely
corrupted signals,” IEEE Trans. Inf. Theory, vol. 58, no. 5, pp. 3115–
3130, 2012.
[22] B. M. Popovic, “Synthesis of power efficient multitone signals with flat
amplitude spectrum,” IEEE Trans. Commun., vol. 39, no. 7, pp. 1031–
1033, 1991.
[23] J. A. Davis and J. Jedwab, “Peak-to-mean power control in OFDM,
Golay complementary sequences, and Reed-Muller codes,” IEEE Trans.
Inf. Theory, vol. 45, no. 7, pp. 2397–2417, 1999.
[24] B. Levitt, “FH/MFSK performance in multitone jamming,” IEEE J. Sel.
Areas Commun., vol. 3, no. 5, pp. 627–643, 1985.
[25] C. R. Berger, S. Zhou, J. C. Preisig, and P. Willett, “Sparse channel
estimation for multicarrier underwater acoustic communication: From
subspace methods to compressed sensing,” IEEE Trans. Signal Process.,
vol. 58, no. 3, pp. 1708–1721, 2010.
[26] J. Haupt, W. U. Bajwa, G. Raz, and R. Nowak, “Toeplitz compressed
sensing matrices with applications to sparse channel estimation,” IEEE
Trans. Inf. Theory, vol. 56, no. 11, pp. 5862–5875, 2010.
[27] J. Meng, W. Yin, Y. Li, N. T. Nguyen, and Z. Han, “Compressive sensing
based high-resolution channel estimation for OFDM system,” IEEE J.
Sel. Topics Signal Process., vol. 6, no. 1, pp. 15–25, 2012.
[28] K. Li, L. Gan, and C. Ling, “Convolutional compressed sensing using
deterministic sequences,” IEEE Trans. Signal Process., vol. 61, no. 3,
pp. 740–752, 2013.
[29] D. Umehara, H. Nishiyori, and Y. Morihiro, “Performance evaluation
of CMFB transmultiplexer for broadband power line communications
under narrowband interference,” in Power Line Communications and Its
Applications, 2006 IEEE International Symposium on. IEEE, 2006, pp.
50–55.
[30] A. Gomaa and N. Al-Dhahir, “A sparsity-aware approach for NBI
estimation in MIMO-OFDM,” IEEE Trans. Wireless Commun., vol. 10,
no. 6, pp. 1854–1862, 2011.
[31] J. Romberg, “Compressive sensing by random convolution,” SIAM J.
Imaging Sciences, vol. 2, no. 4, pp. 1098–1128, 2009.
[32] G. Puy, P. Vandergheynst, R. Gribonval, and Y. Wiaux, “Universal and
efficient compressed sensing by spread spectrum and application to
realistic Fourier imaging techniques,” EURASIP J. Advances in Signal
Processing, vol. 2012, no. 1, pp. 1–13, 2012.
[33] J. A. Tropp, J. N. Laska, M. F. Duarte, J. K. Romberg, and R. G.
Baraniuk, “Beyond Nyquist: Efficient sampling of sparse bandlimited
signals,” IEEE Trans. Inf. Theory, vol. 56, no. 1, pp. 520–544, 2010.
[34] J. Romberg and R. Neelamani, “Sparse channel separation using random
probes,” Inverse Problems, vol. 26, no. 11, p. 115015, 2010.
[35] J. P. Slavinsky, J. N. Laska, M. A. Davenport, and R. G. Baraniuk,
“The compressive multiplexer for multi-channel compressive sensing,”
in IEEE Int. Conf. Acoustics, Speech and Signal Processing (ICASSP),
2011, pp. 3980–3983.
[36] Y. Rivenson, A. Stern, and B. Javidi, “Single exposure super-resolution
compressive imaging by double phase encoding,” Optics express, vol. 18,
no. 14, pp. 15 094–15 103, 2010.
[37] J. Li, J. S. Li, Y. Y. Pan, and R. Li, “Compressive optical image
encryption,” Scientific reports, vol. 5, 2015.
[38] M. A. Herman and T. Strohmer, “High-resolution radar via compressed
sensing,” IEEE Trans. Signal Process., vol. 57, no. 6, pp. 2275–2284,
2009.
[39] R. F. Marcia, C. Kim, J. Kim, D. J. Brady, and R. M. Willett, “Fast
disambiguation of superimposed images for increased field of view,” in
Image Processing, 2008. ICIP 2008. 15th IEEE International Conference
on. IEEE, 2008, pp. 2620–2623.
[40] D.-S. Pham and S. Venkatesh, “Improved image recovery from compressed data contaminated with impulsive noise,” IEEE Trans. Image
Process., vol. 21, no. 1, pp. 397–405, 2012.
[41] M. Filipović, “Reconstruction of sparse signals from highly corrupted
measurements by nonconvex minimization,” in IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2014.
[42] R. Saab, R. Chartrand, and O. Yilmaz, “Stable sparse approximations via
nonconvex optimization,” in Acoustics, Speech and Signal Processing,
2008. ICASSP 2008. IEEE International Conference on. IEEE, 2008,
pp. 3885–3888.
[43] R. Chartrand and W. Yin, “Iteratively reweighted algorithms for compressive sensing,” in IEEE International Conference on Acoustics,
Speech and Signal Processing (ICASSP). IEEE, 2008, pp. 3869–3872.

[44] R. Foygel and L. Mackey, “Corrupted sensing: Novel guarantees for
separating structured signals,” IEEE Trans. Inf. Theory, vol. 60, no. 2,
pp. 1223–1247, Feb 2014.
[45] Y. Chen, C. Caramanis, and S. Mannor, “Robust sparse regression
under adversarial corruption,” in Proceedings of the 30th International
Conference on Machine Learning (ICML-13), 2013, pp. 774–782.
[46] C. Studer and R. G. Baraniuk, “Stable restoration and separation of
approximately sparse signals,” Applied and Computational Harmonic
Analysis, vol. 37, no. 1, pp. 12–35, 2014.
[47] G. Pope, A. Bracher, and C. Studer, “Probabilistic recovery guarantees
for sparsely corrupted signals,” IEEE Trans. Inf. Theory, vol. 59, no. 5,
pp. 3104–3116, May 2013.
[48] J. Wright, A. Y. Yang, A. Ganesh, S. S. Sastry, and Y. Ma, “Robust face
recognition via sparse representation,” IEEE Trans. Pattern Anal. Mach.
Intell., vol. 31, no. 2, pp. 210–227, 2009.
[49] J. N. Laska, P. T. Boufounos, M. A. Davenport, and R. G. Baraniuk,
“Democracy in action: Quantization, saturation, and compressive sensing,” Applied and Computational Harmonic Analysis, vol. 31, no. 3, pp.
429–443, 2011.
[50] Y. Chi, “Convex relaxations of spectral sparsity for robust superresolution and line spectrum estimation,” in Wavelets and Sparsity XVII,
vol. 10394. International Society for Optics and Photonics, 2017, p.
103941G.
[51] C. Fernandez-Granda, G. Tang, X. Wang, and L. Zheng, “Demixing
sines and spikes: Robust spectral super-resolution in the presence of
outliers,” arXiv preprint arXiv:1609.02247, 2016.
[52] M. Grant and S. Boyd, “CVX: Matlab software for disciplined convex
programming, version 2.1,” http://cvxr.com/cvx, Mar. 2014.
[53] ——, “Graph implementations for nonsmooth convex programs,”
in Recent Advances in Learning and Control, ser. Lecture Notes
in Control and Information Sciences, V. Blondel, S. Boyd, and
H. Kimura, Eds.
Springer-Verlag Limited, 2008, pp. 95–110,
http://stanford.edu/∼ boyd/graph dcp.html.
[54] M. Talagrand, The generic chaining. Springer, 2005, vol. 154.
[55] A. Eftekhari, H. L. Yap, C. J. Rozell, and M. B. Wakin, “The restricted
isometry property for random block diagonal matrices,” arXiv preprint
arXiv:1210.3395, 2012.
[56] M. Rudelson and R. Vershynin, “On sparse reconstruction from Fourier
and Gaussian measurements,” Communications on Pure and Applied
Mathematics, vol. 61, no. 8, pp. 1025–1045, 2008.
[57] N. Alon and J. H. Spencer, The probabilistic method. John Wiley &
Sons, 2004.

