Sparse recovery using the preservability of the null space property
under random measurements

arXiv:1710.09972v1 [] 27 Oct 2017

Pete Casazza∗

Xuemei Chen†

Richard Lynch‡

October 30, 2017

Abstract
The field of compressed sensing has become a major tool in high-dimensional analysis, with
the realization that vectors can be recovered from relatively very few linear measurements as
long as the vectors lie in a low-dimensional structure, typically the vectors that are zero in most
coordinates with respect to a basis. However, there are many applications where we instead
want to recover vectors that are sparse not with respect to a basis, but rather to a general
dictionary. That is, the vector can be written as the linear combination of very few columns of
a matrix D, where the columns of D form a (typically overcomplete) spanning set.
In this direction, we show that as an matrix D stays bounded away from zero in norm on a
set S and a provided map Φ comprised of i.i.d. subgaussian rows has number of measurements
at least proportional to the square of w(DS), the Gaussian width of the related set DS, then
with high probability the composition ΦD also stays bounded away from zero in norm on S
with bound proportional to w(DS). This result has potential as a powerful tool in dimension
reduction analysis. As a specific application, we obtain that the null space property is preserved
under such subgaussian maps with high probability. This result is nearly optimal in the sense
that we require only a minimal condition on D. Consequently we obtain stable recovery guarantees for dictionary-sparse signals via the ℓ1 -synthesis method, which is typically challenging,
even with random measurements.

1

Introduction

An important problem in high-dimensional analysis is to recover a signal from undersampled and
corrupted measurements. This problem is ill-posed if no further assumptions are imposed on the
signal class. With the breakthrough of compressive sensing (CS), we now know it is possible to
recover signals from an inadequate number of (typically noisy) measurements, provided that the
signals are sitting in a low-dimensional structure.
To make this more concrete, we will use standard CS terminology. We wish to recover a signal
z0 ∈ Rd from its undersampled and corrupted linear measurements y = Φz0 + e ∈ Rm , with the
noise satisfying kek2 ≤ ε. The number of measurements m is assumed to be far less than the
ambient dimension d, meaning the system has infinitely many solutions in general. To surpass
this hurdle, we assume the signal z0 has a sparse structure, that is, it can be written as the linear
combination of only a few atoms from a dictionary. In other words, if D is the matrix whose
columns are the atoms, then z0 = Dx0 for some x0 whose coordinates are mostly zero.
∗

Department of Mathematics, University of Missouri, Columbia, MO
Department of Mathematics & Statistics, University of San Francisco, San Francisco, CA
‡
Department of Mathematics, Texas A& M University, College Station, TX
†

1

To recover dictionary-sparse signals, there are mainly two classes of algorithms: convex programming and greedy algorithms [12, 35, 7, 21, 39, 15, 30]. This paper will focus on convex problems
of the following form:
b
z = arg min fD (z),
z∈Rd

subject to ky − Φzk2 ≤ ε,

(1)

where fD (z) is a convex function of z. The unified form (1) is not new, see [14] for example. Two
questions of interest when attacking this problem are the following:
(Q1) What dictionaries ensure the existence of a sensing matrix Φ to recover z0 stably from (1)?
(Q2) Given such a dictionary D, how do we find the suitable sensing matrices?
First, we introduce some history on attempts to answer these questions.

1.1

The Basis Case

Most CS literature focuses on the case when D is the canonical basis, i.e., z0 = x0 . A suitable
sensing matrix would mean that Φ is able to extract the low-dimensional information off of z0 .
This is reflected in popular conditions like low coherence, the restricted isometry property, the null
space property and its variations. In this case, the most popular method is ℓ1 -minimization, also
known as the Basis Pursuit [7, 21], where fD (z) = kzk1 :
b
z = arg min kzk1
z∈Rd

subject to

ky − Φzk2 ≤ ε.

(2)

Proposed by Candes and Tao [8, 9], the restricted isometry property (RIP) is sufficient to recover
sparse signals via (2). A matrix Φ ∈ Rm×d satisfies the RIP with constant 0 ≤ δ < 1 and sparsity
s if
(1 − δ)kxk22 ≤ kΦxk22 ≤ (1 + δ)kxk22

for all s-sparse signals x ∈ Rn . The smallest δs ≥ 0 for which the RIP holds is called the restricted
isometry constant. This condition ensures that distinct sparse vectors have sufficiently far away
measurements, providing explicit recovery guarantees.
While the RIP is a sufficient condition for recovery guarantees via (2), another property known
as the null space property (NSP) is both necessary and sufficient. A sensing matrix Φ ∈ Rm×d
is said to satisfy the null space property of order s if for any index set T with |T | ≤ s and any
x ∈ ker(Φ)\{0}, kxT k1 < kxT C k1 holds. Here xT denotes the vector having the same entries as x
in the indices in T and zero elsewhere. It is known that the successful recovery of sparse vectors
from Basis Pursuit (2) when ε = 0 occurs if and only if the NSP holds [17, 23]. Moreover, it was
shown in [3] that the NSP is necessary and sufficient for the stable recovery via Basis Pursuit.
Other than the characterization of Basis Pursuit, another advantage of this property is that it only
depends on the kernel of Φ, which means that this property is invariant under linear combinations
of measurements (the rows of Φ). By a compactness argument, the NSP of order s is equivalent to
the existence of 0 < γ < 1, such that
kxT k1 < γkxT C k1 , for all x ∈ ker(Φ)\{0}.

(3)

This is the so-called stable null space property.
The answer to (Q2) in the basis case is to use random matrices as the sensing matrix Φ. It
is well-known that such matrices satisfy the RIP with high probability, provided that m is on the
2

order of s log d [8, 33]. Since the NSP is equivalent to stable recovery, it thus follows that the RIP
implies the NSP. However, it is worth mentioning that these two properties are not equivalent and
there is a genuine gap between them [4].
Much more can be said about both the history and the theory of CS in the basis case. For those
interested in learning more, see the book [22] and the survey [20].

1.2

The General Dictionary Case

The general setting z0 = Dx0 where D is an arbitrary full rank d × n matrix is much more
challenging. When d = n, the columns of D form a basis for Rd and it is not hard to see that we
can translate this to the canonical basis case as described before. However, the difficulty occurs
when we assume that n > d so the dictionary D is overcomplete. In this case, z0 has infinitely
many representations in D, including possibly more than one sparse representation. There are many
applications where the signals are seen through such a transformation and the need to understand
when stable recovery is achievable is immense [32, 6, 25, 2, 16, 13, 19, 29].
We note that such an overcomplete dictionary is also often called a finite frame for Rd . The
field of finite frame theory is rich and has proven to be a powerful asset in many modern, real-world
applications. We refer the inquisitive readers to [10, 11] for a more thorough introduction to the
elements of finite frame theory.
Perhaps the most reasonable recovery problem to consider in the dictionary setting, since it is
the natural extension of (2), is the ℓ1 -synthesis method:
b = arg min kxk1
x
b
z = Db
x.

subject to

ky − ΦDxk2 ≤ ε

(4)

We note that defining kzkKD := min{kαk1 : Dα = z} gives the following reformulation of the
ℓ1 -synthesis method (4):
b
z = arg min kzkKD

subject to

b
z = arg min kD∗ zk1

subject to

z∈Rd

ky − Φzk2 ≤ ε.

(5)

Specifically, for any convex set K, the Minkowski functional of K is defined as kvkK := inf{λ > 0 :
λ−1 v ∈ K} so that in the dictionary setting where D = [d1 , · · · , dn ] with KD := conv{±di }N
i=1 ,
we have kzkKD = min{kαk1 : Dα = z} [37].
One way to guarantee the successful recovery of (4) is to require ΦD to have the NSP or the
RIP. Rauhut et al. [32] showed that if Φ ∈ Rm×d is a random matrix satisfying a concentration
inequality with m = O(s log ns ) and D satisfies the RIP, then the matrix ΦD also satisfies the RIP.
Once the composition ΦD satisfies the RIP, the program (4) will stably recover the sparse
representation x0 , and consequently the signal z0 . However, we often only care about the recovery
b to be far away from x0 .
of z0 in this dictionary based sparse problem, in which case we allow x
To approach the problem in this new light, the work in [6] instead proposed the model where
fD (z) = kD∗ zk1 in (1), called the ℓ1 -analysis method:
z∈Fd

ky − Φzk2 ≤ ε.

(6)

They showed that successful recovery via (6) is possible when D is a Parseval frame, i.e. DD∗ = Id
for some constant A > 0, and provided that Φ satisfies a dictionary based RIP.
The ℓ1 -analysis and ℓ1 -synthesis models assume different sparsity to begin with. The analysis
model assumes the sparsity of the analysis coefficient D∗ z, which has applications in imaging where
D can be the finite difference operator, wavelets, shearlets, etc. [27, 26]. The ℓ1 -synthesis model
3

assumes one of the infinitely many coefficients for z in D is sparse, as introduced at the beginning.
This is more inclusive as the analysis coefficient is a particular case where the dual frame is the
analysis operator (z = DD∗ z), see [25] for more details. On the technical side, the synthesis
approach often imposes more challenges due to its setting, and the fact that we do not know which
dual frame of D generates a sparse representation. The work by Chen et al. [13] tackled the
ℓ1 -synthesis problem and aimed to lay a framework for this method. They proposed a dictionary
based NSP for the sensing matrix, D-NSP for short, which we now define.
Definition 1.1. Let D ∈ Rd×n be a dictionary. A matrix Φ ∈ Rm×d is said to satisfy the D-NSP
of order s if for any index set T with |T | ≤ s and any v such that Dv ∈ ker Φ\{0}, there is some
u ∈ ker D so that
kvT + uk1 < kvT c k1 .
The D-NSP is a characterization of exact recovery of dictionary sparse signals via (4) when
ε = 0, therefore is a generalization of the NSP. The following result is important to shape up the
direction of this paper.
Theorem 1.2 ([13, Theorem 7.2]). If D is full spark, then Φ has the D-NSP with sparsity s if
and only if ΦD has the NSP with the same sparsity.
A frame D ∈ Rd×n is full spark if every collection of d frame vectors is linearly independent.
Full spark is not a strong assumption on dictionaries. In fact, it is quite obvious that if we randomly
choose the entries of D according to any continuous distribution, then D will be full spark with
probability one. More details can be found in [1].
As a (surprising) result of Theorem 1.2, if the ℓ1 -synthesis method is successful at all, almost
always, we will recover both x0 and z0 , and D will satisfy the NSP since ker(D) ⊂ ker(ΦD). In
other words, if we are using ℓ1 -synthesis to recover z0 , then it is very reasonable to assume that
D has NSP and the coefficients x0 will be recovered simultaneously. Therefore we will study the
properties of the composition ΦD to ensure the success of ℓ1 -synthesis.
Like the basis case, most work for the dictionary case often uses random measurements. The
paper [26] uses Gaussian measurements for the ℓ1 -analysis method, providing both nonuniform and
uniform guarantees. The work [18] also considers the ℓ1 -analysis approach, but instead uses Weibull
measurements. As mentioned earlier, the work by Rauhut et al. [32] does analyze the ℓ1 -synthesis
method, however, it requires the dictionary D to have the RIP, which is harsh. We again note
that there is a gap between the RIP and the NSP [4], so we would like to reduce this assumption
on D. Another notable work is by Vershynin [37], which directly measures the recovery error in
expectation.
Theorem 1.3 ([37, Theorem 7.1]). Assume for normalization that all dictionary vectors satisfy
kdi k2 ≤ 1 and z0 = Dx0 . If b
z is a solution from (5) with ε replaced by mε, where Φ is a Gaussian
matrix, then
r
√
s log n
(7)
kx0 k2 + 2πε
Ekb
z − z0 k2 ≤ c
m
However, the term kx0 k2 does not promote sparsity, and therefore will not provide exact reconstruction for s-sparse representations. Hence, we will
explore the behavior of ΦD when rows of Φ are random, given that D has the NSP.
It is also desirable to have similar results for a deterministic Φ, which can be the direction of
future work.
4

1.3

Our Contribution and Organization

The contribution of this paper is two folds. The first main result, Theorem 3.1, states that a certain
property of an operator/dictionary can be preserved under a subgaussian random map, given that
this map is projecting to a dimension that is on the order of the square of the Gaussian width
of certain set. This could potentially be used to analyze other properties of compressed sensing
matrices, or even beyond the scope of sparse analysis. Our second main result is the application
of Theorem 3.1 to the null space property. Specifically, Theorem 3.3 says that if Φ ∈ Rm×d is a
sensing matrix with independently drawn rows from a subgaussian distribution, D ∈ Rd×n satisfies
the NSP, and the number of measurements m is large enough, then ΦD also satisfies the NSP with
high probability. Consequently, we get a recovery result Corollary 3.8, which is the first recovery
result with subgaussian measurements that only requires the dictionary to be NSP.
The road map is as follows. In Section 2, we provide the required preliminary material and
notations that will be used throughout the paper. In Section 3, we introduce our main result as
described above and describe how it is essentially optimal. Furthermore, we obtain as a corollary
a more suitable recovery guarantee for the ℓ1 -synthesis method. Also, the more specific cases that
Φ has rows drawn independent from a multivariate normal distribution or where the row entries
come from a standard Gaussian vector are given. We then provide the theory behind our results
in Section 4, as well as alternative estimates for the Gaussian width. Finally, we end with Section
5, wherein we provide better estimates in the case that Φ is made up of Gaussian vectors.

2

Preliminaries

We use k · kp for the standard ℓp norm and we let Spn−1 := {x ∈ Rn : kxkp = 1}. We also denote
[n] := {1, · · · , n}. If S ⊂ Rn and D ∈ Rd×n is a dictionary, then we write DS for DS = {Dx : x ∈
S}. Also, we denote the columns of D by di so that D = [d1 , · · · , dn ].
The stable NSP as defined in (3) is a matrix property, however, we will abuse the notation and
say a vector x has the stable NSP if kxT k1 < γkxT C k1 for any index set T with cardinality at most
s. Since we will use it multiple times, we let Sγ be the set of vectors on the unit ball that do not
have the stable NSP. Explicitly,
Sγ := {x : kxT k1 ≥ γkxT c k1 for some |T | ≤ s} ∩ S2n−1 .

(8)

Taking the intersection with the unit ball in the definition of Sγ is mainly for convenience because
then D having the stable NSP is equivalent to a positive lower bound of kDxk2 on the set that
violates the stable NSP. In summary, D having the NSP is equivalent to the existence of γ > 0 and
η > 0 such that
inf {kDxk2 : x ∈ Sγ } ≥ η.
(9)

We will use the notation x ∼ N (µ, σ 2 ) to mean that a one dimensional random variable x
follows a normal distribution with mean µ and variance σ 2 . On the other hand, X ∼ N (µ, Σ) will
mean that a multidimensional random variable X follows a multivariate normal distribution with
mean vector µ and covariance matrix Σ.

2.1

The Gaussian Width

In the proof of our main result, we will need to bound w(DSγ ), where w denotes the Gaussian
width defined as follows.

5

Definition 2.1. The Gaussian width of a set S ⊂ Rn is defined as
w(S) := E suphg, xi,
x∈S

where g ∼ N (0, In ) is a standard Gaussian random vector.
The Gaussian width plays a central role in asymptotic convex geometry. In particular, thinking
of each inner product hg, xi as a random projection, the Gaussian width measures how well, on
average, the vectors in S can line up with a randomly chosen direction. It is in this way that the
Gaussian width can be thought of as a way to measure the “size” of a set [38]. In terms of CS,
bounding the Gaussian width is how one obtains the important concentration equality used in the
now standard CS proofs [22, Chapter 9]. Therefore, it is natural that our proof techniques will
make use of it as well. Lastly, we note that it is often required that the set S be symmetric about
the origin, which Sγ satisfies.
We will need the following result. The argument is given on Page 10 of [31], but we will provide
it in Section 4.3 for the sake of completeness.
Lemma 2.2. For any map F ∈ Rd×n and any S ⊂ Rn , we have
w(FS) ≤ kFk2 w(S).
Furthermore, if inf {kFxk2 : x ∈ S} ≥ η for some constant η > 0, then
w(FS) ≥ η.

2.2

Subgaussian Vectors

The measurement matrix Φ ∈ Rm×d in our result will have rows drawn i.i.d. from a subgaussian
distribution, which we now define.
Definition 2.3. A random vector ϕ ∈ Rd is called a subgaussian vector with parameters (α, σ) if
it satisfies the following.
(1) It is centered, that is, E[ϕ] = 0.
(2) There exists a positive α such that E [|hϕ, zi|] ≥ α for every z ∈ Sd−1
2 .
(3) There exists a positive σ such that Pr (|hϕ, zi| ≥ t) ≤ 2 exp(−t2 /(2σ 2 )) for every z ∈ Sd−1
2 .
There are many examples of subgaussian vectors, but we only introduce two of the most common
ones, which will appear in our results.
Example 2.4 (Standard Gaussian vector). Let ϕ ∈ Rd ∼ N (0, Id ) be a standard Gaussian vector.
If z ∈ Sd−1
2 , then Z := hϕ, zi ∼ N (0, 1) and it is well known that
r
 2
t
2
and
Pr (|Z| ≥ t) ≤ exp −
,
E[|Z|] =
π
2
p
so the standard Gaussian vector is subgaussian with parameters α = 2/π and σ = 1.

6

Example 2.5 (Nonstandard Gaussian vector). Suppose that ϕ ∈ Rd ∼ N (0, Σ) where the co2
2 , respectively. Then
variance matrix Σ has smallest and largest singular values, σmin
and σmax
d−1
−1/2
ψ := Σ
ϕ ∼ N (0, Id ) and we can compute for all z ∈ S2 that
+#
"*
r
h
i
h
i
2
Σ1/2 z
1/2
1/2
1/2
≥ σmin
E [|hϕ, zi|] = E |hΣ ψ, zi| = E |hψ, Σ zi| = kΣ zk2 E
ψ,
1/2
π
kΣ zk
and in a similar fashion
Pr [|hϕ, zi| ≥ t] = Pr

"*

Σ1/2 z
ψ,
kΣ1/2 zk

+

so that ϕ is subgaussian with parameters α = σmin

2.3

The Mean Empirical Width

≥
p

t
kΣ1/2 zk2

#



t2
≤ exp − 2
2σmax



,

2/π and σ = σmax .

n
If {fi }m
i=1 are independent copies of the random distribution f ∈ R , then we can define the mean
n
empirical width of a set S ⊂ R as



m
1 X
εi fi ,
Wm (S; f ) := E sup x, √
m
x∈S
i=1

where {εi }m
i=1 are independent random variables taking values uniformly over {±1} and are independent from everything else. This quantity appears in the Mendelson’s small ball method (Theorem
4.1), which is a major tool that we use.
The mean empirical width Wm (S; f ) is a distribution-dependent measure of the size of the set
S. Estimation of Wm (S; f ) for any subgaussian vector f is made in [36], where S is required to be
S2n−1 ∪K for some cone K. However, the bound can be relaxed to any subset S by the observation of
the generic chaining bound and the majorizing measure theorem [34, Theorem 2.2.18 and Theorem
2.4.1]. We will state this as a lemma.
Lemma 2.6. If f ∈ Rn is a subgaussian vector with parameters (α, σ), then for any set S ⊂ Rn
we have
Wm (S; f ) ≤ Cσw(S)
(10)
for some universal constant C.
This constant C will appear in our main theorems.
Remark 2.7. When f follows a centered multivariate
normal distribution N (0, Σ), we can take
Pm
−1/2
C = 1. Let gi := Σ
fi ∼ N (0, In ), then g = i=1 εi gi ∼ N (0, In ) as well, so




m
m
1 X
1 X
1/2
εi fi = E sup z, √
εi Σ gi
Wm (S; f ) = E sup z, √
m
m
z∈S
z∈S
i=1
i=1


m
1 X
1/2
εi gi = E sup hx, gi
= E sup Σ z, √
m
z∈S
x∈Σ1/2 S
i=1

= w(Σ

1/2

S) ≤ σmax w(S),

where the last inequality is due to Lemma 2.2.
7

3
3.1

Main Results
Preservability Under Subgaussian Maps

Theorem 3.1 (Preservability under random maps). Let D ∈ Rd×n be arbitrary, let S ⊂ Rn be such
that inf {kDxk2 : x ∈ S} ≥ η for some constant η > 0, and assume ϕ ∈ Rd is a subgaussian vector
with parameters (α, σ). If Φ ∈ Rm×d is a measurement matrix with rows that are independent
copies of ϕ⊤ so that the number of measurements satisfies
m≥
then with probability at least

48 σ 6 2 2
C w (DS),
η 2 α6


α4
1 − exp −m 2 4
64 σ



,

we have
inf kΦDxk2 ≥ Cσw(DS).

x∈S

(11)

Theorem 3.1 is beyond the null space property. It says that if an operator stays bounded away
from 0 on some set, then this operator under a random map also stays bounded away from 0 on
the same set, given that the dimension of the random map is at least proportional to the square of
the Gaussian width of a related set. This could be potentially useful for other dimension reduction
analysis. The proof of Theorem 3.1 can be found in Section 4.1.
Remark 3.2. Theorem 3.1 can be compared to [5, Proposition 18]. Both their statement and ours
are about the minimal number of measurements related to Gaussian width. However, ours has a
dictionary D incorporated.
As an application of Theorem 3.1, we let S = Sγ , and compute the Gaussian width of DSγ in
Section 4.2. See Theorem 4.8. Recall that Sγ is the set of vectors that violates the stable NSP.
This implies the following theorem on preserving the null space property.
Theorem 3.3. Assume Φ ∈ Rm×d is a sensing matrix comprised of rows drawn i.i.d. from
a subgaussian distribution with parameters (α, σ). Take D ∈ Rd×n to be a dictionary satisfyingthe stable NSP of order s with inf {kDxk2 : x ∈ Sγ } ≥ η for some η > 0 and satisfying
max kdi k22 : i ∈ [n] ≤ ρ. If the number of measurements satisfies
m≥
then with probability at least

18 · 48 σ 6 ρ 2
C s log(2n),
η 2 α6 γ 2


α4
1 − exp −m 2 4
64 σ



,

the composition ΦD also has the stable NSP of order s with inf {kΦDxk2 : x ∈ Sγ } ≥ Cση.
Remark 3.4. Theorem 3.3 is optimal in the sense that we require a minimal condition on D. If
ΦD has the NSP, then D must also have the NSP (hence some kind of stable NSP) since ker(D)
is a proper subspace of ker(ΦD). Thus, D having the NSP is a a very reasonable condition if we
want stable recovery through ℓ1 -synthesis.

8

The Gaussian distributions are important special cases of subgaussian distributions, so we list
two corollaries of Theorem 3.3 below, using the estimates in Example 2.5 and 2.4, as well as Remark
2 /σ 2
2.7. In Corollary 3.5, κ := σmax
min is the condition number of Σ.
Corollary 3.5. Suppose Φ ∈ Rm×d is a sensing matrix with rows drawn i.i.d. from a Gaussian
distribution N (0, Σ) in which the covariance matrix Σ has condition number κ, and suppose D ∈
Rd×n has the stable NSP of order s with inf {kDxk2 : x ∈ Sγ } ≥ η for some η > 0 and satisfies
max kdi k22 : i ∈ [n] ≤ ρ. If the the number of measurements satisfies
m≥
then with probability at least

18 · 213 π 3 ρκ3
s log(2n),
η2
γ2


κ2
1 − exp −m 5 2
4 π



,

the composition ΦD also has the stable NSP of order s with inf {kΦDxk2 : x ∈ Sγ } ≥ σmax η.
Corollary 3.6. Suppose Φ ∈ Rm×d is a sensing matrix with rows drawn i.i.d. from a standard Gaussian distribution N (0, Id ), and suppose D ∈ Rd×n
 has the stable NSP of order s with
inf {kDxk2 : x ∈ Sγ } ≥ η for some η > 0 and satisfies max kdi k22 : i ∈ [n] ≤ ρ. If the the number
of measurements satisfies
18 · 213 π 3 ρ
m≥
s log(2n),
η2
γ2
then with probability at least



1
1 − exp −m 5 2
4 π



,

the composition ΦD also has the stable NSP of order s with inf {kΦDxk2 : x ∈ Sγ } ≥ η.
Remark 3.7. Better estimates than those given in Corollary 3.5 can be made using estimates
specific to Gaussian distributions. See Theorem 5.1.

3.2

Sparse Recovery via the ℓ1 -synthesis Method

The stable NSP in the form of inf {kDxk2 : x ∈ Sγ } ≥ η > 0 is similar to the robust NSP introduced
in [18], since it resembles the recovery result by the robust NSP in the basis case. In Section 4.4,
we state the theorem in the basis case and its proof because we could not find this formulation in
the literature.
As a result of Theorem 3.3, we can get a uniform recovery result using Theorem 4.12 where
we replace A by ΦD. The notation σs (x) denotes the ℓ1 -error of best s-term approximation to a
vector x, defined by
σs (x) := inf{kx − vk : v is s-sparse}.
Note that the infimum is achieved by taking v := xT , where T is the index set containing the
indices where the s-largest absolute value entries of x occur.
Corollary 3.8. Suppose Φ ∈ Rm×d is a sensing matrix comprised of rows drawn i.i.d. from
a subgaussian distribution with parameters (α, σ) and suppose D ∈ Rd×n
 has2 the stable NSP of
order s with inf {kDxk2 : x ∈ Sγ } ≥ η for some η > 0 and satisfies max kdi k2 : i ∈ [n] ≤ ρ. Let
9

z0 = Dx0 , and the measurements y satisfying ky − Φz0 k2 ≤ ε. If the number of measurements
satisfies
18 · 48 σ 6 ρ 2
C s log(2n),
m≥
η 2 α6 γ 2


α4
then with probability at least 1 − exp −m 2 4 , the ℓ1 -synthesis method (4) provides a stable
64 σ
recovery for both the coefficients x0 and the signal z0 as
2γ + 2
2ε
σs (x0 ) +
1−γ
Cση
2γ + 2
2εkDk2
kb
z − z0 k2 ≤ kDk2
σs (x0 ) +
.
1−γ
Cση
kb
x − x0 k2 ≤

Remark 3.9. This corollary is a probabilistic statement whereas Theorem 1.3 is stated in terms of
mean squared error. Moreover, the term kx0 k2 in (7) does not promote sparsity, and therefore will
not provide exact reconstruction for s-sparse representations. This makes sense since no condition
is imposed on D in Theorem 1.3. Overall, the recovery result Corollary 3.8 imposes minimal
conditions on D, and as far as the authors can tell, is first of its kind.

4

Proofs of the Results

We will apply Mendelson’s Small Ball Method in our setting. Most of the work will be in properly
estimating two important quantities, which will further lead to the need to estimate the Gaussian
width w(DSγ ). This is what makes up Sections 4.1 and 4.2. In doing so, we will obtain the bound
on the number of measurements in Theorem 3.3 and its corollaries that forces ΦD to have the NSP
with high probability given that Φ is a matrix made up of independent copies of a subgaussian
vector and D satisfies the NSP. In Section 4.3 we prove Lemma 2.2 and use it to obtain a different
estimate for the Gaussian width than in Section 4.2. Lastly, in Section 4.4, we provide a stable
recovery result with stable NSP for completeness.

4.1

Preservability Under a Random Map

A major component of our proof is the application of the following theorem, coined as Mendelson’s
Small Ball Method by J. Tropp [36] and originally stated in [28].
Theorem 4.1 ([36, Proposition 5.1], cf. [28, Theorem 2.1]). Fix a set S ⊂ Rn . Let f be a random
⊤
vector in Rn and let F ∈ Rm×n have rows {fi⊤ }M
i=1 that are independent copies of f . Define


Qξ (S; f ) := inf Pr |hx, f i| ≥ ξ
x∈S

and



m
1 X
εi fi ,
Wm (S; f ) := E sup x, √
m
x∈S
i=1

where {εi }m
i=1 are independent random variables taking values uniformly over {±1} and are independent from everything else. Then for any ξ > 0 and t > 0, we have
√
(12)
inf kFxk2 ≥ ξ mQ2ξ (S; f ) − 2Wm (S; f ) − ξt
x∈S

2 /2

with probability ≥ 1 − e−t

.

10

Notice that if rows of Φ are independent copies of a random vector ϕ, then rows of ΦD are
independent copies of the random vector D⊤ ϕ. We will apply Theorem 4.1 with ΦD in place of F
and the random vector D⊤ ϕ in place of f , which in turn will require us to estimate the quantities
Q2ξ (S; D⊤ ϕ) and Wm (S; D⊤ ϕ).
In the proof of Theorem 4.3, we will use the following lemma to bound Q2ξ (S; D⊤ ϕ). The
proof is in [36, Section 6.5].
Lemma 4.2. If f ∈ Rn is a subgaussian vector with parameters (α, σ), then
Pr [|hz, f i| ≥ t] ≥

(α − t)2
4σ 2

for any 0 < t < α and z ∈ S2n−1 .
Theorem 4.3. Let D ∈ Rd×n be arbitrary, let S ⊂ Rn be so that inf {kDxk2 : x ∈ S} ≥ η for some
constant η > 0, and let ϕ ∈ Rd be a subgaussian measurement with parameter (α, σ). If Φ ∈ Rm×d
has rows that are independent copies of ϕ⊤ , then
αη
αη  α 2 √
m − 2Cσw(DS) −
inf kΦDxk2 ≥ 3
t
(13)
x∈S
4
σ
4
2 /2

for any t > 0 with probability at least 1 − e−t

.

Proof. We first apply Mendelson’s Small Ball Method, Theorem 4.1, with F replaced by ΦD and
therefore f replaced by D⊤ ϕ to obtain the bound
√
(14)
inf kΦDxk2 ≥ ξ mQ2ξ (S; D⊤ ϕ) − 2Wm (S; D⊤ ϕ) − ξt.
x∈S

By Lemma 4.2, provided we choose ξ to satisfy 2ξ/η < α, we obtain for any x ∈ S






Dx
ξ
ξ
Dx
(α − 2ξ/η)2
Pr (|hDx, ϕi| ≥ 2ξ) = Pr
,ϕ ≥
,ϕ ≥
≥ Pr
≥
kDxk2
kDxk2
kDxk2
η
4σ 2
and therefore


(α − 2ξ/η)2
Q2ξ (S; D⊤ ϕ) = inf Pr |hx, D⊤ ϕi| ≥ 2ξ = inf Pr (|hDx, ϕi| ≥ 2ξ) ≥
.
x∈S
x∈S
4σ 2

Lemma 2.6 readily gives the estimate

Wm (S; D⊤ ϕ) = Wm (DS; ϕ) ≤ Cσw(DS).
Placing these two bounds into (14) and choosing ξ to satisfy 2ξ/η = α/2 gives the bound in (13).
Remark 4.4. Notice that Theorem 4.3 is a generalization of [36, Theorem 6.3].
Finally, we can provide the proof of Theorem 3.1.
Proof of Theorem 3.1. Theorem 4.3 implies that
αη
αη  α 2 √
αη
m − 2Cσw(DS) −
inf kΦDxk2 ≥ 3
t := a − b −
t.
x∈S
4
σ
4
4

Picking m and t to satisfy a ≥ 2b and (αη/4)t = (a − b)/2 gives

inf kΦDxk2 ≥ a − b − (a − b)/2 = (a − b)/2 ≥ b/2 = Cσw(DS).

x∈S

11

All that is left is to rewrite these conditions in terms of m and t. We have
48 σ 6 2 2
αη  α 2 √
m
≥
4Cσw(DS)
⇔
m
≥
a ≥ 2b ⇔
C w (DS)
43 σ
η 2 α6

and

a−b
a
αη  α 2 √
αη
m
t=
≥ = 4
4
2
4
4
σ

⇔

t≥

proving the result.

1 √  α 2
m
64
σ

⇔

−

t2
α4
≤ −m 2 4 ,
2
64 σ

The last ingredient of the proof of Theorem 3.3 is to estimate the Gaussian width w(DSγ ),
since the infimum in (13) being bounded away from zero will imply that ΦD has the stable NSP.
This will require a bit of work and is done in the next subsection.

4.2

Estimating the Gaussian Width

It remains to suitably bound the Gaussian width of DSγ , which we recall is defined by
w(DSγ ) := E sup hg, zi = E sup hD⊤ g, xi,
z∈DSγ

(15)

x∈Sγ

where g ∈ Rd is a standard Gaussian vector. We will alter the proof in [22, Chapter 9] to fit our
needs. First, we introduce the convex cone
(
)
s
n
X
X
Kγ,s := u ∈ Rn : uℓ ≥ 0, ℓ ∈ [n],
uℓ ≥ γ
uℓ
ℓ=1

ℓ=s+1

and its dual cone
∗
Kγ,s
:= {z ∈ Rn : hz, ui ≥ 0 for all u ∈ Kγ,s } .

Also, recall the nonincreasing rearrangement of a vector x ∈ Rd is the vector x∗ ∈ Rd for which
x∗1 ≥ x∗2 ≥ · · · ≥ x∗d
and x∗i = xπ(i) for some permutation π.
We can now state the following lemma. It has a proof that is similar to that of [22, Proposition
9.31], but we provide it for the sake of completeness.
Lemma 4.5. If D ∈ Rd×n is an arbitrary matrix and g ∈ Rd ∼ N (0, Id ), then
w(DSγ ) ≤ E min∗ k(D⊤ g)∗ + zk2 .
z∈Kγ,s

Proof. Elements in Sγ are invariant under permutation of indices and entrywise sign changes, so
w(DSγ ) = maxhD⊤ g, xi = maxh(D⊤ g)∗ , xi =
x∈Sγ

x∈Sγ

max

u∈Kγ,s ∩SN−1

h(D⊤ g)∗ , ui ≤ min∗ k(D⊤ g)∗ + zk2 ,
z∈Kγ,s

where the last inequality follows by the duality
max

h−g, xi ≤ min∗ kg − zk2 ,

x∈K,kxk2 ≤1

z∈K

as given in [22, (B.39)].
12

(16)

The following Lemma is similar to that given in [22, Remark 9.25], but here we assume a general
variance rather than one.
Lemma 4.6. If a ∼ N (0, σ 2 ), then
ESt2 (a)

≤σ

4

r

2 −2 −t2 /(2σ2 )
t e
,
πe

where St is the soft thresholding operator defined by

 u − t if u > t
St (u) :=
0
if |u| ≤ t .

u + t if u < −t

Proof. We compute

Z ∞
2
2
2
St2 (u)e−u /(2σ ) du
ESt2 (a) = √
2
2πσ 0
r Z ∞
1 2
2
2
(u − t)2 e−u /(2σ ) du
=
σ π t
r Z
1 2 ∞ 2 −(v+t)2 /(2σ2 )
=
v e
dv
σ π 0
r Z
2 ∞ 2 −v2 /(2σ2 ) −vt/σ2
−t2 /(2σ2 ) 1
v e
e
dv
=e
σ π 0
r Z 
2 ∞ v −(v/σ)2 /2  −vt/σ2
−t2 /(2σ2 )
ve
dv
=e
e
π 0
σ
r
Z
2 −1/2 ∞ −vt/σ2
−t2 /(2σ2 )
≤e
e
dv
ve
π
0
r
2 −1/2 σ 4
−t2 /(2σ2 )
=e
e
π
t2
r
2 −2 −t2 /(2σ2 )
t e
= σ4
πe
as desired.
Lastly, we need the following bound on the expectation of the elementwise maximum of D⊤ g.

Lemma 4.7. If D ∈ Rd×n is any matrix with max kdi k22 : i ∈ [n] ≤ ρ and g ∈ Rd ∼ N (0, Id ),
then


p
⊤
E max |(D g)i | ≤ 2ρ log(2n)
i

13

Proof. Setting ai := (D⊤ g)i gives ai ∼ N (0, σi2 ) with σi = kdi k2 , and thus for any fixed t ≥ 0
Z
2
2
1
q
e−x /2σi et|x| dx
E exp(t|ai |) =
R
2πσi2
Z ∞
1
2 2
2 2
2
q
=2
e−(x−σi t) /2σi eσi t /2 dx
0
2πσi2
Z ∞
2 2
1
2 2
2
q
≤ 2eσi t /2
e−(x−σi t) /2σi dx
−∞
2πσi2


kdi k2 t2
= 2 exp
2

Since the exponential function is convex, it follows from Jensen’s inequality that






 2
n
n
X
X
kdi k2 t2
ρt
2 exp
exp (t|ai |) ≤
exp t E max |ai | ≤ E exp t max |ai | ≤ E
≤ 2n exp
i
i
2
2
i=1

i=1

whence




log(2n)
+ tρ/2.
E max |ai | ≤
i
t

p
p
2 log(2n)/ρ gives the desired bound E (maxi |ai |) ≤ 2ρ log(2n).

Theorem 4.8. If D ∈ Rd×n is any matrix with max kdi k22 : i ∈ [n] ≤ ρ, then
p
w(DSγ ) ≤ γ −1 18sρ log(2n).

Picking t =

Proof. Define

Fγ,s :=

[

t≥0

{z ∈ Rn : zℓ = t, ℓ ∈ [s], zk ≥ −γt, k = s + 1, . . . , n}

Ks∗

which satisfies Fγ,s ⊂
by Lemma 9.32 of [22]. The minimum over a smaller set can only be
larger so we obtain w(DSγ ) ≤ E min k(D⊤ g)∗ + zk2 by Lemma 4.5. By the definition of Fγ,s and
z∈Fγ,s

concavity of the square root function, we get
w(DSγ ) ≤ E min k(D⊤ g)∗ + zk2
z∈Fγ,s

v
v
u s
u X
n
uX
u
t ((D⊤ g)∗ + t)2 + t
((D⊤ g)∗ℓ + zℓ )2 
≤E
min
ℓ
t≥0

zℓ ≥−γt,ℓ∈[n]\[s]

ℓ=1

ℓ=s+1

Now fix t ≥ 0 to be chosen later. Again by concavity, and since (D⊤ g)∗ℓ has mean zero we obtain
v
v
u s
u
n
X
uX
u
∗
⊤
2
t
w(DSγ ) ≤ E
((D⊤ g)∗ℓ + zℓ )2
(17)
((D g)ℓ + t) + Et min
ℓ=1

zℓ ≥−t

ℓ=s+1

v
v
u s
u
n
q
X
uX
u
√
∗
⊤
2
⊤
t
((D⊤ g)∗ℓ + zℓ )2
≤E
((D g)ℓ ) + 2t E(D g)ℓ + t s + Et min
zℓ ≥−t

ℓ=1

v
v
u s
u X
uX
u n
√
∗
2 ((D⊤ g)∗ ),
⊤
2
t
≤E
((D g)ℓ ) + t s + Et
Sγt
ℓ
ℓ=1

ℓ=s+1

14

(18)

ℓ=s+1

(19)

where St is the soft thresholding operator defined earlier. Note that Inequality (19) holds because
of how the zl are defined.
By Lemma 4.7, the first term in (19) can be estimated by
v
u s


p
uX
√
≤ 2ρs log(2n).
Et ((D⊤ g)∗ℓ ))2 ≤ s · E max D⊤ g
1≤i≤n

ℓ=1

i

Next, we bound the last term in (19) by
v
v
v
u X
u X
u X
n
n
n
u
u
u
2
∗
2
∗
2 ((D⊤ g) ),
⊤
⊤
t
t
t
Sγt ((D g)ℓ ) ≤ E
E
Sγt ((D g)ℓ ) ≤ E
Sγt
ℓ
ℓ=s+1

ℓ=s+1

ℓ=s+1

where we used the fact that {(D⊤ g)∗ℓ : ℓ = s + 1, · · · , n} are the n − s smallest entries in magnitude
to obtain the second inequality.
To estimate the second moment of the soft thresholding operator, we again use the fact that
ai := (D⊤ g)i gives ai ∼ N (0, σi2 ) with σi = kdi k2 and so Lemma 4.6 implies
r
r




−(γt)2
−(γt)2
2
2
−2
−2
2
2
4
(γt) exp
(γt) exp
≤ρ
ESγt (ai ) ≤ σi
πe
πe
2ρ
2σi2
Finally, combining the all of these estimates of the quantities in (19) gives
s
r


p
√
−(γt)2
2
2
−2
w(DSγ ) ≤ 2ρs log(2n) + t s + (n − s)ρ
(γt) exp
.
πe
2ρ

yielding γ −1

4.3

p

2ρ log(2n) and using the fact that γ −1 ≥ 1 gives
s
p
p
1
n−s 1
√
w(DSγ ) ≤ 2ρs log(2n) + γ −1 2sρ log(2n) + ρ
2n
2πe log(2n)


p
1
≤ 2sρ log(2n) 1 + γ −1 +
√
1/4
(8πe)
s log(2n)
p
−1
≤ 3γ
2sρ log(2n)

Choosing t = γ −1

p

18sρ log(2n) as sought.

Remarks on Gaussian Width

Recall that a Gaussian process {Xt }t∈T for some index set T (which can be uncountably infinite)
is a sequence of random variables Xt so that any finite linear combination follows a Gaussian
distribution. Slepian’s lemma [24] gives a way to compare such processes.
Lemma 4.9 (Slepian’s Lemma). If {Xt }t∈T and {Xt }t∈T are Gaussian processes so that for any
s, t ∈ T
E|Xs − Xt |2 ≤ E|Ys − Yt |2 ,
then
E sup Xt ≤ E sup Yt .
t∈T

t∈T

15

Proof of Lemma 2.2. We define the Gaussian processes {Xu }u∈S and {Yu }u∈S


Fu
,g
and Yu := kFk2 hu, gi,
Xu := hFu, gi = kFuk2
kFuk2
where g ∼ N (0, Id ). We notice
E |Xu − Xv |2 = kF(u − v)k22 ≤ kFk22 ku − vk22 = E |Yu − Yv |2 .
Thus, Lemma 4.9 gives
w(FS) = E sup Xu ≤ E sup Yu = kFk2 w(S).
u∈S

u∈S

Furthermore, if inf {kFxk2 : x ∈ S} ≥ η for some constant η > 0, then for any x0 ∈ S
w(FS) = E suphFx, gi
x∈S


Fx
= E sup kFxk2
,g
kFxk2
x∈S


Fx0
≥ ηE
,g
kFx0 k2
=η

as desired.
We can also provide a different estimate for the Gaussian width in light of Lemma 2.2. We
instead consider vectors that do not satisfy the stable NSP on the ℓ1 ball rather than the ℓ2 ball,
Sγ1 := {x : kxT k1 ≥ γkxT c k1 for some |T | ≤ s} ∩ S1n−1 .
Proposition 4.10. If D ∈ Rd×n is any matrix, then
w(DSγ1 ) ≤ 2kDk2

p

(20)

2 log n.

Proof. First, notice that w(DSγ1 ) = w(conv(DSγ1 )) = w(D conv(Sγ1 )) = w(DB1 ), where conv(S)
denotes the convex hull of S and B1 := {x : kxk1 ≤ 1}. The Gaussian width of the ℓ1 ball is well
known. For example,
p
w(B1 ) = E sup hx, gi = Ekgk∞ ≤ 2 2 log n.
x∈B1

√
Combining this estimate with Lemma 2.2 gives w(DSγ1 ) ≤ 2kDk2 2 log n as desired.

Remark 4.11. By defining η1 := min kDxk2 : x ∈ Sγ1 , we can rewrite the bound on in m in
Theorem 3.3 as
49 σ 6
m ≥ 2 6 CkDk2 log n
η1 α
using exactly the same proof techniques as in Theorem 3.1, then applying Proposition 4.10.

16

4.4

Sparse recovery with Stable NSP

Theorem 4.12. If a sensing matrix A ∈ Rm×n satisfies the stable NSP of order s with
inf {kAvk2 : v ∈ Sγ } ≥ η

for some η > 0,

then given y = Ax + e with kek2 ≤ ε, we have
kb
x − xk2 ≤

2ε
2γ + 2
σs (x) + ,
1−γ
η

(21)

where
b = arg min kzk1
x
z∈Rd

subject to

ky − Azk2 ≤ ε.

b − x and T be the support of the biggest s entries of x in magnitude. Then by a
Proof. Let h := x
standard compressed sensing argument, we have
where σs (x) = kx − xT k1 .
If h/khk2 ∈ Sγ , then

khT C k1 ≤ khT k1 + 2σs (x),

(22)

ηkhk2 ≤ kAhk2 ≤ 2ε.

(23)

On the other hand, if h/khk2 ∈
/ Sγ , then the vector h itself has the stable NSP and therefore
khT k1 < γkhT C k1 . Combined with (22), we have
khT k1 ≤

2γ
σs (x).
1−γ

(24)

The equations (22), (24), and the fact that khk1 = khT k1 + khT C k1 , we get
khk2 ≤ khk1 ≤

2γ + 2
σs (x).
1−γ

(25)

Combining the two cases (23) and (25), we get the desired result (21).

5

Better Estimates For Corollary 3.5

The following theorem is an improvement on Corollary 3.5 in terms of the condition number κ. The
techniques are the same ones used in proving Theorem 3.3, but for the Gaussian distribution we
can improve Lemma 4.2 and hence improve the estimate on the marginal tail Qξ . See (26) below.
Theorem 5.1. Suppose Φ ∈ Rm×d is a sensing matrix with rows drawn i.i.d. from a Gaussian distribution N (0, Σ) in which the covariance matrix Σ has condition number κ, and suppose
D ∈ Rd×n has the NSP of order s with inf {kDxk2 : x ∈ Sγ } ≥ η for some η > 0 and satisfies
max kdi k22 : i ∈ [n] ≤ ρ. If the the number of measurements satisfies
m≥

then with probability at least

18 · 29 πe ρκ
s log(2n),
η2
γ2


1 − exp −m

the composition ΦD also has the NSP of order s.

17

1
128eπ



,

Proof. Let ϕ ∈ Rd ∼ N (0, Σ) be the vector that generates Φ. The random vector ϕ has the same
distribution as Σ1/2 g, where g ∼ N (0, Id ). Therefore,
hDx, ϕi = hDx, Σ

1/2

gi = hΣ

1/2

Dx, gi = kΣ

1/2

Dxk2



Σ1/2 Dx
,g
kΣ1/2 Dxk2



= kΣ1/2 Dxk2 Z

where Z ∼ N (0, 1). Therefore, we obtain
Q2ξ (Sγ ; D⊤ ϕ) = inf Pr (|hDx, ϕi| ≥ 2ξ)
x∈Sγ

!
2ξ
= inf Pr |Z| ≥
x∈Sγ
Σ1/2 Dx 2


2ξ
≥ Pr |Z| ≥
ησmin


1
2ξ 2
ησmin
· √ exp − 2 2
≥
4ξ
η σmin
2π

(26)

where we used the well-known lower bound
Pr(Z > t) ≥

1 1 −t2 /2
√ e
,
2t 2π

for any t ≥ 1

with the assumption that 2ξ/(ησmin ) ≥ 1. We also have
Wm (Sγ ; D⊤ ϕ) = Wm (DSγ ; D⊤ ϕ) ≤ σmax w(DSγ )
by Remark 2.7. Theorem 4.1 hence implies that
√
inf kΦDxk2 ≥ ξ mQ2ξ (Sγ ; D⊤ ϕ) − 2Wm (Sγ ; D⊤ ϕ) − ξt
x∈Sγ


√ ησmin
2ξ 2
− 2σmax w(DSγ ) − ξt
≥ m √ exp − 2 2
η σmin
4 2π
=: a − b − ξt

2 /2

with probability ≥ 1 − e−t

. Picking m, ξ, t such that a ≥ 2b and ξt = (a − b)/2 gives

inf kΦDxk2 ≥ a − b − (a − b)/2 = (a − b)/2 ≥ b/2 > 0,

x∈S

guaranteeing the null space property of ΦD.
Lastly, we rewrite these conditions choosing 2ξ = ησmin and invoke Theorem 4.8 to get
a ≥ 2b

⇔

√ ησmin −1/2
m √ e
≥ 4σmax w(DSγ )
4 2π

⇔

m≥

18 · 29 πe ρκ
s log(2n)
η2
γ2

and
a−b
a √ ησmin
ησmin
t=
≥ = m √ e−1/2
2
2
4
16 2π

⇔

as desired.

18

√
m
t≥ √
8 2πe

⇔

−

t2
1
≤ −m
2
128πe

Acknowledgements
We would like to thank Eric Pinkham for taking part in our discussions to help move the paper
along. We would also like to acknowledge the gracious grant support we received: ARO W911NF16-1-0008; NSF ATD 1321779; NSF DMS 1307685; and NSF DMS 1725455.

References
[1] B. Alexeev, J. Cahill, and D. G. Mixon. Full spark frames. J. Fourier Anal. Appl. 18 (2012),
no. 6: 1167–1194.
[2] A. Aldroubi, X. Chen, and A. Powell. Perturbations of measurement matrices and dictionaries in compressed sensing. Appl. Comput. Harmon. Anal. 33 (2012), no. 2: 282–291.
[3] A. Aldroubi, X. Chen, and A. Powell. Stability and robustness of ℓq minimization using null
space property. Proceedings of SampTA 2011 (2011).
[4] J. Cahill, X. Chen, and R. Wang. The gap between the null space property and the restricted
isometry property. Linear Algebra and its Applications 501 (2016): 363–375.
[5] J. Cahill and D. G. Mixon. Robust width: A characterization of uniformly stable and robust
compressed sensing. arXiv:1408.4409
[6] E. J. Candès, Y. Eldar, D. Needell, and P. Randall. Compressed sensing with coherent and
redundant dictionaries. Appl. Comput. Harmon. Anal. 31 (2011), no. 1: 59–73.
[7] E. J. Candès, J. Romberg, and T. Tao. Stable signal recovery from incomplete and inaccurate
measurements. Comm. Pure Appl. Math. 59 (2006), no. 8: 1207–1223.
[8] E. J. Candès and T. Tao. Decoding by linear programming. IEEE Trans. Inform. Theory 51
(2005), no. 12: 4203–4215.
[9] E. J. Candès and T. Tao. Near optimal signal recovery from random projections: universal
encoding strategies? IEEE Trans. Inform. Theory 52 (2006), no. 12: 5406–5425.
[10] P. G. Casazza and G. Kutyniok. “Finite frames: Theory and applications.” Springer (2013).
[11] P. G. Casazza and R. G. Lynch. A brief introduction to Hilbert space frame theory and
its applications. Finite frame theory. Proc. Sympos. Appl. Math., 73, AMS Short Course
Lecture Notes, Amer. Math. Soc., Providence, RI, (2016): 1–51.
[12] S. S. Chen, D. L. Donoho, and M. A. Saunders. Atomic decomposition by Basis Pursuit.
SIAM J. Sci. Comput. 20 (1998), no. 1: 33-61. Reprinted in SIAM Rev. 43 (2001), no. 1:
129–159.
[13] X. Chen, H. Wang, and R. Wang. A null space analysis of the ℓ1 -synthesis method in
dictionary-based compressed sensing. Applied and Computational Harmonic Analysis 37
(2014), no. 3: 492–515.
[14] V. Chandrasekaran, B. Recht, P. Parrilo, and A. Willsky. The convex geometry of linear
inverse problems. Found. Comput. Math. 12 (2012), no. 6: 805–849

19

[15] A. Cohen, W. Dahmen, and R. DeVore. Orthogonal Matching Pursuit under the Restricted
Isometry Property. Constr. Approx. 45 (2017), no. 1: 113–127.
[16] M. A. Davenport, D. Needell, and M. B. Wakin. Signal space CoSaMP for sparse recovery
with redundant dictionaries. IEEE Trans. Inform. Theory 59 (2013), no. 10: 6820–6829.
[17] D. Donoho and M. Elad. Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ1 minimization. Proceedings of the National Academy of Sciences 100 (2003),
no. 5: 2197–2202.
[18] S. Foucart. Stability and robustness of ℓ1 -minimizations with Weibull matrices and redundant
dictionaries. Linear Algebra Appl. 441 (2014): 4–21.
[19] S. Foucart. Dictionary-sparse recovery via thresholding-based algorithms. J. Fourier Anal.
Appl. 22 (2016), no. 1: 6–19.
[20] S. Foucart. Flavors of Compressive Sensing. In: Fasshauer G., Schumaker L. (eds) Approximation Theory XV: San Antonio 2016. AT 2016. Springer Proceedings in Mathematics &
Statistics, vol 201. Springer, Cham.
[21] S. Foucart and M. Lai. Sparsest solutions of underdetermined linear systems via ℓq minimization for 0 < q ≤ 1. Appl. Comput. Harmon. Anal. 26 (2009), no. 3: 395-407.
[22] S. Foucart and H. Rauhut. “A mathematical introduction to compressive sensing.” Boston:
Birkhäuser (2013).
[23] R. Gribonval and M. Nielsen, Sparse representations in unions of bases. IEEE Trans. Inform.
Theory 49 (2003), no. 12: 3320–3325.
[24] M. Ledoux and M. Talagrand. “Probability in Banach spaces: isoperimetry and processes.”
Volume 23. Springer (1991).
[25] S. Li, T. Mi, and Y. Liu. Performance analysis of ℓ1 -synthesis with coherent frames. 2012
IEEE International Symposium on Information Theory Proceedings (2012).
[26] M. Kabanava and H. Rauhut. Analysis ℓ1 -recovery with frames and Gaussian measurements.
Acta Appl. Math. 140 (2015): 173–195.
[27] E. J. King, G. Kutyniok, and X. Zhuang. Analysis of inpainting via clustered sparsity and
microlocal analysis” Journal of mathematical imaging and vision 48.2 (2014): 205-234.
[28] V. Koltchinskii and S. Mendelson. Bounding the smallest singular value of a random matrix
without concentration. International Mathematics Research Notices. 2015 (2015), no. 23:
12991–13008.
[29] F. Krahmer, D. Needell and R. Ward. Compressive sensing with redundant dictionaries and
structured measurements. SIAM J. Math. Anal. 47 (2015), no. 6: 4606–4629.
[30] D. Needell and J. Tropp. CoSaMP: Iterative signal recovery from incomplete and inaccurate
samples. Appl. Comput. Harmon. Anal. 26 (2009), no. 3: 301–321.
[31] Y. Plan, R. Vershynin, and E. Yudovina. High-dimensional estimation with geometric constraints. Inf. Inference 6 (2017), no. 1: 1–40.
20

[32] H. Rauhut, K. Schnass, and P. Vandergheynst. Compressed sensing and redundant dictionaries. IEEE Trans. Inform. Theory 54 (2008), no. 5: 2210–2219.
[33] M. Rudelson and R. Vershynin. On sparse reconstruction from Fourier and Gaussian measurements. Comm. Pure Appl. Math. 61 (2008), no. 8: 1025–1045.
[34] M. Talagrand. “Upper and lower bounds for stochastic processes: modern methods and
classical problems.” Springer Science & Business Media (2014).
[35] R. Tibshirani. Regression shrinkage and selection via the lasso. J. Roy. Statist. Soc. Ser. B
58 (1996), no. 1: 267–288.
[36] J. A. Tropp. Convex recovery of a structured signal from independent random linear measurements. “Sampling theory, a renaissance.” Appl. Numer. Harmon. Anal., Birkhuser/Springer,
Cham, (2015): 67–101.
[37] R. Vershynin. Estimation in high dimensions: a geometric perspective. “Sampling theory, a
renaissance.” Appl. Numer. Harmon. Anal., Birkhuser/Springer, Cham, (2015): 3–66.
[38] M. Wainright. Statistics meets optimization:
randomization and approximation for high-dimensional problems. Nachdiplom Lecture, ETH Zurich (2015).
https://www.stat.berkeley.edu/~wainwrig/nachdiplom/. Scribed by Y. Wei.
[39] T. Zhang. Sparse recovery with orthogonal matching pursuit under RIP. IEEE Trans. Inform.
Theory. 57 (2011), no. 9: 6215–6221.

21

