1

Stable Recovery of Structured Signals From
Corrupted Sub-Gaussian Measurements
Jinchi Chen∗ and Yulong Liu∗
∗ School of Physics, Beijing Institute of Technology, Beijing 100081, China

arXiv:1709.05827v1 [cs.IT] 18 Sep 2017

Abstract
This paper studies the problem of accurately recovering a structured signal from a small number of corrupted sub-Gaussian
measurements. We consider three different procedures to reconstruct signal and corruption when different kinds of prior knowledge
are available. In each case, we provide conditions (in terms of the number of measurements) for stable signal recovery from
structured corruption with added unstructured noise. Our results theoretically demonstrate how to choose the regularization
parameters in both partially and fully penalized recovery procedures and shed some light on the relationships among the three
procedures. The key ingredient in our analysis is an extended matrix deviation inequality for isotropic sub-Gaussian matrices,
which implies a tight lower bound for the restricted singular value of the extended sensing matrix. Numerical experiments are
presented to verify our theoretical results.
Index Terms
Corrupted sensing, compressed sensing, signal separation, signal demixing, sub-Gaussian, Gaussian width, Gaussian complexity, Gaussian squared distance, extended matrix deviation inequality.

I. I NTRODUCTION
Corrupted sensing concerns the problem of recovering a structured signal from a relatively small number of corrupted
measurements
y = Φx? + v ? + z,
m×n

?

n

(1)
?

m

where Φ ∈ R
is the sensing matrix, x ∈ R is the structured signal, v ∈ R is the structured corruption, and z ∈ Rm
is the unstructured observation noise. The goal is to estimate x? and v ? from given knowledge of y and Φ.
This problem has received increasing attention recently with many interesting practical applications as well as theoretical
consideration. Examples of applications include face recognition [2], subspace clustering [3], sensor network [4], latent variable
modeling [5], and so on. On the theoretical side, performance guarantees include sparse signal recovery from sparse corruption
[6], [7], [8], [9], [10], [11], [12], [13], low-rank matrix recovery from sparse corruption [5], [14], [15], [16], and structured
signal recovery from structured corruption [17]. It is worth noting that this model (1) also includes the signal separation (or
demixing) problem [18] in which v ? might actually contain useful information and thus be necessary to be recovered. In
particular, if there is no corruption (v ? = 0), this model (1) reduces to the standard compressed sensing problem.
Since this problem is generally ill-posed, tractable recovery is possible when both signal and corruption are suitably structured.
Typical examples of structured signals (or corruptions) include sparse vectors, which exhibit low complexity under the `1 norm,
and low-rank matrices which exhibit low complexity with respect to the nuclear norm (more examples can be found in [19]).
Let f (·) and g(·) be suitable norms which promote structures for signal and corruption respectively. We consider three different
convex optimization approaches to disentangle signal and corruption when different kinds of prior information are available.
Specifically, when prior knowledge of either signal f (x? ) or corruption g(v ? ) is available and the noise level δ (in terms of
the `2 norm) is known, it is natural to consider the following constrained convex recovery procedures
min f (x),

s.t. g(v) ≤ g(v ? ), ky − Φx − vk2 ≤ δ

(2)

min g(v),

s.t. f (x) ≤ f (x? ), ky − Φx − vk2 ≤ δ.

(3)

x,v

and
x,v

When only the noise level δ is known, it is convenient to use the partially penalized convex recovery procedure
min f (x) + λ · g(v),
x,v

s.t.

ky − Φx − vk2 ≤ δ,

(4)

where λ > 0 is a regularization parameter. When there is no prior knowledge available, it is practical to utilize the fully
penalized convex recovery procedure
1
min ky − Φx − vk22 + τ1 · f (x) + τ2 · g(v),
(5)
x,v 2
where τ1 , τ2 > 0 are some regularization parameters.
The material in this paper was presented in part at the IEEE International Symposium on Information Theory, Aachen, Germany, June 2017 [1].

2

A. Contribution
This paper considers the problem of recovering structured signals from corrupted sub-Gaussian measurements. More precisely,
we consider the following observation model:
• Sub-Gaussian measurements: we assume that each row Φi of the sensing matrix Φ is independent, centered, and subGaussian random vector with
√
kΦi kψ2 ≤ K/ m and E ΦTi Φi = In /m,
(6)
•

where k · kψ2 denotes the sub-Gaussian norm (defined in (9)) and In is the n-dimensional identity matrix;
Bounded or sub-Gaussian noise: the unstructured noise z is assumed to be bounded (kzk2 ≤ δ) or be a random vector
with independent centered sub-Gaussian entries satisfying
kzi kψ2 ≤ L and E zi2 = 1.

(7)

Under the above model assumptions, the contribution of this paper is twofold:
• First, we establish an extended matrix deviation inequality for isotropic sub-Gaussian matrices, which provides a powerful
tool for analyzing the corrupted sensing problem;
• Second, based on the deviation inequality, we present performance guarantees for all three convex recovery procedures.
These results theoretically demonstrate how to select the regularization parameters in both partially and fully penalized
recovery procedures and shed some light on the relationships among the three approaches.
B. Related Work
Within the past few years, there have been numerous studies to understand the theoretical aspect of the corrupted sensing
problem. These works might be roughly put into the following three groups by the type of structures considered.
1) Sparse Signal Recovery from Sparse Corruption: The specific problem of recovering a sparse vector from sparsely
corrupted measurements has been analyzed under a variety of different model assumptions. For instance, Wright and Ma [6]
study exact recovery by the partially penalized recovery procedure (with f (·) = g(·) = k · k1 , λ = 1, and δ = 0) under a
bouquet model: y = Φx? +v ? , where the columns of Φ are independent
identically distributed (i.i.d.) samples from a Gaussian
√
distribution N (µ, ν 2 Im /m) with kµk2 = 1 and kµk∞ ≤ C/ m, and v ? has uniformly random signs. Li [7] considers stable
?
?
?
?
recovery
pof (x , v ) from y = Φx + v + z by the partially penalized recovery procedure (with f (·) = g(·) = k · k1 and
λ = 1/ log(n/m) + 1), where Φ is a Gaussian matrix with i.i.d. entries and z is a bounded noise vector. In the absence of
noise, [7] also considers a class of sensing matrices, in which the rows of Φ are sampled independently from a population
obeying E ΦTi Φi = In and kΦi k∞ ≤ c. In contrast to [7], Nguyen and Tran [8] also establish stable or exact recovery of
(x? , v ? ) from y = Φx? +v ? +z by the partially penalized recovery procedure, but with a different model assumption in which
Φ has columns sampled uniformly from an orthonormal matrix, x? has uniformly random signs, v ? has uniformly distributed
support, and z is a bounded noise vector. In a subsequent paper [9], Nguyen and Tran study stable recovery of (x? , v ? ) from
y = Φx? + v ? + z by the fully penalized recovery procedure (with f (·) = g(·) = k · k1 ), where Φ is an Guassian sensing
matrix with i.i.d. entries and z is a Gaussian noise vector. Pope et al. [12] investigate the exact recovery from the observation
model y = Φx? + Ψv ? , where Φ and Ψ are deterministic matrices. The authors require uniform randomness in the support
set of x? or v ? and rely on certain incoherence properties of Φ and Ψ. These probabilistic recovery guarantees improve or
refine the previous results in [10], [11], [13].
2) Low-rank Matrix Recovery from Sparse Corruption: Another line of work considers the problem of recovering a low-rank
matrix from sparse corruption. Chandrasekaran et al. [5] study the exact decomposition of a given matrix into its sparse and
low-rank components by the partially penalized
P recovery procedure (with f (·) = k · k∗ , g(·) = k · k1 and δ = 0), where kDk∗
denotes the nuclear norm of D and kDk1 = i,j |Di,j | . The work of Candès et al. [14] uses this model for robust principal
component analysis and image processing applications. Modifications to the rank-sparsity model also find applications in robust
statistics, see e.g., [15], [16].
3) Structured Signal Recovery from Structured Corruption: The most closely related to our current paper are the results by
[18], [17], [20], [21], in which the problem of recovering a structured signal from structured corruption is considered. In [18],
McCoy and Tropp analyze the constrained recovery procedures ((2) and (3)) in the setting where Φ is a random orthogonal
matrix (m = n) and measurements are noiseless (δ = 0). In the same setting, the work of Amelunxen et al. [20] establishes
the sharpness of their recovery results, by specifying an appropriate threshold under which the constrained procedures fail
with high probability. Foygel and Mackey [17] study both the constrained recovery procedures ((2) and (3)) and the partially
penalized recovery procedure (4) in the setting where Φ is a Gaussian matrix (m ≤ n or m > n) with i.i.d. entries and
the noise is bounded. A recent work of Zhang et al. [21] establishes the phase transition theory of the constrained recovery
procedures under the setting of [17]. In the present paper, we establish performance guarantees for all three convex recovery
procedures in the setting where Φ is a sub-Gaussian matrix and the noise is bounded or sub-Gaussian. These results solve
a series of open problems in [17], for example, allowing non-Gaussian sensing matrix and stochastic unstructured noise in
observation model (1) and analyzing the fully penalized convex recovery procedure (5) for arbitrary structured signals and
structured corruptions.

3

2

Normal
Cone

Tangent
Cone
1

-2

-1

1

2

-1

-2

Fig. 1. Illustrations of the subdifferential, scaled subdifferential, normal cone, and tangent cone for f (x) = kxk1 at the point x = (1, 0). (For clarity, cones
are shifted to the original point.)

C. Organization
The remainder of the paper is organized as follows. We begin by reviewing some preliminaries that are necessary for our
subsequent analysis in Section II. In Section III, we establish a mathematical tool which is critical for analyzing the corrupted
sensing problem. Section IV is devoting to presenting the main theoretical results of the paper. We then present results from
numerical simulations in Section V. We conclude the paper in Section VI.
II. P RELIMINARIES
In this section, we review some useful concepts from convex geometry and high-dimensional probability that underlie our
analysis. Throughout the paper, Sn−1 and Bn2 denote the unit sphere and ball in Rn under the `2 norm respectively, while
Bnf := {u ∈ Rn : f (u) ≤ 1} is the unit ball in Rn under the norm defined by f . The compatibility constant between f and
the `2 norm is defined as αf := supu6=0 f (u)/kuk2 . We use the notation C, C 0 , c, c0 , etc., to refer to positive constants, whose
value may change from line to line.
A. Convex Geometry
1) Subdifferential: The subdifferential of f at x is the set of vectors
∂f (x) = {u ∈ Rn : f (x + d) ≥ f (x) + hu, di for all d ∈ Rn }.
For any number κ ≥ 0, we denote the scaled (by κ) subdifferential as κ · ∂f (x) = {κu : u ∈ ∂f (x)}.
2) Tangent Cone and Normal Cone: A cone is a set that is closed under multiplication by positive scalars. The tangent
cone of f at x is defined as the set of descent directions of f at x
Tf = {u ∈ Rn : f (x + t · u) ≤ f (x) for some t > 0}.
The normal cone of f at x is the polar of the tangent cone, given by
Nf = {u ∈ Rn : hu, di ≤ 0 for all d ∈ Tf },
which may be written as the cone hull of the subdifferential (if 0 ∈
/ ∂f (x)) [22, Theorem 1.3.5]
Nf = cone{∂f (x)} = {u ∈ Rn : u ∈ t · ∂f (x) for some t > 0}.
Fig. 1 illustrates related concepts in R2 for the `1 norm.

4

3) Gaussian Complexity, Gaussian Width, and Gaussian Distance: For any T ⊆ Rn , a simple way to quantify the “size”
of T is through the Gaussian complexity
γ(T ) := E sup |hg, xi|, where g ∼ N (0, In ).
x∈T

Another popular geometric quantity closely related to Gaussian complexity is the Gaussian width
ω(T ) := E sup hg, xi, where g ∼ N (0, In ).
x∈T
1

In particular [23],
(ω(T ) + kyk2 ) /3 ≤ γ(T ) ≤ 2ω(T ) + kyk2 for every y ∈ T .

(8)

The Gaussian squared distance η 2 (T ) of a subset T ⊂ Rn is defined as
η 2 (T ) := E inf kg − uk22 , where g ∼ N (0, In ).
u∈T

B. High-Dimensional Probability
1) Sub-Gaussian and Sub-exponential Random Variables: A random variable X is sub-Gaussian if its distribution is
dominated by a Gaussian distribution. Formally, X is called a sub-Gaussian random variable if the Orlicz norm
kXkψ2 = inf{K > 0 : E ψ2 (|X|/K) ≤ 1}

(9)

is finite for the Orlicz function ψ2 (x) = exp(x2 ) − 1. The sub-Gaussian norm of X, denoted kXkψ2 , is defined to be the
smallest K in (9). There are several equivalent definitions used in the literature. In particular, X is sub-Gaussian if there exist
absolute constants C > 1 and K such that

1/p
√
E |X|p
≤ K p, for all p ≥ 1
(10)
or


P |X| ≥ t ≤ C exp −t2 /K 2 ,

for all t ≥ 0.

(11)

Thus we can redefine the sub-Gaussian norm of X as the smallest K such that (10) or (11) holds. One can show that kXkψ2
defined this way is within an absolute constant factor from that defined in (9), see [24, Section 5.2.3]. Classical examples of
sub-Gaussian random variables include Gaussian, Bernoulli, and all bounded random variables. Similarly, a random variable X
is sub-exponential if its distribution is dominated by an exponential distribution. More precisely, X is called a sub-exponential
random variable if the Orlicz norm
kXkψ1 = inf{K > 0 : E ψ1 (|X|/K) ≤ 1}
(12)
is finite for the Orlicz function ψ1 (x) = exp(x) − 1. The sub-exponential norm of X, denoted kXkψ1 , is defined to be the
smallest K in (12).
2) Sub-Gaussian and Sub-exponential Random Vectors: A random vector x in Rn is sub-Gaussian (or sub-exponential) if
all of its one-dimensional marginals are sub-Gaussian (or sub-exponential) random variables and its ψ2 -norm (or ψ1 -norm) is
defined as
hx, yi ψ2 or kxkψ1 := sup
hx, yi ψ1 .
kxkψ2 := sup
(13)
y∈Sn−1

A random vector x in Rn is called isotropic if

y∈Sn−1

E(xxT ) = In .

For basic properties of sub-Gaussian and sub-exponential random variables (vectors), see e.g., [24], [25, Chapter 2]. Some
properties which will be used in our proofs are included in Appendix A.
1 Here

we use a slightly sharper upper bound than that in [23]. Indeed, since T −T is original symmetric, then 2ω(T ) = γ(T −T ) = E supx,y∈T |hg, x−
1

yi| ≥ E supx∈T |hg, x − yi| ≥ E supx∈T [|hg, xi| − |hg, yi|] ≥ γ(T ) − (E |hg, yi|2 ) 2 = γ(T ) − kyk2 , ∀ y ∈ T . Rearranging yields the desired
result.

5

3) Talagrand’s Majorizing Measure Theorem: The key ingredient in the proofs of our mathematical tools is the Talagrand’s
Majorizing Measure Theorem which states that any sub-Gaussian process is dominated by a Gaussian process with the same
(or larger) increments.
Fact 1 (Talagrand’s Majorizing Measure Theorem). Let (Xu )u∈T be a random process indexed by points in a bounded set
T ⊂ Rn . Assume that the process has sub-Gaussian increments, that is, there exists M ≥ 0 such that
kXu − Xv kψ2 ≤ M ku − vk2

for every u, v ∈ T .

Then
E sup Xu − Xv ≤ CM ω(T ).

(14)

u,v∈T

Moreover, for any t ≥ 0, the event


sup Xu − Xv ≤ CM ω(T ) + t · diam(T )

(15)

u,v∈T

holds with probability at least 1 − exp(−t2 ), where diam(T ) := supx,y∈T kx − yk2 denotes the diameter of T .
Remark 1. The expectation bound (14) of this theorem can be found e.g. in [26, Theorem 2.1.1, 2.1.5]. The high probability
bound (15) can be found e.g. in [27, Theorem 3.2] or [23, Theorem 4.1].
III. E XTENDED M ATRIX D EVIATION I NEQUALITY
In this section, we establish a mathematical tool which provides a unified framework for analyzing all three recovery
procedures. Note that if we denote Υ = [Φ, Im ] and s? = [(x? )T , (v ? )T ]T , then the observation model (1) can be reformulated
as y = Υs? + z, which is the same as the standard compressed sensing model. It is now well known that the restricted singular
value of the sensing matrix Υ (see, e.g., [28], [19]) plays a key role in analyzing the compressed sensing problem. With this
observation in mind, we establish an extended matrix deviation inequality which implies a tight lower bound for the restricted
singular value of the extended sensing matrix [Φ, Im ]. This √result states that√ for p
any isotropic sub-Gaussian matrix A and
any bounded subset T ⊆ Rn × Rm , the deviation of kAa + mbk2 around m · kak22 + kbk22 over vectors (a, b) ∈ T is
uniformly bounded by the Gaussian complexity of T .
Theorem 1 (Extended Matrix Deviation Inequality). Let A be an m × n matrix whose rows Ai are independent centered
isotropic sub-Gaussian vectors with K = maxi kAi kψ2 , and T be a bounded subset of Rn × Rm . Then
q
√
√
E sup kAa + mbk2 − m · kak22 + kbk22 ≤ CK 2 · γ(T ).
(a,b)∈T

For any t ≥ 0, the event
sup

kAa +

√

mbk2 −

√

m·

(a,b)∈T

q
kak22 + kbk22 ≤ CK 2 [γ(T ) + t · rad(T )]

holds with probability at least 1 − exp(−t2 ), where rad(T ) := supx∈T kxk2 denotes the radius of T .
Proof. See Appendix B.
Remark 2 (Anisotropic case). By using a simple linear transform, Theorem 1 can be extended to the anisotropic case in which
each row of A satisfies E ATi Ai = Σ for some invertible covariance matrix Σ. To see this, consider the whitened version
B = AΣ−1/2 . Note that
D
E
kBi kψ2 = sup
BiT , y ψ2 = sup
ATi , Σ−1/2 y
ψ2
y∈Sn−1
y∈Sn−1
D
E
−1/2
T
−1/2
−1/2
= sup kΣ
yk2 · Ai , Σ
y/kΣ
yk2
ψ2

y∈Sn−1

≤ kΣ

−1/2

k · K.

Define the block diagonal matrix Σ̃ = diag{Σ1/2 , Im }, then we have
q
q
√
√
√
√
E sup kAa + mbk2 − m · kΣ1/2 ak22 + kbk22 = E sup kBΣ1/2 a + mbk2 − m · kΣ1/2 ak22 + kbk22
(a,b)∈T

(a,b)∈T

=E

sup

kBa +

√

mbk2 −

√

m·

(a,b)∈Σ̃T

≤ CkΣ−1 kK 2 γ(Σ̃T )
≤ CkΣ−1 k max{kΣk1/2 , 1}K 2 γ(T ).

q

kak22 + kbk22

6

The first inequality follows from Theorem 1. The last inequality holds because γ(Σ̃T ) ≤ kΣ̃kγ(T ) = max{kΣk1/2 , 1}γ(T ).
Similarly, we can obtain the anisotropic version for the second part of Theorem 1.
Remark 3. Very recently, Liaw et al. [23] have shown that if A is an isotropic (or anisotropic) sub-Gaussian matrix, then
√
E sup kAak2 − mkak2 ≤ CK 2 γ(T )
a∈T

and the event
sup kAak2 −

√

mkak2 ≤ CK 2 [γ(T ) + t rad(T )]

(16)

a∈T

holds with probability at least 1 − exp(−t2 ). It is not hard to see that these results can not be directly applied to the corrupted
sensing problem, because the covariance matrix of each row of [Φ, Im ] is singular. However, [Φ, Im ] still has independent
sub-Gaussian rows. This fact allows us to generalize the analysis in [23] to the extended case. It is worth noting that there are
several earlier variants of (16) proved in [29], [30], [27]. See [23] for their comparisons.
When T is a subset of the unit sphere, we have the following corollary.
Corollary 1. Under the assumptions of Theorem 1, for any t ≥ 0, the event
√
√
sup
kAa + mbk2 − m ≤ CK 2 [γ(T ∩ Sn+m−1 ) + t]

(17)

(a,b)∈T ∩Sn+m−1

holds with probability at least 1 − exp(−t2 ).
√
Corollary 1 may be specialized to bound to the restricted singular value of [A, mIm ]. Indeed, let T ⊂ Sn+m−1 . Then the
corollary states that, with high probability (e.g., 1 − exp{−γ 2 (T ∩ Sn+m−1 )}),
√
√
kAa + mbk2 ≥ m − CK 2 γ(T ∩ Sn+m−1 )
inf
(18)
(a,b)∈T ∩Sn+m−1

and
sup
(a,b)∈T ∩Sn+m−1

kAa +

√

mbk2 ≤

√

m + CK 2 γ(T ∩ Sn+m−1 )

(19)

for all (a, b) ∈ T . As we will see in the next section, (18) plays a key role in analyzing the corrupted sensing problem.
IV. R ECOVERY F ROM C ORRUPTED S UB -G AUSSIAN M EASUREMENTS
In this section, we present our theoretical results on the recovery of structured signals from corrupted sub-Gaussian
measurements via three different convex recovery procedures.
A. Recovery via Constrained Optimization
We start with analyzing the constrained convex recovery procedures (2) and (3). Our first result shows that, with high
probability, approximately


CK 4 ω 2 (Tf (x? ) ∩ Sn−1 ) + ω 2 (Tg (v ? ) ∩ Sm−1 )
(20)
corrupted measurements suffice to recover (x? , v ? ) exactly in the absence of noise and stably in the presence of noise, via
either of the procedures (2) or (3).
Before stating our result, we need to define the error set
E1 (x? , v ? ) := {(a, b) ∈ Rn × Rm : f (x? + a) ≤ f (x? ) and g(v ? + b) ≤ g(v ? )},
in which the error vector (x̂ − x? , v̂ − v ? ) lives. By the convexity of f and g, E1 (x? , v ? ) belongs to the following convex
cone
C1 (x? , v ? ) := {(a, b) ∈ Rn × Rm : ha, ui ≤ 0 and hb, si ≤ 0 for any u ∈ ∂f (x? ) and s ∈ ∂g(v ? )},
which is equivalent to
{(a, b) ∈ Rn × Rm : a ∈ Tf (x? ) and b ∈ Tg (v ? )}.
Fig. 2 illustrates the error set E1 , error cone C1 , and corresponding spherical part of C1 . As we will see in this section, the
Gaussian complexity of the spherical part of the error cone is closely related to the number of measurements to guarantee
successful recovery.
Then we have the following result.

7

error set

error cone

Fig. 2. Illustrations of the error set E1 , error cone C1 , and corresponding spherical part of C1 : C1 ∩ Sn+m−1 (denoted by the red arc).

Theorem 2 (Constrained Recovery). Let (x̂, v̂) be the solution to either of the constrained optimization problems (2) or (3).
If the number of measurements
√
m ≥ CK 2 γ(C1 (x? , v ? ) ∩ Sn+m−1 ) + ,
(21)
then

√
q
2δ m
2
2
?
?
kx̂ − x k2 + kv̂ − v k2 ≤

2
n+m−1
with probability at least 1 − exp{−γ (C1 ∩ S
)}.
√
√
Remark 4. If we consider the observation model y = Ax? + mv ? + z as that in [9], then the factor m can be removed
from the error bound. This change of the model seems to make our result more interpretable, but we analyze the original
observation model (1) here.
Proof. Since (x̂, v̂) solves (2) or (3), we have f (x̂) ≤ f (x? ) and g(v̂) ≤ g(v ? ). This implies (x̂ − x? , v̂ − v ? ) ∈ E1 (x? , v ? ) ⊂
C1 (x? , v ? ). It then follows from (18) and (21) that the event
√
√
min
mkΦa + bk2 ≥ m − CK 2 γ(C1 (x? , v ? ) ∩ Sn+m−1 ) ≥ 
(22)
(a,b)∈C1 (x? ,v ? )∩Sn+m−1

holds with probability at least 1 − exp{−γ 2 (C1 (x? , v ? ) ∩ Sn+m−1 )}.
On the other hand, since both (x̂, v̂) and (x? , v ? ) are feasible, by the triangle inequality, we have
kΦ(x̂ − x? ) + (v̂ − v ? )k2 ≤ ky − Φx̂ − v̂k2 + ky − Φx? − v ? k2 ≤ 2δ.

(23)

Combining (22) and (23) yields
2δ ≥ kΦ(x̂ − x? ) + (v̂ − v ? )k2
q
(v̂ − v ? )
Φ(x̂ − x? )
p
= kx̂ − x? k22 + kv̂ − v ? k22 · p
+
kx̂ − x? k22 + kv̂ − v ? k22
kx̂ − x? k22 + kv̂ − v ? k22
q

≥ kx̂ − x? k22 + kv̂ − v ? k22 · √ .
m

2

Rearranging completes the proof.
To make use of Theorem 2, it suffices to bound γ(C1 (x? , v ? ) ∩ Sn+m−1 ). Since a number of upper bounds on Gaussian
width and Gaussian squared distance for different structured settings are available in the literature (see, e.g., [19], [20], [17],

8

[31]), it is highly desirable to bound γ(C1 (x? , v ? )∩Sn+m−1 ) in terms of these familiar parameters. Then we have the following
result.
Lemma 1. The Gaussian complexity of C1 (x? , v ? ) ∩ Sn+m−1 satisfies




γ(C1 (x? , v ? ) ∩ Sn+m−1 ) ≤ 2 ω Tf (x? ) ∩ Sn−1 + ω Tg (x? ) ∩ Sm−1 + 1 .
Proof. Let g ∼ N (0, In ) and h ∼ N (0, Im ), it follows from the definition of Gaussian complexity that
γ(C1 (x? , v ? ) ∩ Sn+m−1 ) = E
=E

hg, ai + hh, bi

sup
(a,b)∈C1 (x? ,v ? )∩Sn+m−1

sup

hg, ai · c + hh, bi ·

p

1 − c2

c∈(0,1)
a∈Tf (x? )∩Sn−1
b∈Tg (v ? )∩Sm−1

≤E

sup

c · |hg, ai| +

p

1 − c2 |hh, bi|

c∈(0,1)
a∈Tf (x? )∩Sn−1
b∈Tg (v ? )∩Sm−1

≤E

sup
a∈Tf (x? )∩Sn−1

|hg, ai| + E

sup

|hh, bi|

b∈Tg (v ? )∩Sm−1

= γ(Tf (x? ) ∩ Sn−1 ) + γ(Tg (v ? ) ∩ Sm−1 )




≤ 2 ω Tf ∩ Sn−1 + ω Tg ∩ Sm−1 + 1 .
The last inequality is due to (8).
Thus, (20) follows from Theorem 2 and Lemma 1.
Remark 5. When Φ is a random orthogonal matrix (m = n) and measurements are noiseless (δ = 0), Amelunxen et al.
[20] show that if m ≥ ι(Tf (x? )) + ι(Tg (v ? )), then the constrained procedures (2) and (3) succeed with high probability,

2
where the statistical dimension ι(T ) of a closed convex cone T ∈ Rn is defined as ι(T ) = E supu∈T ∩Bn2 hu, gi with
g ∼ N (0, In ). They also establish the sharpness of their result. Our result (20) essentially coincides with this result because
the statistical dimension of a closed convex cone T ∈ Rn is closely related to its Gaussian width [20, Proposition 10.2]:
ω 2 (T ∩ Sn−1 ) ≤ ι(T ) ≤ ω 2 (T ∩ Sn−1 ) + 1.
Remark 6. When Φ is a Gaussian matrix (m > n or m ≤ n), Foygel and Mackey [17] establish similar result as (20) in terms
of Gaussian squared complexity2 under bounded noise (kzk2 ≤ δ). They also numerically show that their result is sharp. In
the absence of noise, Zhang et al. [21] recently establish that the phase transition of the constrained procedure under Gaussian
measurements occurs around ω 2 (Tf (x? ) ∩ Sn−1 ) + ω 2 (Tg (v ? ) ∩ Sm−1 ).
B. Recovery via Partially Penalized Optimization
We next present performance analysis for the partially penalized optimization problem (4). Our second result shows that,
with high probability, approximately


CK 4 η 2 (λ1 · ∂f (x? )) + η 2 (λ2 · ∂g(v ? ))
(24)
corrupted measurements suffice to recover (x? , v ? ) exactly in the absence of noise and stably in the presence of noise, via the
procedure (4). Here, λ1 and λ2 are absolute constants such that the regularization parameter λ = λ2 /λ1 .
In this case, it is natural to define the following error set
E2 (x? , v ? ) := {(a, b) ∈ Rn × Rm : f (x? + a) + λ · g(v ? + b) ≤ f (x? ) + λ · g(v ? )}.
By the convexity of f and g, E2 (x? , v ? ) belongs to the following convex cone
C2 (x? , v ? ) := {(a, b) ∈ Rn × Rm : ha, ui + λhb, si ≤ 0 for any u ∈ ∂f (x? ) and s ∈ ∂g(v ? )}.
Then we have the following result.
Theorem 3 (Partially Penalized Recovery). Let (x̂, v̂) be the solution to the partially penalized optimization problem (4). If
the number of measurements
√
m ≥ CK 2 γ(C2 (x? , v ? ) ∩ Sn+m−1 ) + ,
(25)
2
Gaussian squared complexity of a set T ∈ Rn is defined as ζ 2 (T ) = E supu∈T hu, gi + , where g ∼ N (0, In ) and (a)+ = max{a, 0}. Note
2
?
n−1
that the Gaussian squared complexity ζ (Tf (x ) ∩ S
) is very slightly bigger than the squared Gaussian width ω 2 (Tf (x? ) ∩ Sn−1 ).
2 The

9

then

√
q
2δ m
kx̂ − x? k22 + kv̂ − v ? k22 ≤

with probability at least 1 − exp{−γ 2 (C2 ∩ Sn+m−1 )}.
Proof. The proof is similar to that of Theorem 2. Since (x̂, v̂) solves (4), we have (x̂−x? , v̂ −v ? ) ∈ E2 (x? , v ? ) ⊂ C2 (x? , v ? ).
It then follows from (18) and (25) that the event
√
√
min
mkΦa + bk2 ≥ m − CK 2 γ(C2 (x? , v ? ) ∩ Sn+m−1 ) ≥ 
(26)
(a,b)∈C2 (x? ,v ? )∩Sn+m−1

holds with probability at least 1 − exp{−γ 2 (C2 (x? , v ? ) ∩ Sn+m−1 )}.
On the other hand, since both (x̂, v̂) and (x? , v ? ) are feasible, by the triangle inequality, we have
kΦ(x̂ − x? ) + (v̂ − v ? )k2 ≤ ky − Φx̂ − v̂k2 + ky − Φx? − v ? k2 ≤ 2δ.

(27)

Combining (26) and (27) completes the proof.
To bound γ(C2 (x? , v ? ) ∩ Sn+m−1 ) in terms of familiar parameters, we have the following result.
Lemma 2. The Gaussian complexity of C2 (x? , v ? ) ∩ Sn+m−1 satisfies
p
γ(C2 (x? , v ? ) ∩ Sn+m−1 ) ≤ 2 η 2 (λ1 · ∂f (x? )) + η 2 (λ2 · ∂g(v ? )) + 1.
Proof. By the definition of C2 (x? , v ? ), for any point (a, b) ∈ C2 (x? , v ? ), we have
ha, ui + λhb, si ≤ 0
for any u ∈ ∂f (x? ) and s ∈ ∂g(v ? ). Multiplying both sides by λ1 yields
ha, λ1 ui + hb, λ2 si ≤ 0.
For any fixed g ∈ Rn and h ∈ Rm , it follows from the Cauchy-Schwarz inequality that
ha, gi + hb, hi ≤ ha, g − λ1 ui + hb, h − λ2 si
≤ kak2 kg − λ1 uk2 + kbk2 kh − λ2 sk2 .
Choosing suitable ū ∈ ∂f (x? ) and s̄ ∈ ∂g(v ? ) such that
kg − λ1 · ūk2 = dist(g, λ1 · ∂f (x? )) := df
and
kh − λ2 · s̄k2 = dist(h, λ2 · ∂g(v ? )) := dg ,
we obtain
ha, gi + hb, hi ≤ kak2 · dist(g, λ1 · ∂f (x? )) + kbk2 · dist(h, λ2 · ∂g(v ? ))

(28)

= df · kak2 + dg · kbk2 .
Then, by the definition of Gaussian width,

ω C2 (x? , v ? ) ∩ Sn+m−1 = E

sup



hg, ai + hh, bi





kak2 · df + kbk2 · dg

(a,b)∈C2 (x? ,v ? )∩Sn+m−1

≤E

sup
(a,b)∈C2

≤E



(x? ,v ? )∩Sn+m−1

q
q
p
d2f + d2g ≤ E d2f + E d2g = η 2 (λ1 · ∂f (x? )) + η 2 (λ2 · ∂g(v ? )),

where g ∼ N (0, In ) and h ∼ N (0, Im ). The second and the third inequalities follow from the Cauchy-Schwarz and Jensen’s
inequalities, respectively. By (8), we complete the proof.
Thus, combining Theorem 3 and Lemma 2 yields (24).

10

1) How to Choose the Regularization Parameter λ?: The result (24) also suggests a simple strategy to choose λ1 and λ2 ,
and hence the regularization parameter λ = λ2 /λ1 . Observe that the number of observations to guarantee successful recovery
by (4) depends on λ1 and λ2 through η 2 (λ1 · ∂f (x? )) and η 2 (λ2 · ∂g(v ? )) respectively. In order to achieve the possibly
smallest number of observations, it is natural to choose λ1 and λ2 which make the two Gaussian squared distances as small
as possible. Thus we can pick
λ?1 = arg min η 2 (λ1 · ∂f (x? )), λ?2 = arg min η 2 (λ2 · ∂g(v ? )), and λ? = λ?2 /λ?1 .
λ1 >0

λ2 >0

(29)

Furthermore, it has been shown in [20, Proposition 4.1] that if the subdifferential ∂f (x? ) (or ∂g(v ? )) is nonempty, compact,
and does not contain the original, then the function J(κ) = η 2 (κ · ∂f (x? )) (or η 2 (κ · ∂g(v ? ))) is strictly convex for κ > 0,
so it achieves its minimum at a unique point. Thus, under mild conditions, the optimal regularization parameter λ? is always
unique.
Remark 7. In the setting of Gaussian measurements, Foygel and Mackey [17] establish similar result as (24) in terms of
Gaussian squared distance under bounded noise (kzk2 ≤ δ). Their result also indicates the same way to choose the regularization
parameter λ. However, in the sub-Gaussian case, our proof is totally different from theirs. Because many useful properties of
Gaussian distribution (e.g., the rotation invariance property, Gordon’s comparison lemma [32]) which are heavily used in [17]
do not hold in the sub-Gaussian case.
C. Recovery via Fully Penalized Optimization
Finally, we analyze the fully penalized optimization problem (5). In this case, due to the presence of noise, we require
regularization parameters τ1 and τ2 to satisfy the following condition.
Condition 1. For any β > 1,
τ1 ≥ βf ∗ (ΦT z) and

τ2 ≥ βg ∗ (z).

This condition is a natural extension to that in [33, Lemma 1], where only the regularization parameter for signal (τ1 ) is
considered and β = 2. Then our third result shows that, with high probability, approximately


(τ1 αf )2 + (τ2 αg )2
(30)
CK 4 η 2 (τ1 · ∂f (x? )) + η 2 (τ2 · ∂g(v ? )) +
β2
corrupted measurements suffice to recover (x? , v ? ) exactly in the absence of noise and stably in the presence of noise, via the
procedure (5).
Under the above condition, we similarly define the error set
E3 (x? , v ? ) := {(a, b) ∈ Rn × Rm : τ1 f (x? + a) + τ2 g(v ? + b) ≤ τ1 f (x? ) + τ2 g(v ? ) +

1
[τ1 f (a) + τ2 g(b)]}.
β

Note that if 0 < β ≤ 1, it then follows from the triangle inequality that the inequality defining E3 (x? , v ? ) holds for all (a, b).
Thus we require β > 1, which will restrict the set of E3 (x? , v ? ) and yield the restricted error set. By the convexity of f and
g, E3 (x? , v ? ) belongs to the following convex cone
C3 (x? , v ? ) := {(a, b) ∈ Rn × Rm : τ1 ha, ui + τ2 hb, si ≤

1
[τ1 f (a) + τ2 g(b)] for any u ∈ ∂f (x? ) and s ∈ ∂g(v ? )}.
β

Then we have the following result.
Theorem 4 (Fully Penalized Recovery). Let (x̂, v̂) be the solution to the fully penalized optimization problem (5) with τ1 and
τ2 satisfying Condition 1. If the number of measurements
√
m ≥ CK 2 γ(C3 (x? , v ? ) ∩ Sn+m−1 ) + ,
(31)
then
q

kx̂ − x? k22 + kv̂ − v ? k22 ≤ 2m ·

β + 1 (τ1 αf + τ2 αg )
·
β
2

(32)

with probability at least 1 − exp{−γ 2 (C3 ∩ Sn+m−1 )}.
Proof. Since (x̂, v̂) solves (5), we have
1
1
ky − Φx̂ − v̂k22 + τ1 f (x̂) + τ2 g(v̂) ≤ ky − Φx? − v ? k22 + τ1 f (x? ) + τ2 g(v ? ).
2
2
Observe that
1
1
1
ky − Φx̂ − v̂k22 = kΦ(x̂ − x? ) + (v̂ − v ? )k22 + kzk22 − hΦ(x̂ − x? ), zi − hv̂ − v ? , zi .
2
2
2

(33)

11

Substituting this into (33) yields
1
kΦ(x̂ − x? ) + (v̂ − v ? )k22 ≤ τ1 [f (x? ) − f (x̂)] + τ2 [g(v ? ) − g(v̂)] + hΦ(x̂ − x? ), zi + hv̂ − v ? , zi .
2
On the one hand, since kΦ(x̂ − x? ) + (v̂ − v ? )k22 ≥ 0, we have

(34)

τ1 f (x̂) + τ2 g(v̂) ≤ τ1 f (x? ) + τ2 g(v ? ) + hΦ(x̂ − x? ), zi + hv̂ − v ? , zi
≤ τ1 f (x? ) + τ2 g(v ? ) + f ∗ (ΦT z) · f (x̂ − x? ) + g ∗ (z) · g(v̂ − v ? )
τ2
τ1
· f (x̂ − x? ) +
· g(v̂ − v ? ),
≤ τ1 f (x? ) + τ2 g(v ? ) +
β
β
where f ∗ (·) and g ∗ (·) denote the dual norm3 of f (·) and g(·) respectively. The second inequality follows from generalized
Hölder’s inequality. The last inequality is due to Condition 1. This implies (x̂ − x? , v̂ − v ? ) ∈ E3 (x? , v ? ) ⊂ C3 (x? , v ? ). It
then follows from (18) and (31) that the event
√
√
min
mkΦa + bk2 ≥ m − CK 2 γ(C3 (x? , v ? ) ∩ Sn+m−1 ) ≥ 
(35)
?
?
n+m−1
(a,b)∈C3 (x ,v )∩S

holds with probability at least 1 − exp{−γ 2 (C3 (x? , v ? ) ∩ Sn+m−1 )}.
On the other hand, it follows from (34) that
τ1
τ2
1
kΦ(x̂ − x? ) + (v̂ − v ? )k22 ≤ τ1 · f (x̂ − x? ) + τ2 · g(v̂ − v ? ) +
· f (x̂ − x? ) +
· g(v̂ − v ? )
2
β
β

β+1
=
τ1 · f (x̂ − x? ) + τ2 · g(v̂ − v ? )
β

β+1
=
αf τ1 · kx̂ − x? k2 + αg τ2 · kv̂ − v ? k2
β
q
q
β+1
≤
· (τ1 αf )2 + (τ2 αg )2 · kx̂ − x? k22 + kv̂ − v ? k22
β
q
β+1
≤
· (τ1 αf + τ2 αg ) · kx̂ − x? k22 + kv̂ − v ? k22 ,
β

(36)

where αf and αg are compatibility constants. The first inequality √
follows from the triangle inequality. In the last two inequalities,
we have used the Cauchy-Schwarz inequality and the fact that a2 + b2 ≤ a + b for a, b ≥ 0, respectively.
Combining (35) and (36) yields
2(β + 1)
· (τ1 αf + τ2 αg ) ≥
β

q

kx̂ −

x? k22

+ kv̂ −

v ? k22

· p

Φ(x̂ − x? )
kx̂ − x? k22 + kv̂ − v ? k22

+p

(v̂ − v ? )
kx̂ − x? k22 + kv̂ − v ? k22

2

2

2
≥ kx̂ − x? k22 + kv̂ − v ? k22 · .
m
Rearranging yields the desired result.
q

To bound the Gaussian complexity of C3 (x? , v ? ) ∩ Sn+m−1 in terms of familiar parameters, we have the following result.
Lemma 3.
"
?

?

n+m−1

γ(C3 (x , v ) ∩ S

p

p
)≤2
η 2 (τ1 · ∂f (x? )) + η 2 (τ2 · ∂g(v ? )) +

#
(τ1 αf )2 + (τ2 αg )2
+ 1.
β

Proof. The proof is similar to that of lemma 2. By the definition of C3 (x? , v ? ), for any point (a, b) ∈ C3 (x? , v ? ), we have
ha, τ1 ui + hb, τ2 si −

1
[τ1 f (a) + τ2 g(b)] ≤ 0
β

for any u ∈ ∂f (x? ) and s ∈ ∂g(v ? ). It then follows from the Cauchy-Schwarz inequality that
1
[τ1 f (a) + τ2 g(b)]
β
1
≤ kak2 kg − τ1 uk2 + kbk2 kh − τ2 sk2 + [τ1 f (a) + τ2 g(b)],
β

ha, gi + hb, hi ≤ ha, g − τ1 ui + hb, h − τ2 si +

3 The

n
dual norm of f is defined as f ∗ (d) = supu∈Bn hu, di, where Bn
f = {u ∈ R : f (u) ≤ 1}.
f

12

where g ∈ Rn and h ∈ Rm are arbitrary vectors. Choosing suitable ũ ∈ ∂f (x? ) and s̃ ∈ ∂g(v ? ) such that
kg − τ1 · ũk2 = dist(g, τ1 · ∂f (x? )) := d0f
and
kh − τ2 · s̃k2 = dist(h, τ2 · ∂g(v ? )) := d0g ,
we obtain
ha, gi + hb, hi ≤ kak2 · dist(g, τ1 · ∂f (x? )) + kbk2 · dist(h, τ2 · ∂g(v ? )) +
≤ d0f · kak2 + d0g · kbk2 +

1
[τ1 f (a) + τ2 g(b)]
β

(37)

1
[τ1 αf kak2 + τ2 αg kbk2 ],
β

where the last inequality follows from the definition of the compatibility constant.
Then, by the definition of Gaussian width,



ω C3 (x? , v ? ) ∩ Sn+m−1 = E
sup
hg, ai + hh, bi
(a,b)∈C3 (x? ,v ? )∩Sn+m−1

 0

τ2 αg
τ1 αf
· kak2 +
· kbk2
df · kak2 + d0g · kbk2 +
β
β
(a,b)∈C3 (x? ,v ? )∩Sn+m−1
p
q
2
2
(τ1 αf ) + (τ2 αg )
02
≤ E d02
f + dg +
β
p
p
(τ1 αf )2 + (τ2 αg )2
2
?
2
?
,
≤ η (τ1 · ∂f (x )) + η (τ2 · ∂g(v )) +
β
≤E

sup

where g ∼ N (0, In ) and h ∼ N (0, Im ). The second and the third inequalities follow from the Cauchy-Schwarz and Jensen’s
inequalities respectively. By (8), we complete the proof.
Clearly, (30) comes from Theorem 4 and Lemma 3.
1) Identify the Range of τ1 and τ2 : Since our result relies on Condition 1, it is necessary to identify the range of the
regularization parameters τ1 and τ2 under different kinds of noise. In the absence of noise (z = 0), we can easily see that
Condition 1 holds with τ1 ≥ 0 and τ2 ≥ 0. In general, we establish the following Chevet-type inequality which indicates
Condition 1 holds with high probability under both bounded and stochastic noise scenarios.
Lemma 4. Let A be an m × n matrix whose rows Ai are independent centered isotropic sub-Gaussian vectors with
maxi kAi kψ2 ≤ K, and w be any fixed vector. Let T be any bounded subset Rn . Then, for any t ≥ 0, the event


sup hAu, wi ≤ CKkwk2 γ(T ) + t · rad(T )
u∈T

holds with probability at least 1 − exp{−t2 }.
Proof. Define the random process
Xu := hAu, wi , for any u ∈ T ,
which has sub-Gaussian increments
kXu − Xu0 kψ2 = k hA(u − u0 ), wi kψ2
≤ kwk2 kA(u − u0 )kψ2
≤ CKkwk2 ku − u0 k2
for any u, u0 ∈ T . The first inequality follows from the definition of the ψ2 -norm of a sub-Gaussian random vector (13)
and the last inequality holds because { ATi , (u − u0 ) }m
i=1 are independent centered sub-Gaussian random variables with
k ATi , (u − u0 ) kψ2 ≤ Kku − u0 k2 and hence kA(u − u0 )kψ2 ≤ CKku − u0 k2 . Define T̄ = T ∪ {0}. It follows from
Talagrand’s Majorizing Measure Theorem that the event
sup hAu, wi ≤ sup | hAu, wi | = sup | hAu, wi |
u∈T

u∈T

u∈T̄

= sup | hAu, wi − hA0, wi |
u∈T̄

≤ sup | hAu, wi − hAu0 , wi |
u,u0 ∈T̄
0

≤ C Kkwk2 (ω(T̄ ) + t diam(T̄ ))
≤ C 00 Kkwk2 (γ(T ) + t rad(T ))

13

holds with probability at least 1 − exp{−t2 }. In the last inequality, we have used the facts that ω(T̄ ) ≤ γ(T̄ ) = γ(T ) and
diam(T ) ≤ 2 rad(T ). This completes the proof.
√
Bounded Noise Case: When the noise is bounded (kzk2 ≤ δ), it follows from Lemma 4 that the event (choosing t = m)

√
CKδ 
f ∗ (ΦT z) = sup hΦu, zi ≤ √
γ(Bnf ) + m · rf
n
m
u∈Bf
holds with probability at least 1 − exp(m), where Bnf = {u ∈ Rn : f (u) ≤ 1} and rf = sup{kuk2 : u ∈ Bnf }. Thus it is
natural to choose

√
CKδβ 
γ(Bnf ) + m · rf := τ1B ,
(38)
τ1 ≥ √
m
which implies that the first part of Condition 1 holds with high probability. In addition, note that g ∗ (z) = supu∈Bm
hz, ui ≤
g
m
m
m
kuk
=
δ
·
r
,
where
B
=
{u
∈
R
:
g(u)
≤
1}
and
r
=
sup{kuk
:
u
∈
B
}.
Therefore,
we
can
choose
δ supu∈Bm
2
g
g
2
g
g
g
τ2 ≥ βδ · rg := τ2B .

(39)

vector satisfying (7), then kzk2 concentrates near the value
√ Sub-Gaussian Noise Case: When z is a sub-Gaussian random√
m with high probability [25, Theorem 3.1.1], namely kkzk2 − mkψ2 ≤ CK 2 . This implies


√
√
√
P kzk2 ≥ (L2 + 1) m ≤ P kzk2 − m ≥ L2 m ≤ 2e−cm .
Combining this with Lemma 4 and taking union bound yields


√
f ∗ (ΦT z) = sup hΦu, zi ≤ CK(1 + L2 ) γ(Bnf ) + m · rf
u∈Bn
f

with probability at least 1 − 3e−cm . Thus we can choose


√
τ1 ≥ CK(1 + L2 )β γ(Bnf ) + m · rf := τ1S ,

(40)

which means that the first part of Condition 1 holds with high probability in the sub-Gaussian noise case. For the second part
of Condition 1, note that the random process
Xa := ha, zi ,

for any a ∈ T

has sub-Gaussian increments
kXa − Xa0 kψ2 = k ha − a0 , zi kψ2 ≤ L · ka − a0 k2

for any a, a0 ∈ T .

It follows from Talagrand’s Majorizing Measure Theorem that the event (similar arguments to that of Lemma 4)
sup ha, zi ≤ CL[γ(T ) + t rad(T )]
a∈T

holds with probability at least 1 − exp(−t2 ). Choosing t =

√

m, we obtain that the event


√
g ∗ (z) = sup hz, ui ≤ CL γ(Bm
m · rg
g )+
u∈Bm
g

holds with probability at least 1 − exp{−m}. Thus, in the sub-Gaussian noise case, we can choose


√
τ2 ≥ CLβ γ(Bm
m · rg := τ2S .
g )+

(41)

2) How to Choose the Regularization Parameters τ1 and τ2 ?: Once the range of τ1 and τ2 is determined, then we can choose
the “best” regularization parameters under certain criteria in this range. Our theoretical results show that both the number of
observations (30) and the recovery error bound (32) rely on the regularization parameters τ1 and τ2 . Then one might expect
to select τ1 and τ2 in the specified range such that these two quantities are as small as possible. However, it is not hard to
see that these two quantities do not achieve their minima at the same time in general, so it is practical to choose some criteria
which make a tradeoff between the number of observations and the recovery error bound. Specifically, if one wants to choose
τ1 and τ2 such that the number of observations (30) which guarantees successful recovery for (5) is as small as possible, then
one can pick
(
)
(
)
αf2 2
αg2 2
?
2
?
?
2
?
and τ2· = arg min η (τ2 · ∂g(v )) + 2 τ2 ,
(42)
τ1· = arg min η (τ1 · ∂f (x )) + 2 τ1
τ2 ≥τ2·
τ1 ≥τ1·
β
β
where τ1· (or τ2· ) denotes τ1B (or τ2B ) in the bounded noise case and τ1S (or τ2S ) in the sub-Gaussian noise case. Moreover,
when both ∂f (x? ) and ∂g(v ? ) are nonempty, compact, and do not contain the original, by the strict convexity of objective

14

functions, these “best” parameters are uniquely attained. If one wants to select τ1 and τ2 which make the recovery error bound
(32) as small as possible, then one can pick
?
τ1·
= arg min

τ1 ≥τ1·

2m(β + 1)αf
2m(β + 1)αg
?
τ1 = τ1· and τ2·
= arg min
τ2 = τ2· .
τ2 ≥τ2·
β2
β2

(43)

This result demonstrates that if we want to recover signal and corruption accurately by the fully penalized procedure in the
noise-free case, we require
τ1 → 0+ and τ2 → 0+ ,
(44)
which might be regarded as promoting the equality constraint y = Φx + v in the fully penalized optimization problem.
D. Relationships Among Three Procedures
The theory of Lagrange multipliers [34, Section 28] asserts that the three procedures are essentially equivalent when the
regularization parameters λ, τ1 , and τ2 are chosen correctly. However, the primary difficulty lies in determining these parameters
when prior information is unavailable. Our results, (24), (30), and (32), suggest some useful strategies to choose these parameters
and shed some light on the relationships among these approaches.
Let m1 , m2 , and m3 be the necessary numbers of observations which guarantee successful recovery for constrained, partially
penalized, and fully penalized recovery procedures, respectively. Since C1 (x? , v ? ) ⊆ C2 (x? , v ? ) ⊆ C3 (x? , v ? ), by the definition
of Gaussian complexity, we have γ(C1 (x? , v ? ) ∩ Sn+m−1 ) ≤ γ(C2 (x? , v ? ) ∩ Sn+m−1 ) ≤ γ(C3 (x? , v ? ) ∩ Sn+m−1 ) and hence
m1 ≤ m2 ≤ m3 . This relation seems natural, because one might expect that the more prior information, the less number of
measurements to guarantee success.
On the other hand, it follows from [20, Theorem 4.3, Proposition 10.2] and [17, Proposition 1] that, under a weak
decomposition assumption4 , the optimized Gaussian squared distance minκ≥0 η 2 (κ · ∂f (x? )) provides a faithful approximation
to the statistical dimension ι(Tf (x? )), and hence the squared Gaussian width ω 2 (Tf (x? )∩Sn−1 ), i.e., minκ≥0 η 2 (κ·∂f (x? )) ≈
ω 2 (Tf (x? ) ∩ Sn−1 ). This implies that
η 2 (λ?1 · ∂f (x? )) ≈ ω 2 (Tf (x? ) ∩ Sn−1 ) and η 2 (λ?2 · ∂g(v ? )) ≈ ω 2 (Tg (v ? ) ∩ Sm−1 ),
provided that both ∂f (x? ) and ∂g(v ? ) are nonempty, compact, and do not contain the original. It then follows from (20) and
(24) that m1 ≈ m2 if we choose λ according to (29). For the fully penalized procedure, if we pick τ1 and τ2 according to
(42) under the noise-free case, i.e.,
(
)
(
)
αf2 2
αg2 2
?
2
?
?
2
?
τ1 = arg min η (τ1 · ∂f (x )) + 2 τ1
and τ2 = arg min η (τ2 · ∂g(v )) + 2 τ2 ,
τ1 >0
τ2 >0
β
β
and if β is chosen large enough such that both αf2 τ12 /β 2 and αg2 τ22 /β 2 are negligible, then we have τ1? ≈ λ?1 and τ2? ≈ λ?2 ,
and hence m2 ≈ m3 . Thus we might conclude that under proper parameter selection strategies, the three approaches are
approximately equivalent in terms of the necessary number of observations to guarantee success.
V. N UMERICAL S IMULATIONS
In this section, we provide a series of numerical tests to verify our theoretical results in Section IV. We present constrained,
partially penalized, and fully penalized recovery experiments for sparse signals and sparse corruptions in the absence or presence
of noise. In each experiment, we employ the CVX Matlab package [35], [36] to solve our convex optimization problems.
A. Phase Transition of Constrained Recovery Procedure
We first investigate the empirical behavior of the constrained recovery procedure when the noise level δ = 0 and the norm
of the true signal f (x? ) = kx? k1 are known exactly. We fix the sample size and signal length m = n = 128, and vary the
sparsity levels (ssig , scor ) ∈ [1, 128] × [1, 128]. We implement the following experiment 20 times for each (ssig , scor ) pair:
(1) Generate a signal vector x? with ssig independent standard normal entries and set the other n − ssig entries to 0.
(2) Generate a corruption vector v ? with scor independent standard normal entries and set the other m − scor entries to 0.
(3) For Gaussian measurements, draw a sensing matrix Φ ∈ Rm×n with independent N (0, 1/m) entries;
 for scaled
√ symmetric
m×n
Bernoulli
measurements,
draw
a
sensing
matrix
Φ
∈
R
with
independent
entries
obeying
P
Φ
=
1/
m = 1/2
i,j

√
and P Φi,j = −1/ m = 1/2.
(4) Solve the following constrained optimization problem:
(x̂, v̂) ∈ arg min kvk1 , s.t. kxk1 ≤ kx? k1 , y = Φx + v.
x,v

4 For

x 6= 0, ∂f (x) satisfies the weak decomposition assumption: ∃w0 ∈ ∂f (x) s.t. hw − w0 , w0 i = 0, ∀w ∈ ∂f (x).

(45)

15

Gaussian Measurements

Bernoulli Measurements

Theory

120

0.9

0.9

Theory

120

0.8

0.8

100

100

0.6

80

0.5
60
0.4
0.3

40

0.7
Sparsity level of corruption

Sparsity level of corruption

0.7

0.6

80

0.5
60
0.4
0.3

40

0.2
20

0.2
20

0.1

20

40

60

80

100

120

0

0.1

20

40

Sparsity level of signal

60

80

100

0

120

Sparsity level of signal

Fig. 3. Phase transition of the constrained recovery procedure (45) under Gaussian and Bernoulli measurements. The red curve plots the phase transition
threshold predicted by (46).

(5) Declare success if kx̂ − x? k2 /kx? k2 ≤ 10−3 .
To compare these empirical results with our theory, we overlay the theoretical recovery threshold suggested by (20)5
ω 2 (Tf (x? ) ∩ Sn−1 ) + ω 2 (Tg (v ? ) ∩ Sm−1 ),

(46)

where the squared Gaussian widths of signals and corruptions can be accurately estimated by (see, e.g., [19, Appendix C] or
[17, eq.(10)])




Z ∞
2(n − ssig )
2
2
2
−x2 /2
−t2 /2
√
(1 + t )
e
dx − te
min E
inf
kg − uk2 = min ssig (1 + t ) +
t≥0
t≥0
u∈t·∂kx? k1
2π
t
and

min E
t≥0

inf

u∈t·∂kv ? k1

kg −

uk22



2(m − scor )
√
= min scor (1 + t ) +
t≥0
2π
2


Z
2
(1 + t )

∞

e

−x2 /2

dx − te

−t2 /2


,

t

respectively.
Fig. 3 displays the empirical probability of success for each setting of (ssig , scor ) averaged over the 20 runs. We can
see that our theoretical recovery threshold closely aligns with observed phase transition under both Gaussian and Bernoulli
measurements.
B. Phase Transition of Partially Penalized Recovery Procedure
We next consider the partially penalized recovery procedure in the noiseless setting where neither f (x) = kx? k1 nor
g(v) = kv ? k1 is known beforehand. The experiment settings are almost the same as in the constrained case except that we
recover signals and corruptions via the following procedure in step (4):
min kxk1 + λkvk1 , s.t. y = Φx + v.
x,v

(47)

We test two kinds of the regularization parameter: 1) λ = λ? , which is chosen according to (29) and depends on the signal and
corruption sparsity levels ssig and scor , and 2) λ = 1. As discussed in Section IV-D, when we choose λ = λ? , the necessary
number of measurements to guarantee success by the partially penalized procedure is nearly the same as that of the constrained
one. Thus, we also overlay the curve of (46) to compare with the empirical results.
Fig. 4 shows the empirical probability of success as the signal and corruption sparsity levels ssig and scor vary. We can find
that the recovery performance in the case of λ = λ? is better than that in the case of λ = 1. This demonstrates that the choice
of the regularization parameter suggested by (29) is effective. Moreover, signal recovery with λ = λ? is nearly as good as in
the constrained case, but without any prior knowledge of kx? k1 .
5 In [21], the second author of this paper and his collaborators have shown that the phase transition of the constrained procedure under Gaussian measurements
occurs around ω 2 (Tf (x? ) ∩ Sn−1 ) + ω 2 (Tg (v ? ) ∩ Sm−1 ). A large number of numerical experiments indicate that this theoretical recovery threshold also
holds for sub-Gaussian measurements. This observed universality phenomenon suggests us to set CK 4 = 1 in (20) for our numerical simulations.

16

Gaussian Measurements, λ = 1

Gaussian Measurements, λ = λ?

Theory

120

0.9

Theory

120

0.8

0.8

100

100

0.6

80

0.5
60
0.4
0.3

40

0.7
Sparsity level of corruption

Sparsity level of corruption

0.7

0.6

80

0.5
60
0.4
0.3

40

0.2

0.2

20

20
0.1

20

40

60

80

100

120

0.1

0

20

40

Sparsity level of signal

60

80

100

120

0

Sparsity level of signal

Bernoulli Measurements, λ =1

Bernoulli Measurements, λ = λ?

Theory

120

0.9

Theory

120

0.8

0.9
0.8

100

100

0.6

80

0.5
60
0.4
0.3

40

0.7
Sparsity level of corruption

0.7
Sparsity level of corruption

0.9

0.6

80

0.5
60
0.4
0.3

40

0.2
20

0.2
20

0.1

20

40

60

80

100

120

0

Sparsity level of signal

0.1

20

40

60

80

100

120

0

Sparsity level of signal

Fig. 4. Phase transition of the partially penalized recovery procedure (47) with different kinds of the regularization parameter under Gaussian and Bernoulli
measurements. The red curve plots the phase transition threshold predicted by (46).

C. Phase Transition of Fully Penalized Recovery Procedure
Thirdly, we study the empirical behavior of the fully penalized recovery procedure in the noiseless setting where neither
f (x) = kx? k1 nor g(v) = kv ? k1 is known a priori. Similarly, the experiment settings are nearly the same as in the constrained
case except that we reconstruct signals and corruptions via the following procedure in step (4):
1
min ky − Φx − vk22 + τ1 kxk1 + τ2 kvk1 .
(48)
x,v 2
As suggested in Section IV-C2, in order to recover signals and corruptions faithfully by this procedure, we require that the
regularization parameters τ1 and τ2 tend to zero. Thus we set τ1 = τ2 = 10−5 . For reference, we also overlay the curve of
(46) to compare with the empirical results.
Fig. 5 illustrates the average empirical probability of success for each setting (ssig , scor ). We can see that the theoretical
recovery threshold (46) roughly predict observed phase transition with this choice of the regularization parameters.
D. Stable Recovery
Finally, we investigate the empirical behavior of the three procedures under noisy measurements. We fix m = n = 128 and
ssig = scor = 20. The first three steps of this experiment are the same as that in the constrained case and the other steps are
as follows:
(4) Generate a Gaussian noise vector z and scale z such that kzk2 = δ.
(5) Solve constrained, partially penalized, and fully penalized procedures under different noise levels with different regularization parameters. In the partially penalized case, we choose λ = λ? according to (29) or λ = 1. In the fully penalized

17

Gaussian Measurements, τ1=τ2=10−5

Bernoulli Measurements, τ1=τ2=10−5

0.9

Theory

120

0.9

Theory

120

0.8

0.8

100

100

0.6

80

0.5
60
0.4
0.3

40

0.7
Sparsity level of corruption

Sparsity level of corruption

0.7

0.6

80

0.5
60
0.4
0.3

40

0.2

0.2

20

20
0.1

20

40

60

80

100

0.1

0

120

20

40

Sparsity level of signal

60

80

100

0

120

Sparsity level of signal

Fig. 5. Phase transition of the fully penalized recovery procedure (48) with τ1 = τ2 = 10−5 under Gaussian and Bernoulli measurements. The red curve
plots the phase transition threshold predicted by (46).

Bernoulli Measurements
5

4.5

4.5

4

4

3.5

3.5
Recovery error

Recovery error

Gaussian Measurements
5

CP

3

PPP λ = λ?
2.5

PPP λ = 1
FPP τ1 = τ2 = 2δ

2

FPP τ1 = τ2 = 1

1.5

3

PPP λ = 1
2

0.5

0.5

0.05

0.1

0.15

0.2
0.25
0.3
Noise level δ

0.35

0.4

0.45

FPP τ1 = τ2 = 2δ
FPP τ1 = τ2 = 1

1.5
1

0

PPP λ = λ?

2.5

1

0

CP

0.5

0

0

0.05

0.1

0.15

0.2
0.25
0.3
Noise level δ

0.35

0.4

0.45

0.5

q
Fig. 6. Recovery error kx̂ − x? k22 + kv̂ − v ? k22 by constrained, partially penalized, and fully penalized procedures (abbreviated as CP, PPP, and FPP,
respectively) under different noise levels with different regularization parameters. Left: Gaussian measurements, right: Bernoulli measurements.

case, we choose τ1 √
and τ2√according
(43) or τ1 = τ2 = 1. Here, for sparse signal and sparse corruption, (43) implies
√
τ1 = τ1B ≈ CKβδ( n + m)/ m = 2CKβδ = C 0 Kβδ and τ2 = τ2B = βδ. In our simulations, we choose C 0 K = 1
and β = 2.
p
(6) Record the `2 recovery error kx̂ − x? k22 + kv̂ − v ? k22 in each case.
Fig. 6 shows the average recovery error across 20 runs. We can see that the recovery error increases linearly as the noise level
increases in both constrained and partially penalized cases, which is consistent with our theoretical results (Theorems 2 and 3).
Moreover, the partially penalized procedure with different regularization parameters shows almost the same performance as the
constrained one when the sparsity levels of signal and corruption are not too high (ssig = scor = 20). This implies that when
the estimate of the sparsity levels ssig and scor is unavailable, the setting λ = 1 yields high probability recovery, provided that
the sparsity levels of signal and corruption are relatively low. In the fully penalized case, the recovery performance with τ1 and
τ2 chosen according to (43) is much better than that with τ1 = τ2 = 1. This demonstrates the effectiveness of the parameter
selection strategy (43).
VI. C ONCLUSION
In this paper, we have established an extended matrix deviation inequality for sub-Gaussian matrices, which provides a
powerful tool to analyze the corrupted sensing problem. We then presented performance analysis for three convex recovery

18

procedures which are used to recover structured signals from corrupted sub-Gaussian measurements when different kinds of
prior information are available. We considered both bounded and stochastic noise. Our results have shown that, under proper
conditions, these approaches reconstruct both signal and corruption exactly in the absence of noise and stably in the presence
of noise. Moreover, our results also indicate how to pick the regularization parameters in both partially and fully penalized
recovery procedures and reveal the relationships among these methods. For future work, it would be of great interest to establish
the phase transition theory for both constrained and partially penalized procedures under sub-Gaussian measurements.
A PPENDIX A
S OME P ROPERTIES OF S UB -G AUSSIAN AND S UB - EXPONENTIAL RANDOM VARIABLES AND VECTORS
Fact 2 (Product of sub-Gaussians is sub-exponential). [25, Lemma 2.7.7] Let X and Y be sub-Gaussian random variables
(not necessarily independent). Then XY is sub-exponential. Moreover,
kXY kψ1 ≤ kXkψ2 kY kψ2 .

(49)

Fact 3 (Centering). [25, Lemma 2.6.8 and Exercise 2.7.10] If X is sub-Gaussian (or sub-exponential), then so is X − E X.
Moreover,
kX − E Xkψ2 ≤ CkXkψ2 and
kX − E Xkψ1 ≤ CkXkψ1 .
Fact 4 (Hoeffding-type Inquality). [25, Theorem 2.6.3] Let X1 , . . . , Xm be independent, mean-zero, sub-Gaussian random
variables, and a = (a1 , a2 , . . . , am )T ∈ Rm . Then, for any t ≥ 0, we have
( m
)


X
ct2
,
(50)
P
ai Xi ≥ t ≤ 2 exp − 2
K kak22
i=1
where K = maxi kXi kψ2 .
Fact 5 (Bernstein-type Inequality). [25, Theorem 2.8.2] Let X1 , X2 , . . . , Xm be independent, mean-zero, sub-exponential
random variables, and a = (a1 , a2 , . . . , am )T ∈ Rm . Then, for any t ≥ 0, we have
)
( m



X
t2
t
ai Xi ≥ t ≤ 2 exp −c min
P
,
,
(51)
K 2 kak22 Kkak∞
i=1
where K = maxi kXi kψ1 .
A PPENDIX B
P ROOF OF T HEOREM 1
√

In order to prove
p Theorem 1, we need the following key lemma which states that the random process Xa,b := kAa +
√
mbk2 − m · kak22 + kbk22 has sub-Gaussian increments.

Lemma 5 (Sub-Gaussian Process). Let A be an m×n matrix whose rows Ai are independent centered isotropic sub-Gaussian
vectors. Then the random process
√
√
Xa,b = kAa + mbk2 − (E kAa + mbk22 )1/2
q
√
√
= kAa + mbk2 − m · kak22 + kbk22
has sub-Gaussian increments:
kXa,b − Xa0 ,b0 kψ2 ≤ CK 2 ·

q

ka − a0 k22 + kb − b0 k22

for every (a, b), (a0 , b0 ) ∈ Rn × Rm ,

where K = maxi kAi kψ2 .
Proof. See Appendix C.
Combing Lemma 5 and Talagrand’s Majorizing Measure Theorem yields the proof of Theorem 1.
Proof. According to Lemma 5, the random process
Xa,b := kAa +

√

mbk2 −

√

m·

q
kak22 + kbk22

has sub-Gaussian increments, that is
kXa,b − Xa0 ,b0 kψ2 ≤ CK 2 ·
= CK 2

q

ka − a0 k22 + kb − b0 k22
   0
a
a
− 0
b
b 2

(52)

19

for every (a, b), (a0 , b0 ) ∈ T . It follows from Talagrand’s Majorizing Measure Theorem that
   
g
a
2
0
0
Xa,b − Xa ,b ≤ CK E sup
,
E
sup
h
b
0
0
(a,b)∈T
(a,b),(a ,b )∈T
= CK 2 ω(T ),
where g ∼ N (0, In ) and h ∼ N (0, Im ). Thus, fix an arbitrary point (a0 , b0 ) ∈ T and use the triangle inequality to obtain
E sup

Xa,b ≤ E sup

Xa,b − Xa0 ,b0 + E Xa0 ,b0

(a,b)∈T
2

(a,b)∈T

≤ CK ω(T ) + E Xa0 ,b0 .
The second term can be bounded as follows:
E Xa0 ,b0 ≤ C 0 kXa0 ,b0 kψ2 ≤ C 00 K 2 ·

 
a0
b0

.
2

The first inequality follows from the equivalent definition (10) and the second inequality holds by using Lemma 5 with
[a0T , b0T ]T = 0. Therefore, by (8), we have
 
a0
E sup Xa,b ≤ CK 2 ω(T ) + C 00 K 2 ·
b0 2
(a,b)∈T
≤ C0 K 2 γ(T ).
This establishes the expectation bound.
For the high probability bound, define T̄ = T ∪ {0}. It also follows from Talagrand’s Majorizing Measure Theorem that
with probability at least 1 − exp(−t2 ),
sup
(a,b)∈T

Xa,b =

sup

Xa,b =

(a,b)∈T̄

sup

Xa,b − X0,0

(a,b)∈T̄

≤

sup
(a,b),(a0 ,b0 )∈T̄

0 2

Xa,b − Xa0 ,b0

≤ C K ω(T̄ ) + t · diam(T̄ )


≤ CK 2 γ(T ) + t · rad(T ) .



In the last inequality, we have used the facts that ω(T̄ ) ≤ γ(T̄ ) = γ(T ) and diam(T̄ ) ≤ 2 rad(T ). This completes the
proof.
A PPENDIX C
P ROOF OF L EMMA 5
Our proof of Lemma 5 is inspired by [37] and [23]. For clarity, the proof is divided into three steps. First, we show a partial
case of Lemma 5 in which (aT , bT )T ∈ Sn+m−1 and (a0T , b0T )T = 0. We then extend this by allowing (a0T , b0T )T to be an
arbitrary unit vector. Finally, we prove the increment inequality (52) for any (a, b), (a0 , b0 ) ∈ Rn × Rm .
Since Ai are isotropic sub-Gaussian random vectors, it follows from (10) that K is bounded below by an absolute constant.
For simplicity, we will assume that K ≥ 1.
Step 1: (aT , bT )T ∈ Sn+m−1 and (a0T , b0T )T = 0. In this case, we have the following result.
Lemma 6. Let A be a sub-Gaussian random matrix as in Lemma 5. Then
√
√
kAa + mbk2 − m
≤ CK 2 for every [aT , bT ]T ∈ Sn+m−1 .
ψ2

(53)

20

√
1
Proof. We begin with establishing a concentration inequality for m
kAa + mbk22 − 1. For any t ≥ 0, we have


√
1
2
(54)
p := P
kAa + mbk2 − 1 ≥ t
m


1
2
=P
kAak22 + √ hAa, bi + kbk22 − 1 ≥ t
m
m


1
2
=P
kAak22 − kak22 + √ hAa, bi ≥ t
m
m


1
2
2
2
≤P
kAak2 − kak2 + √ hAa, bi ≥ t
m
m




1
t
2
t
2
2
≤P
kAak2 − kak2 ≥
+ P √ hAa, bi ≥
m
2
2
m
=: p1 + p2 .
Pm
2
1
1
T
kAak22 − kak22 as a sum of independent random variables m
−
To bound p1 , it will be useful to express m
i=1 [ Ai , a
P
2
m
1
2
T
m
T
kak2 ] := m i=1 Zi . By assumption, { Ai , a }i=1 are independent centered sub-Gaussian random variables with E Ai , a =
kak22 and k ATi , a kψ2 ≤ Kkak2 ≤ K. Therefore, by facts 3 and 2 , {Zi }m
i=1 are independent centered sub-exponential
random variables with
kZi kψ1 = k ATi , a

2

≤ Ck ATi , a

− E ATi , a
2

2

kψ1

kψ1 by Fact 3

≤ Ck ATi , a k2ψ2

by Fact 2

2

≤ CK .
It follows from Bernstein’s inequality (Fact 5) that
)
(
m
t
1 X
Zi ≥
(55)
p1 =P
m i=1
2


t2
t
≤2 exp −c min( 2 4
,
)
4C K /m 2CK 2 /m
n
o
cm
=2 exp − 2 4 min(t2 , 2CK 2 t)
K
o
n 4C
c1 m
≤2 exp − 4 min(t2 , t) .
K
The last inequality holds because we can easily choosePC such that 2CK 2 ≥ 1.
m
To bound p2 , it will be helpful to write hAa, bi = i=1 bi ATi , a , where { ATi , a }m
i=1 are independent centered subT
Gaussian random variable with k Ai , a kψ2 ≤ K. Applying Hoeffding’s inequality (Fact 4) yields
(
)
m
1 X
t
T
bi Ai , a ≥
(56)
p2 = P √
4
m i=1


cmt2
≤ 2 exp −
16K 2 kbk22


c2 mt2
≤ 2 exp −
.
K4
The last inequality holds because kbk2 ≤ 1 and K ≥ 1.
Combining the upper bounds of p1 and p2 yields


n c m
o
c2 mt2
1
p ≤ 2 exp − 4 min(t2 , t) + 2 exp −
K
K4
n c m
o
0
≤ 4 exp − 4 min(t2 , t) .
K
√
We then establish a concentration inequality for √1m kAa + mbk − 1. To this end, we will use the following fact
|z − 1| ≥ δ

implies |z 2 − 1| ≥ max(δ 2 , δ), for any z ≥ 0

and δ ≥ 0.

(57)

21

√1 kAa
m

√

mbk together with (57) where t = max{δ 2 , δ}, we obtain for any δ ≥ 0 that



√
√
1
1
2
2
P √ kAa + mbk2 − 1 ≥ δ ≤P
kAa + mbk2 − 1 ≥ max(δ , δ)
m
m


c0 mδ 2
.
≤4 exp −
K4
√
√
This implies kAa + mbk2 − m ψ2 ≤ CK 2 and completes the proof.
Using this for z =

+



Step 2: (aT , bT )T ∈ Sn+m−1 and (a0T , b0T )T ∈ Sn+m−1 . In this case, we have the following result.
Lemma 7. Let A be a sub-Gaussian random matrix as in Lemma 5. Then
q
√
√
≤ CK 2 · ka − a0 k22 + kb − b0 k22 ,
kAa + mbk2 − kAa0 + mb0 k2
ψ2

for every (aT , bT )T , (a0T , b0T )T ∈ Sn+m−1 .
Proof. Given t ≥ 0, it suffices to show
(
)
√
√


kAa + mbk2 − kAa0 + mb0 k2
−ct2
p
p := P
≥ t ≤ C exp
.
K4
ka − a0 k22 + kb − b0 k22
We will proceed √
differently for small and large t.
Case 1: t ≥ 2 m. Denote
a − a0
b − b0
p
u := p
and
v
:=
.
ka − a0 k22 + kb − b0 k22
ka − a0 k22 + kb − b0 k22
It follows from the triangle inequality that
(
)
√
kA(a − a0 ) + m(b − b0 )k2
p
p≤P
≥t
ka − a0 k22 + kb − b0 k22

√
= P kAu + mvk2 ≥ t

√
√
√
= P kAu + mvk2 − m ≥ t − m


√
√
t
≤ P kAu + mvk2 − m ≥
2


ct2
≤ 2 exp − 4 .
K
√
The second inequality
holds because t ≥ 2 m and the last inequality follows from Lemma 6.
√
Case 2: t ≤ 2 m. Denote
u0 = a + a0 and v 0 = b + b0 .
√
√
Multiplying both sides of the inequality defining p in (58) by kAa + mbk2 + kAa0 + mb0 k2 yields
(
)
√
√

√
√
kAa + mbk22 − kAa0 + mb0 k22
p
p=P
≥ t kAa + mbk2 + kAa0 + mb0 k2
ka − a0 k22 + kb − b0 k22
(
)
√
√
√
hA(a − a0 ) + m(b − b0 ), A(a + a0 ) + m(b + b0 )i
p
≤P
≥ t · kAa + mbk2
ka − a0 k22 + kb − b0 k22

√
√
√
=P
Au + mv, Au0 + mv 0 ≥ t · kAa + mbk2 .
Define the event Ω1 as

Ω1 :=

kAa +

√

mbk2 ≥

√ 
m
.
2

By the law of total probability, we have






√
√ 0
√
0
p≤P
Au + mv, Au + mv ≥ t · kAa + mbk2

{z
}

|
:=Ω0




= P Ω0 Ω1 · P Ω1 + P Ω0 Ωc1 · P Ωc1

 c
≤ P Ω0 and Ω1 + P Ω1
:= p1 + p2 .

(58)

22

We can easily bound p2 using Lemma 6

√ 
m
p2 = P
= P kAa + mbk2 ≤
2

√ 
√
√
m
= P kAa + mbk2 − m ≤ −
2

√ 
√
√
m
≤ P kAa + mbk2 − m ≥
2


√
√
√
t
≤ P kAa + mbk2 − m ≥
since t ≤ 2 m
4


c1 t2
since Lemma 6
≤ 2 exp −
16K 4
 00 2 
c t
≤ 2 exp − 4 .
K


Ωc1



√

To bound p1 , note that

p1 := P Ω0 and Ω1

√ 
√
√
t m
≤P
Au + mv, Au0 + mv 0 ≥
2

√ 
√
√
t m
0
0
0
0
= P hAu, Au i + m hv, v i + m hAu, v i + m hAu , vi ≥
2


√ 
√ 
√
√
t
t m
m
0
0
0
0
≤ P hAu, Au i + m hv, v i ≥
m hAu, v i + m hAu , vi ≥
+P
4
4



√ 
√ 
√ 
√
√
t m
t m
t m
0
0
0
0
+P
+P
≤ P hAu, Au i + m hv, v i ≥
m hAu, v i ≥
m hAu , vi ≥
4
8
8
=: p1a + p1b + p1c .
We bound the three terms separately. To bound p1a , note that
hb − b0 , b + b0 i
hv, v 0 i = p
ka − a0 k22 + kb − b0 k22
kbk22 − kb0 k22
=p
ka − a0 k22 + kb − b0 k22
kak22 − ka0 k22
= −p
ka − a0 k22 + kb − b0 k22
= − hu, u0 i .
Therefore, we can bound p1a as p1 (55) in Lemma 6

√ 
t m
0
0
p1a = P hAu, Au i + m hv, v i ≥
4

√ 
t
m
= P hAu, Au0 i − m hu, u0 i ≥
4
( m
√ )
X

t m
T
T
0
0
=P
Ai , u Ai , u − hu, u i ≥
4
i=1
( m
)
√
X
t m
=P
Zi ≥
.
4
i=1
By assumption, it follows from facts 3 and 2 that {Zi }m
i=1 are independent, mean-zero, sub-exponential random variables with
kZi kψ1 = k ATi , u
≤ C 0 k ATi , u

ATi , u0 − hu, u0 i kψ1
ATi , u0 kψ1

≤ C 0 k ATi , u kψ2 · k ATi , u0 kψ2
≤ C 0 K 2 kuk2 · ku0 k2 ≤ 2C 0 K 2 = CK 2 .

23

Using Bernstein’s inequality (Fact 5) yields



√
t2
mt
p1a ≤ 2 exp −c min
,
16C 2 K 4 4CK 2
n
√ o
c
2
2
≤ 2 exp −
min
t
,
4CK
t
m
2 4
n 16Cc K
o

√
2
2 2
≤ 2 exp −
since t ≤ 2 m
min
t
,
2CK
t
2
4
 16C 2K 
ct
choose C such that 2CK 2 ≥ 1
≤ 2 exp −
16C 2 K 4


c1 t2
≤ 2 exp − 4 .
K


Similar to p2 (56) in Lemma 6, we can easily obtain p1b ≤ 2 exp −c2 t2 /K 4 and p1c ≤ 2 exp −c3 t2 /K 4 . Combining
p1a , p1b , and p1c yields






c2 t2
c3 t 2
c1 t2
p1 ≤ 2 exp − 4 + 2 exp − 4 + 2 exp − 4
K
K
K
 0 2
ct
≤ 6 exp − 4 .
K
Therefore, we have


ct2
p ≤ p1 + p2 ≤ C exp − 4 .
K
This completes the proof.
Step 3: (a, b), (a0 , b0 ) ∈ Rn × Rm .
Finally, we prove the increment inequality (52) in full generality. Without lost of generality, we assume that kak22 +kbk22 = 1
T
T
and ka0 k22 + kb0 k22 ≥ 1. Define the unit vector (ā0 , b̄0 )T with
a0
ā0 := p
ka0 k22 + kb0 k22

and

b0
b̄0 := p
.
ka0 k22 + kb0 k22

Then we have
kXa,b − Xa0 ,b0 kψ2 ≤ kXa,b − Xā0 ,b¯0 kψ2 + kXā0 ,b¯0 − Xa0 ,b0 kψ2
=: R1 + R2 .
By Lemma 7, R1 ≤ CK 2 ·

q

2
2

a − ā0

+ b − b̄0

2
.
2

Since (ā0 , b̄0 ) and (a0 , b0 ) are colinear, we have

R2 = kXā0 ,b¯0 − Xa0 ,b0 kψ2
q
= ka0 − ā0 k22 + kb0 − b̄0 k22 · kXā0 ,b¯0 kψ2
q
≤ CK 2 · ka0 − ā0 k22 + kb0 − b̄0 k22 .
The last inequality follows from Lemma 6.
Combining R1 and R2 yields
R1 + R2 ≤

√

2CK 2 ·

q
ka − a0 k22 + kb − b0 k22 ,

where we have used the fact [25, Exercise 9.1.7] that
q
q
√ q
ka − ā0 k22 + kb − b̄0 k22 + kā0 − a0 k22 + kb̄0 − b0 k22 ≤ 2 ka − a0 k22 + kb − b0 k22 .
This completes the proof of Lemma 5.
ACKNOWLEDGMENT
The authors thank Huan Zhang and Xu Zhang for helpful discussions.

24

R EFERENCES
[1] J. Chen and Y. Liu, “Corrupted sensing with sub-gaussian measurements,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT). Aachen, Germany: IEEE, 2017,
pp. 516–520.
[2] 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.
[3] E. Elhamifar and R. Vidal, “Sparse subspace clustering,” in Proc. IEEE Conf. Comput. Vis. Pattern Recognit., Miami Beach, FL, 2009, pp. 2790–2797.
[4] 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.
[5] V. Chandrasekaran, S. Sanghavi, P. A. Parrilo, and A. S. Willsky, “Rank-sparsity incoherence for matrix decomposition,” SIAM J. Optim., vol. 21, no. 2,
pp. 572–596, 2011.
[6] J. Wright and Y. Ma, “Dense error correction via `1 -minimization,” IEEE Trans. Inf. Theory, vol. 56, no. 7, pp. 3540–3560, 2010.
[7] X. Li, “Compressed sensing and matrix completion with constant proportion of corruptions,” Construct. Approximation, vol. 37, no. 1, pp. 73–99, 2013.
[8] N. H. Nguyen and T. D. Tran, “Exact recoverability from dense corrupted observations via-minimization,” IEEE Trans. Inf. Theory, vol. 59, no. 4, pp.
2017–2035, 2013.
[9] ——, “Robust lasso with missing and grossly corrupted observations,” IEEE Trans. Inf. Theory, vol. 4, no. 59, pp. 2036–2058, 2013.
[10] P. Kuppinger, G. Durisi, and H. Bolcskei, “Uncertainty relations and sparse signal recovery for pairs of general signal sets,” IEEE Trans. Inf. Theory,
vol. 58, no. 1, pp. 263–277, 2012.
[11] 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.
[12] 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, 2013.
[13] C. Studer and R. G. Baraniuk, “Stable restoration and separation of approximately sparse signals,” Appl. Comp. Harmonic Anal., vol. 37, no. 1, pp.
12–35, 2014.
[14] E. J. Candès, X. Li, Y. Ma, and J. Wright, “Robust principal component analysis?” J. ACM, vol. 58, no. 3, pp. 1–37, 2011.
[15] H. Xu, C. Caramanis, and S. Sanghavi, “Robust pca via outlier pursuit,” IEEE Trans. Inf. Theory, vol. 58, no. 5, pp. 3047–3064, 2012.
[16] H. Xu, C. Caramanis, and S. Mannor, “Outlier-robust pca: the high-dimensional case,” IEEE Trans. Inf. Theory, vol. 59, no. 1, pp. 546–572, 2013.
[17] R. Foygel and L. Mackey, “Corrupted sensing: Novel guarantees for separating structured signals,” IEEE Trans. Inf. Theory, vol. 60, no. 2, pp. 1223–1247,
2014.
[18] M. B. McCoy and J. A. Tropp, “Sharp recovery bounds for convex demixing, with applications,” Found. Comput. Math., vol. 14, no. 3, pp. 503–567,
2014.
[19] V. Chandrasekaran, B. Recht, P. A. Parrilo, and A. S. Willsky, “The convex geometry of linear inverse problems,” Found. Comput. Math., vol. 12, no. 6,
pp. 805–849, 2012.
[20] D. Amelunxen, M. Lotz, M. B. McCoy, and J. A. Tropp, “Living on the edge: Phase transitions in convex programs with random data,” Inf. Inference,
no. 3, pp. 224–294,.
[21] H. Zhang, Y. Liu, and H. Lei, “On the phase transition of corrupted sensing,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT). Aachen, Germany: IEEE,
2017, pp. 521–525.
[22] J.-B. Hiriart-Urruty and C. Lemaréchal, Convex Analysis and Minimization Algorithms I: Fundamentals. New York: Springer-Verlag, 1993.
[23] C. Liaw, A. Mehrabian, Y. Plan, and R. Vershynin, “A simple tool for bounding the deviation of random matrices on geometric sets,” in Geometric
Aspects of Functional Analysis. Springer, 2017, pp. 277–299.
[24] R. Vershynin, “Introduction to the non-asymptotic analysis of random matrices,” in Compressed Sensing: Theory and Applications, Y. Eldar and
G. Kutyniok, Eds. Cambridge, U.K.: Cambridge Univ. Press., 2012, pp. 210–268.
[25] ——, High-Dimensional Probability An Introduction with Applications in Data Science.
Book draft, available at:
https://www.math.uci.edu/ rvershyn/papers/HDP-book/HDP-book.pdf, 2017.
[26] M. Talagrand, The Generic Chaining: Upper and Lower Bounds of Stochastic Processes. New York, NY, USA: Springer-Verlag, 2005.
[27] S. Dirksen, “Tail bounds via generic chaining,” Electron. J. Probab., vol. 20, no. 53, pp. 1–29, 2015.
[28] P. J. Bickel, Y. Ritov, and A. B. Tsybakov, “Simultaneous analysis of lasso and dantzig selector,” Ann. Statist., vol. 37, no. 4, pp. 1705–1732, 2009.
[29] B. Klartag and S. Mendelson, “Empirical processes and random projections,” J. Funct. Anal., vol. 225, no. 1, pp. 229–245, 2005.
[30] S. Mendelson, A. Pajor, and N. Tomczak-Jaegermann, “Reconstruction and subgaussian operators in asymptotic geometric analysis,” Geom. Funct. Anal.,
vol. 17, no. 4, pp. 1248–1282, 2007.
[31] C. Thrampoulidis, S. Oymak, and B. Hassibi, “Recovering structured signals in noise: least-squares meets compressed sensing,” in Compressed Sensing
and its Applications. Springer, 2015, pp. 97–141.
[32] Y. Gordon, “On Milman’s inequality and random subspaces which escape through a mesh in Rn .” New York, NY, USA: Springer-Verlag, 1988, pp.
84–106.
[33] S. N. Negahban, P. Ravikumar, M. J. Wainwright, and B. Yu, “A unified framework for high-dimensional analysis of m-estimators with decomposable
regularizers,” Statist. Sci., vol. 27, no. 4, pp. 538–557, 11 2012.
[34] R. T. Rockafellar, Convex analysis. Princeton university press, 2015.
[35] M. Grant and S. Boyd, “CVX: Matlab software for disciplined convex programming, version 2.1,” http://cvxr.com/cvx, Mar. 2014.
[36] ——, “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.
[37] G. Schechtman, “Two observations regarding embedding subsets of euclidean spaces in normed spaces,” Adv. Math., vol. 200, pp. 125–135, 2006.

