arXiv:1610.04983v2 [] 23 Mar 2018

Improved bounds for sparse recovery from subsampled random
convolutions
Shahar Mendelson∗, Holger Rauhut†, Rachel Ward‡
March 28, 2018

Abstract
We study the recovery of sparse vectors from subsampled random convolutions via ℓ1 minimization. We consider the setup in which both the subsampling locations as well as
the generating vector are chosen at random. For a subgaussian generator with independent entries,
p we improve previously known estimates: if the sparsity s is small enough,
i.e., s . n/ log(n), we show that m & s log(en/s) measurements are sufficient to recover
s-sparse vectors in dimension n with high probability, matching the well-known condition for recovery from standard Gaussian measurements. If s is larger, then essentially
m ≥ s log2 (s) log(log(s)) log(n) measurements are sufficient, again improving over previous estimates. Our results are shown via the so-called robust null space property which
is weaker than the standard restricted isometry property. Our method of proof involves
a novel combination of small ball estimates with chaining techniques which should be of
independent interest.

1

Introduction

Compressive sensing [6, 14, 18] considers the recovery of (approximately) sparse vectors from
incomplete and possibly perturbed linear measurements via efficient algorithms such as ℓ1 minimization. Provably optimal bounds for the minimal number of required measurements in
terms of the sparsity have been shown for Gaussian and, more generally, subgaussian random
matrices [4, 9, 14, 15, 18, 29, 30, 40].
Practical applications demand for structure in the measurement process which is clearly
not present in Gaussian random matrices with independent entries. Several types of structured
random matrices have been studied, including random partial Fourier matrices [6, 7, 40, 35, 38,
5], partial random circulant matrices (subsampled random convolutions) [25, 34, 35, 37, 39],
time-frequency structured random matrices [25, 36, 33], and more [2, 21]. In this article, we
improve known recovery results for partial random circulant matrices.
∗

Department of Mathematics, Technion, Haifa, 32000, Israel, shahar@tx.technion.ac.il & Centre for Mathematics and its Applications, The Australian National University, Canberra 0200 Australia
†
Chair for Mathematics C (Analysis), RWTH Aachen University, rauhut@mathc.rwth-aachen.de
‡
Mathematics Department, University of Texas at Austin, 2515 Speedway, Austin, Texas, 78712,
rward@ma.utexas.edu

1

In mathematical terms, linear measurements of a signal (vector) x ∈ Rn can be written as
y = Ax

with A ∈ Rm×n ,

and we are particularly interested in the case m < n. Compressive sensing predicts that this
system can be solved for x using efficient algorithms if x is sparse enough, say in the sense
that kxk0 = |{ℓ : xℓ 6= 0}| is small. While ℓ0 -minimization is NP-hard [18], several tractable
algorithms have been introduced as alternatives, most notably ℓ1 -minimization (basis pursuit)
[6, 10, 14, 18] which produces a minimizer of
min kzk1 subject to Az = y.

z∈Rn

If A ∈ Rm×n is a random draw of a Gaussian matrix, i.e., all entries are standard normal
random variables, then with probability at least 1 − e−cm , any s-sparse vector x ∈ Rn , (i.e.,
kxk0 ≤ s), can be reconstructed in a stable way (see below) using ℓ1 -minimization from the
given data y = Ax, provided that
m ≥ Cs ln(en/s)
(1)
for some absolute constant C > 0. This bound is optimal [14, 17, 18] in the sense that the
combination of any recovery algorithm with any measurement matrix requires at least (1) many
measurements in order to achieve stable reconstruction, i.e., for any x ∈ Rn (not necessarily
s-sparse), the reconstruction x♯ obtained from y = Ax, satisfies
kx − x♯ k1 ≤ Cσs (x)1 := C inf{kx − zk1 : kzk0 ≤ s},

(2)

see [17, Theorem 2.7] for details. Moreover, exact s-sparse recovery via ℓ1 -minimization necessarily requires (1), see [17, Lemma 2.4].
Unfortunately, Gaussian random matrices are not suitable for many applications of compressive sensing – because of their lack of structure. In fact, structure is required in order to
model realistic measurement scenarios and also to speed up the matrix-vector-multiplications
that have to be applied many times in known ℓ1 -minimization algorithms.
An important example of structured random matrices are m×n matrices that are generated
from the n×n discrete Fourier (more generally, from a Hadamard type matrix, see Definition 2.6
below), by randomly subsampling m rows. This corresponds to taking m random samples of
the discrete Fourier transform of a vector. Again, ℓ1 -minimization successfully recovers s-sparse
vectors with probability at least 1 − ε provided that
m ≥ Cs max{log2 (s) log(n), log(ε−1 )},
see, for example, [7, 40, 35, 5, 20].
In this article we will be concerned with subsampled random convolutions. The circular
convolution on Rn is defined for two vectors x, ξ ∈ Rn as
(x ∗ ξ)k =

n
X

xj ξk−j mod n+1 ,

j=1

2

k = 1, . . . , n.

For a subset Ω ⊂ {1, . . . , n} =: [n] of cardinality m, let PΩ : Rn → Rm be the projection onto
the coordinates indexed by Ω, i.e., (PΩ x)j = xj for j ∈ Ω. A subsampled convolution is defined
as
Bx = PΩ (x ∗ ξ)
(3)
and the corresponding matrix is a partial circulant matrix generated by ξ. Subsampled random
convolutions find applications in radar and coded aperture imaging [3, 19, 39, 43], as well as in
fast dimensionality reduction maps [26].
It was shown in [25] that if ξ is a (standard) Gaussian vector and Ω is an arbitrary (deterministic) subset of cardinality m, then with probability at least 1 − ε, every s-sparse vector
can be reconstructed from Bx via ℓ1 -minimization if
m ≥ Cs max{log2 (s) log2 (n), log(ε−1 )}.

(4)

Stability in the sense of (2) holds for such matrices, and the results are robust when the given
measurements are corrupted by noise (see more details below). Moreover, the recovery result
can be extended to circulant matrices generated by a subgaussian random vector – an object
of central importance to our discussion which will be defined later.
Our focus is on sparse recovery via subsampled random convolutions, where the set Ω is
chosen at random via independent selectors: let (δi )ni=1 be independent, {0, 1}-valued random
variables with mean δ = m/n ∈ (0, 1], and set Ω = {i : δi = 1}. Then the expected size of Ω is
E|Ω| = m and it follows from Bernstein’s inequality that m/2 ≤ |Ω| ≤ 3m/2 with probability
at least 1 − 2 exp(−m/9).
For the sake of simplicity of this exposition, we shall first formulate our main theorem for
a standard Gaussian generator, i.e., a random vector with independent, mean zero, variance
one, normally distributed coordinates. However, the proof we present holds for more general Lsubgaussian random vectors with independent coordinates and a more general class of random
matrices (see Theorem 2.5).
Theorem 1.1. Let ξ ∈ Rn be a draw of a standard Gaussian random vector and let Ω ⊂ [n] be
chosen at random, using independent selectors of mean δ = m/n. Let B be the corresponding
partial random circulant matrix defined in (3). Let s ≤ c1 logn4 (n) and assume that
q
n
if s ≤ c2 log(n)
q
n
if c2 log(n)
≤ s ≤ c1 logn4 (n) ,

m ≥ c3 s log(en/s)

m ≥ c3 s log(en/s)α2s log(eαs )

where αs = log



s2
n

(5)


max{log(en/s), log(s)} . Then with probability at least
o

nn
, s log(en/s)
1 − 2 exp −c0 min
s

the following holds. For all x ∈ Rn , all e ∈ Rm with kek2 ≤ η and y = Bx + e, the minimizer
x♯ of
min kzk1 subject to kBz − yk2 ≤ η
(6)

3

satisfies
√
sη
kx − x k1 ≤ Cσs (x)1 + D √
m
σs (x)1
η
kx − x♯ k2 ≤ C √
+ D√ .
s
m
♯

and

(7)
(8)

The constants c1 , c2 , c3 , C, D > 0 are absolute.
√
Our estimates indicate a phase-transition that occurs when s is roughly of the order of n.
Below this level, the partial circulant matrix exhibits the same behavior as the Gaussian matrix
(which is the optimal scaling of the number of measurements m as a function of the sparsity
parameter s) – it requires Cs log(en/s) measurements to recover an s sparse vector. Above
that level, our estimates require more measurements; for example, if s = nα for 1/2 < α < 1
then c(L, α)s log 3 n · log log n measurements are p
needed.
As we will see later, the phase transition at n/ log(n) is not a coincidence – the analysis
required in the low-sparsity case is truly different from the one needed to deal with the highsparsity one. However, it is presently not clear whether the analysis for the high-sparsity case
can be improved in order to remove the additional logarithmic factors.
In both cases (low and high sparsity) we improve the estimates from [25], though it should
be noted that (4) applies to any set Ω ⊂ [n] of cardinality m, while (5) applies only to randomly
chosen Ω. A random selection Ω has been considered in [39], but the estimates there require
m ≥ Cs log6 (n). On the other hand, [39] applies to vectors that are sparse in an arbitrary
(fixed) orthonormal basis and not only in the canonical basis; our proof technique does not
seem to extend to this case in a simple way.
We stress that (1.1) provides a uniform recovery guarantee in the sense that a single random
draw of the partial circulant matrix is able to recovery all s-sparse vectors simultaneously. This
is in contrast to other previous so-called nonuniform results found in the literature [34, 35, 22]
that only imply recovery of a fixed sparse vector from a random draw of the matrix. Moreover,
these nonuniform results give no or weaker stability estimates than (7) and (8), see e.g. [18,
Theorem 4.33] or [16].
Another improvement on known estimates is that our results hold for noisy measurements
when the noise is bounded in ℓq for q ≥ 2 and the ℓ2 -constraint in (6) is replaced by an
ℓq -constraint (and the error estimates scale with the ℓq norm of the noise), see Theorem 2.5
for details. (Note that a standard RIP-based argument appeared after the first submission
of this manuscript in [12, Theorem A.1].) This allows us, for example, to explore quantized
compressive sensing (see, e.g., [13]), when the quantization error has a natural ℓ∞ -bound.
We note that for a few other constructions of structured random matrices (with fast matrixvector multiplication), recovery results with the optimal number of measurements (1) have
been shown under similar size restrictions on the sparsity as in our main theorem above [1, 2].
However, it seems that our construction is the simplest one and is arguably the only one among
these which models a physically realizable measurement device. In contrast to these previous
results, we are able to extend our bounds to the near-linear sparsity regime at the cost of some
additional logarithmic factors.
Apart from our main results themselves, we believe that our proof techniques are of independent interest. In fact, the crucial ingredient is a probabilistic lower bound on terms of
4

the form inf v∈Vr kΓv ξk2 , where Γv are matrices indexed by a set of unit-norm r-sparse vectors,
and ξ is a subgaussian random vector with independent coordinates. It is based on a new
approach that can be generalized to other generating random vectors with heavier tails and
less independence assumptions, for instance, to log-concave random vectors.
The article is structured as follows. Section 2 discusses preliminaries such as the null space
property, subgaussian random vectors, states the main result and gives a brief explanation of
its proof. Section 3 introduces the small ball estimates required for the proof as well as moment
estimates for norms of subgaussian random vectors. It further provides some covering number
estimates required in the sequel. Section 4 provides the main technical ingredient of the proof
of our main results: a lower bound for inf v∈Vr kΓv ξk2 . Section 5 provides an upper bound for
one-sparse vectors, which is the final ingredient in the proof of the null space property, see also
Theorem 2.3.

2
2.1

Preliminaries and the main result
The null space property

Our analysis is based on a robust version of the null space property, which is a sufficient and
necessary condition for sparse recovery via ℓ1 -minimization. This version is stable when passing
to approximately sparse vectors and robust when the measurements are noisy.
Given v ∈ Rn and S ⊂ [n] = {1, . . . , n}, let vS ∈ Rn with entries (vS )j = vj for j ∈ S and
(vS )j = 0 for j ∈
/ S. Further, S c = [n] \ S denotes the complement of S.
Definition 2.1. For 1 ≤ q ≤ ∞, a matrix A satisfies the ℓq -robust null-space property of order
s with constants ν ∈ (0, 1) and τ > 0 if
ν
kvS k2 ≤ √ kvS c k1 + τ kAvkq
s
for every v ∈ Rn and every S ⊂ [n] of cardinality at most s.
The following result is standard by now (see, e.g., [18, Theorem 4.22]). It uses the notion
of the error of best s-term approximation, defined as
σs (x)1 =

min kx − zk1 ;

z:kzk0 ≤s

that is, σs (x)1 is the ℓ1 -distance between x and the set of s-sparse vectors.
Theorem 2.2. Let 1 ≤ q ≤ ∞ and let A satisfy the ℓq -robust null space property of order s
with constants ν ∈ (0, 1) and τ > 0. Let kekq ≤ η, x ∈ Rn and put y = Ax + e. Then a
minimizer x♯ of
minn kzk1 subject to kAz − ykq ≤ η
z∈R

satisfies
√
kx − x♯ k1 ≤ Cσs (x)1 + D sη
C
kx − x♯ k2 ≤ √ σs (x)1 + Dη,
s
where the constants are given by C =

(1+ν)2
1−ν

and D =
5

(3+ν)
1−ν τ .

(9)
(10)

Roughly speaking, even if x is not s-sparse, but only approximated by an s-sparse vector,
and if one receives linear measurements of x (i.e., Ax) that are corrupted by the “noise” e, then
a solution to the minimization problem still yields a good approximation of x if A possesses
the null space property. In particular, if x is s-sparse then σs (x)1 = 0, and if η = 0 (no noise),
then the reconstruction via equality constrained ℓ1 -minimization is exact.
In order to show the ℓq -robust null-space property, we will proceed in the following way.
Let


ν
n
Tν,s := v ∈ R : kvS k2 ≥ √ kvS c k1 .
s
One may show (see, e.g., [13, 23]) that if
inf

x∈Tν,s

∩S n−1

kAxkq ≥

1
,
τ

then A satisfies the ℓq -robust null space property with constants ν and τ . Moreover, if we set
Vs = {x ∈ Rn : kxk0 ≤ s, kxk2 = 1}
to be the set of s-sparse vectors in the unit sphere, then ([23, Lemma 3], see also [40])
Tν,s ∩ S n−1 ⊂ (2 + ν −1 ) conv Vs ,

(11)

allowing one to study conv Vs instead of Tν,s , where conv S denotes the convex hull of a set S,
that is, the set of all convex combinations of finite subsets of S.
It turns out that one may replace conv Vs with Vr for r sufficiently large by adding a
condition on one-sparse vectors. This was observed for q = 2 in [32, Lemma 5.1] (see also [27,
Theorem B]), but extends also to q > 2 as we outline below.
Theorem 2.3. Let A ∈ Rm×n satisfy
inf kAxk2 ≥ τ −1

x∈Vr

and

If c(ν) = ν 2 /(2ν + 1)2 and
s ≤ c(ν)
then

max kAej k2 ≤ M.

(12)

j≤[n]

r−1
,
M 2τ 2 − 1

1
inf kAxk2 ≥ √ .
x∈Tν,s
2τ

Consequently, A also satisfies the ℓq -robust NSP, for q > 2:
inf kAxkq ≥

x∈Tν,s

1

inf kAxk2 ≥

m1/2−1/q x∈Tν,s

1
m1/2−1/q

√

2τ

Proof. By (11), it suffices to show that the conditions in (12) imply that
√
kAxk2 ≥ 1/( 2τ ).
inf
x∈(2+ν −1 ) conv Vs ∩S n−1

6

.

Applying [27, Lemma 2.6], it follows from (12) that for any y ∈ Rn


n
X
1 
kAyk22 ≥ τ −2 kyk22 −
kAej k22 |yj | − τ −2 kyk21  .
kyk1
r−1

(13)

j=1

√
Let B1n be the unit ball in ℓn1 and observe that conv Vs ⊂ sB1n . Thus, if c1 (ν) = 2 + 1/ν and
y ∈ S n−1 ∩ c1 (ν) conv Vs ,
√
kyk2 = 1 and kyk1 ≤ c1 (ν) s.

Therefore,


kyk21 2
(τ max kAej k2 − 1)
kAyk22 ≥ τ −2 1 −
1≤j≤n
r−1


2

c1 (ν)s 2 2
1
−2
≥τ
1−
τ M −1 ≥ 2
r−1
2τ

by our choice of s. The first inequality in (13) is due to Hölder.

With Theorem 2.3 at hand, we will take the following course of action: we will show that
√
√
(14)
inf kPΩ Axk2 & m and max kPΩ Aej k2 . m
x∈Vr

j∈[n]

for a partial circulant matrix PΩ A, whose rows are chosen using iid selectors.

2.2

Subgaussian random vectors

Just as in [25] we will focus on generators ξ that are isotropic, L-subgaussian and have independent coordinates.
Definition 2.4. A centered random vector ξ = (ξi )ni=1 is L-subgaussian if, for every x ∈ Rn ,
√
(E| ξ, x |p )1/p ≤ L p(E| ξ, x |2 )1/2 .

Assume that ξ1 , . . . , ξn are independent, mean-zero, variance 1, L-subgaussian random variables. In other words, for every p ≥ 1,
√
√
(E|ξi |p )1/p ≤ L p(E|ξi |2 )1/2 = L p.

2

Then ξ is an isotropic random vector on Rn : for every x ∈ Rn , E ξ, x = kxk22 , and it is
standard to verify that it is L-subgaussian as well (see, e.g., [44]). Is it straightforward to show
that if ξ is an L-subgaussian random vector, then for every x ∈ Rn and u ≥ 1,


P r | ξ, x | ≥ uL(E| ξ, x |2 )1/2 ≤ 2 exp(−cu2 ),

for a suitable absolute constant c. If, in addition, ξ is isotropic, then

P r | ξ, x | ≥ uLkxk2 ≤ 2 exp(−cu2 ).
7

2.3

Main result

Our main result provides a bound for the null-space property of partial random circulant
matrices. It implies Theorem 1.1 via Theorem 2.2.
Recall that
• ξ is a random vector whose coordinates are independent, mean-zero, variance 1, L-subgaussian
random variables;
• A is the complete circulant matrix generated by ξ;
• (δi )ni=1 are independent selectors of mean δ = m/n, and Ω = {i : δi = 1}.

Theorem 2.5. There exist constants c0 , . . . , c6 that depend only on L, ρ and τ for which the
following holds for all q ≥ 2. With probability at least

nn
 en o
1 − 2 exp −c0 min
,
, r log
r
r
the partial circulant matrix PΩ A satisfies the ℓq -robust null-space property of order r with
constants ρ ∈ (0, 1) and mτ1/q , where
r
 en 
n
if r ≤ c4
,
δn = c3 r log
r
log n
and

δn = c3 r log
The constant αr satisfies

 en 
r

·

α2r log(eαr )

if c4

r

n
n
< r ≤ c5 4 .
log n
log n

o
n  en 
r2
, log(er)
.
αr ≤ log c6 max log
n
r


Theorem 2.5 is obtained from the analysis to follow by combining Theorem 5.1 and Corollary
4.2, and applying Theorem 2.3. Actually, our analysis holds for a more general class of random
matrices, see Definition (2.6) and the remarks following it.

2.4

The heart of the argument

The proof of Theorem 2.5 has two main components. We will begin by analyzing the way a
complete circulant matrix A : Rn → Rn generated by ξ acts on Vr , and then apply a random
“selector projection” PΩ to the image AVr . Our primary goal is to obtain a lower bound on
inf kPΩ Avk22 = inf

v∈Vr

v∈Vr

n
X

2

δi Av, ei .

(15)

i=1

Thanks to the nature of circulant matrices, there is a standard representation of {Av :
v ∈ Vr } via the Fourier transform. Let F be the (un-normalized) Fourier transform, i.e.,
Fj,k = e−2πijk/n , (which we treat as a “real operator” from Rn onto the image of Rn in order
to avoid working with Cn ) and set v̂ = Fv. If Dx = diag(x1 , . . . , xn ) then
Av = F −1 Dv̂ Fξ.

We will consider a more general set of matrices:
8

Definition 2.6. An orthogonal matrix O is of Hadamard type with constant β ≥ 1 if for every
√
i, j ∈ [n], |Oi,j | ≤ β/ n.
In what follows we will fix three matrices, U, W and O, each of which is of Hadamard type
with constant β, and for x ∈ Rn we set
√
(16)
Γx = nU DW x O,
where DW x = diag(( Wi , x )ni=1 ). Clearly, the representation of Av is precisely of this form: if A
√
is the complete circulant matrix with the generator ξ then for every v ∈ Rn , Av = nU DW v Oξ
for the choice of U = n−1/2 F −1 and W = O = n−1/2 F; in this case β = 1.
From here on, for V ⊂ Rn set
√
ΓV = { nU DW v O : v ∈ V };
naturally, the set of matrices we will be interested in is ΓVr .
Observe that if ξ is an isotropic random vector then for every v ∈ S n−1 , EkΓv ξk22 = n, and
√
at least on average, for a single vector v ∈ Vr , one expects to have kΓv ξk2 ∼ n.
√
Unfortunately, showing that inf v∈Vr kΓv ξk2 ≥ c n alone does not lead to a nontrivial lower
bound on (15). To see why, set
√
x1 = ( n, 0, . . . , 0) and x2 = (1, . . . , 1).
√
Both x1 and x2 have a Euclidean norm of n, but any attempt of selecting a random subset of
coordinates of cardinality m ≪ n fails miserably for x1 and succeeds for x2 : typically, PΩ x1 = 0
√
while kPΩ x2 k2 = m. We will be looking at this type of “good behavior”, exhibiting a (one
sided) standard shrinking phenomenon. The term “one-sided standard shrinking” used in this
context usually refers to a random projection operator T of rank m, for which, with high
probability,
p
kT vk2 ≥ c m/nkvk2 for all vectors of interest.

The operator we are interested in is indeed random, and of the form T = PΩ – a random
coordinate projection – but as the example of x1 shows, PΩ may map x to 0 even if x has a
large norm – unless one imposes some additional condition on x.
The condition we will focus on here is that x has a regular coordinate structure, that is, for
suitable constants α and θ,


α
≥ θn.
(17)
i : |xi | ≥ kxk2 √
n
√
The notion of regularity in (17) implies that |xi | is at least ∼ kxk2 / n for a large subset of
coordinates – of cardinality that is proportional to the dimension n. That set of coordinates
contributes at least a proportion
p of the Euclidean norm of x, and moreover, for a random choice
of Ω ⊂ [n], kPΩ xk2 ≥ ckxk2 · |Ω|/n with high probability.
√
Thus, in addition to showing that inf v∈Vr kΓv ξk2 ≥ c n, we will prove that each of the
vectors Γv ξ is regular in the sense of (17). We will do so by representing a typical realization of
the set {Γv ξ : v ∈ Vr } as a subset of the Minkowski sum of two (random) sets T1 + T2 defined
in the following way: Let H ⊂ Vr be a fine enough net with respect to the Euclidean distance
and set T1 = {Γx ξ : x ∈ H}. For each v ∈ Vr , choose x = π(v) ∈ H minimizing kx − vk2 . Then
T2 = {Γv−π(v) ξ : v ∈ Vr }. We will show the following properties of the sets T1 , T2 :
9

√
• Every t ∈ T1 satisfies ktk2 & n and has regular coordinate structure in the sense of (17).
As a consequence, a random coordinate projection
PΩ will not shrink the ℓ2 -norm of
√
elements in T1 by more than a factor of ∼ δ, and therefore, with high probability,
√
inf kPΩ Γx ξk2 ≥ c δn.
x∈H

√
• The set of “random oscillations” T2 has Euclidean diameter smaller than (c/2) δn. Thus,
its effect is negligible.
What may still appear mysterious is the claim that there is a phase transition in the choice
of δ – and thus in the required number of measurements. The origin of the phase transition
lies in a gap between the cardinality of the net H and the probability estimate one is likely
to have for each Γv . Indeed, for reasons that will be clarified later, the probability that Γv ξ is
“well behaved” can be estimated by exp(−cn/r). In contrast, as a nontrivial Euclidean net in
Vr , |H| ≥ exp(c1 r log(en/r)). In the low-sparsity case, when n/r & r log(en/r), the individual
probability estimate is strong enough to allow uniform control on all the vectors in the net
H. In the high-sparsity case that is no longer true, and an additional argument is required to
bridge the gap between n/r and r log(en/r). Specifically, we will show how one may “transfer
information” from a set of cardinality exp(cn/r) to the net H whose cardinality is much larger
– of the order of exp(cr log(en/r)).

2.5

Notation

Throughout this article, absolute constants are denoted by c, c1 , C, etc. The notation c(L)
refers to a constant that depends only on the parameter L; a ∼ b implies that there are
absolute constants c and C for which ca ≤ b ≤ Ca; and a ∼L b means that the constants c and
C depend only on L. The analogous one-sided notation is a . b and a .L b. Constants whose
values remain unchanged throughout the article are denoted by κ1 , κ2 , etc. .
For 1 ≤ p ≤ ∞ let ℓnp be the normed space (Rn , k kp ) and set Bpn to be its unit ball. S n−1
is the Euclidean unit sphere in Rn . The expectation is denoted by E and P r denotes the
probability of an event. The Lp -norm of a random variable X is denoted kXkLp = (E|X|p )1/p .
We also recall that [n] = {1, . . . , n}.

3
3.1

Small ball estimates and chaining
The random generator

Recall that the random vector ξ we are interested in has independent coordinates (ξi )ni=1 that
are mean-zero, variance 1 and L-subgaussian. In particular, ξ is an isotropic, L-subgaussian
random vector.
A simple observation is that the ξi ’s satisfy a small-ball property: there are positive constants c1 and c2 that depend only on L for which
sup P r(|ξi − u| ≥ c1 ) ≥ c2 .
u∈R

10

(18)

Indeed, for any u ∈ R, kξi − ukL2 ∼ max{kξi kL2 , |u|}, and thus kξi − ukL4 ≤ c3 Lkξi − ukL2 for
a suitable absolute constant c3 . The small-ball property (18) is an immediate outcome of the
Paley-Zygmund inequality (see, e.g., [18, Lemma 7.16]) applied to each Xu = |ξi − u|.
The small-ball property (18) tensorizes, leading to a vector small-ball property for ξ =
n
(ξi )i=1 . To formulate this property, let kΓkHS and kΓk2→2 denote the Hilbert-Schmidt (Frobenius) and operator norms of a matrix Γ, respectively, and set
dΓ =



kΓkHS
kΓk2→2

2

.

Theorem 3.1. [41] For 0 < p < 1, there exists a constant c = c(p) > 0 for which the
following holds. Let X1 , . . . , Xn be independent random variables that satisfy for some t > 0
and 0 < p < 1
sup P r(|Xi − u| ≤ t) ≤ p.
u∈R

Then, for X = (X1 , . . . , Xn ) and every matrix Γ : Rn → Rm ,
 cdΓ
1
.
P r(kΓXk2 ≤ tkΓkHS ) ≤
2
The small-ball property for individual ξi ’s from (18) and Theorem 3.1 imply that the random
vector ξ satisfies a small-ball estimate.
Corollary 3.2. There exist constants κ1 and κ2 that depend only on L such that, for any
matrix Γ : Rn → Rm ,
 κ2 dΓ
1
.
(19)
P r(kΓξk2 ≤ κ1 kΓkHS ) ≤
2
It should be noted that a subgaussian vector with independent coordinates is not the only
random vector that satisfies a small-ball estimate like (19). Moreover, such small-ball estimates
can be used to extend our main result to a larger class of generators – a direction we will not
explore further in this work.
The other type of bound we require deals with the way the moments of kξk grow, for
an arbitrary norm k k on Rn . Unlike Corollary 3.2, this feature does not require ξ to have
independent coordinates, and it holds for any (isotropic) subgaussian random vector (see, for
example, [25, Theorem 2.3]).
Theorem 3.3. There exists an absolute constant c for which the following holds. Let ξ be
an isotropic, L-subgaussian random vector in Rn and set G = (g1 , . . . , gn ) to be the standard
Gaussian vector in Rn . Let k k be a norm on Rn and set B ◦ to be the unit ball of its dual
norm. Then for every p ≥ 1,

√
(Ekξkp )1/p ≤ cL EkGk + p sup ktk2 .
t∈B ◦

We will consider two families of norms associated with the non-increasing rearrangement of
the coordinates of a vector.

11

Definition 3.4. Let (x∗i )ni=1 denote the non-increasing rearrangement of (|xi |)ni=1 . For k ∈ [n],
set
k
X
X 1/2
1/2
(x∗i )2
.
x2i
=
kxk[k] = max
|I|=k

i=1

i∈I

When k = n, the norm k k[k] is simply the Euclidean norm, and the unit ball of the dual
norm is just the standard Euclidean unit ball. When 1 ≤ k < n, the dual unit ball consists of
the set of unit-ℓ2 -norm k-sparse vectors, that is,
Vk = {v ∈ S n−1 : kvk0 ≤ k}.


Pk
∗ 2 1/2 . The
In order to apply Theorem 3.3 to k k[k] one has to control EkGk[k] = E
i=1 (gi )
following result for subgaussian random variables does not require independence.
Lemma 3.5. [24] Let Z1 , . . . , Zn be mean-zero and L-subgaussian random variables such that
maxi∈[n] kZi kL2 ≤ M . Then
E

k
X

(Zi∗ )2

i=1

1/2

≤ cLM

p

k log(en/k).

Proof. Since the proof of this result is not provided in [24], we give it here for convenience. Since
the Zi are L-subgaussian, there exist constants c0 , c1 > 0 such that (see e.g. [18, Proposition
7.23])
!
Zi2
≤ c1 .
E exp c0 2
L kZi k2L2
By Jensen’s inequality and concavity of the logarithm
"

k
1 X ∗ 2 1/2
(Zi )
E
k
i=1

#2

k

≤E

1X ∗ 2
(Zi )
k
i=1

k
X
−1
2 2 1
log(exp(c0 (Zi∗ )2 /(LkZi∗ kL2 )2 ))
≤ c0 M L E
k
i=1
!!
k
(Zi∗ )2
1X
−1
2 2
≤ c0 M L log
E exp c0 2 ∗ 2
k
L kZi kL2
i=1
!!
n
2
X
Z
1
2 2
2 2
E exp c0 2 i 2
≤ c−1
≤ c−1
0 M L log
0 M L log(c1 n/k).
k
L
kZ
k
i
L2
i=1

Rearranging this inequality and adjusting constants yields the claim.
For the choice Zi = ξi , it follows from Lemma 3.5 and Theorem 3.3 that for every p ≥ 1
and k ∈ [n],
p
√ 
k log(en/k) + p .
(20)
(Ekξkp[k] )1/p ≤ cL
12

The second family of norms we require is a generalization of the first one. Let Γ be a matrix
and set
k
X
∗ 1/2
( Γx, ei )2
kxkΓ,k = kΓxk[k] =
= sup x, t ,
t∈Γ∗ Vk

i=1

where the last equality follows from kzk[k] = supt∈Vk z, t .

Lemma 3.6. Let ξ be an isotropic, L-sugaussian random vector. Then for every matrix Γ and
any p ≥ 1,
!
p
√
p 1/p
∗
∗
k log(en/k) max kΓ ei k2 + p sup kΓ tk2 .
(EkΓξk[k] ) ≤ cL
1≤i≤n

t∈Vk

Proof. By Theorem 3.3, it suffices to estimate
EkGkΓ,k

k
X
∗ 1/2
( G, Γ∗ ei )2
= E sup G, t = E
t∈Γ∗ Vk

i=1

for a standard Gaussian vector G. This expectation may be controlled using Lemma 3.5 for
the choice of Zi = G, Γ∗ ei and that fact that M = maxi∈[n] kZi kL2 = maxi∈[n] kΓ∗ ei k2 .
The following standard relation between moments and tails is recorded for convenience as
it will be used frequently in the sequel. Its proof follows immediately from Markov’s inequality.
Lemma 3.7. Assume that a random variable Z satisfies (E|Z|p )1/p ≤ A for some p > 0 and
A > 0. Then, for α > 1,
P r(|Z| ≥ αA) ≤ α−p .
As noted above, the matrices we will be interested in are of the form
√
Γv = nU DW v O,

where U , W and O are Hadamard type matrices with constant β and v ∈ Rn . Thus,
√
√
1/2
kΓv kHS = nkvk2 , kΓv k2→2 = nkW vk∞ ≤ βkvk0 kvk2 ,
and for every i ∈ [n],
kΓ∗v ei k2

=

√

n

n
X

Wℓ , v

ℓ=1

2

2
· Ui,ℓ

1/2

≤ βkvk2 .

(21)

Combining Corollary 3.2, Lemma 3.6 and Lemma 3.7, one has the following:
Corollary 3.8. There exist constants κ1 , κ2 and κ3 that depend only on L and β for which
the following holds. If v ∈ Vr then
 κ2 n/r
√
1
P r(kΓv ξk2 ≤ κ1 nkvk2 ) ≤
,
(22)
2
and if v ∈ Rn and then with probability at least 1 − exp(−p),
p
√ √
kΓv ξk[k] ≤ κ3 (kvk2 k log(en/k) + p · nkW vk∞ ).
13

(23)

Remark 3.9. In what follows, (22) and (23) are the key features of ξ that we will use. To
establish those two facts we used rather special properties of ξ, but while those special properties
(for example, that ξ is stochastically dominated by a Gaussian vector) are highly restrictive, (22)
and (23), or even further relaxations of the two, actually hold for a wider variety of random
vectors. We will pursue this direction in a future contribution.

3.2

Definitions and basic facts

Let (T, d) be a metric space. A subset T ′ ⊂ T is called ε-separated if for every x, y ∈ T ′ ,
d(x, y) ≥ ε. By a standard comparison of packing and covering numbers, see e.g. [18, Lemma
C.2], if T ′ is a maximal ε-separated subset of T , it is also an ε-cover: that is, for every x ∈ T
there is some y ∈ T ′ for which d(x, y) ≤ ε.
In what follows we denote by N (T, d, ε) the cardinality of a minimal ε-cover of T . Note
that if T ⊂ Rn and d is a norm on Rn whose unit ball is B, then N (T, d, ε) is the minimal
number of translates of εB needed to cover T . Therefore, we will sometimes abuse notation
and write N (T, εB) instead of N (T, d, ε).
We will also use the language of Generic Chaining [42] extensively.
Definition 3.10. Given a metric space (T, d), an admissible sequence (Ts )s≥0 is a sequence of
s
subsets of T , with |T0 | = 1 and |Ts | ≤ 22 . Together with an admissible sequence one defines a
collection of maps πs : T → Ts . Usually, πs t is chosen as a nearest point to t in Ts with respect
to the metric d. For s ≥ 0 set
∆s t = πs+1 t − πs t.
Let us define several parameters that will be used throughout the proof of Theorem 2.5.
1. For r ∈ [n] set



log(er)
.
ρ = 10 log 2 e · max 1,
log(en/r)

2. Using the notation introduced earlier, put


κ2
κ21
κ4 = min
,
,
2 256κ23 L2 β 2

(24)

(25)

and observe that κ4 depends only on L and β. Moreover, without loss of generality,
κ4 ≤ 1, and κ3 , L, β ≥ 1.
3. Set s0 and s1 to satisfy
2s0 =

κ4 n
r

and 2s1 = ρr log(en/r)

(26)

and without loss of generality we will assume that s0 and s1 are integers.
4. Finally, let



ρr log(en/r)
= max{1, log(2s1 −s0 )}.
αr = max 1, log
κ4 (n/r)
14

(27)

A key part in the proof of Theorem 2.5 requires a different argument when 2s0 ≥ 2s1 and
when the reverse inequality holds. As we indicated earlier, we will call the former the “lowsparsity” case, and the latter the “high-sparsity” case. It is straightforward to verify that in
the low-sparsity case (2s0 ≥ 2s1 ), this corresponds to
r
n
1/2
r ≤ cκ4
, ρ = 10 log2 e, and αr = 1,
log(cn/κ4 )
while in the “high-sparsity” case,
1/2

r ≥ cκ4
if r ≤

√

r

n
;
log(cn/κ4 )

n then ρ = 10 log2 e, and otherwise, ρ = 10 log2 e ·
αr = log



and
αr = log

 en 
cr 2
· log
κ4 n
r





log(er)
log(en/r) .

if r ≤

Thus,

√
n,


cr 2
· log(er)
otherwise.
κ4 n

Let us again emphasize that κ1 , κ2 , κ3 and κ4 are all constants that depend only on L and β
– an observation that will be used throughout this article.

3.3

Covering of Vr

Let us begin by constructing (a part of) an admissible sequence for Vr .
Lemma 3.11. Let 1 ≤ r ≤ n/2 and s1 as above. There exists an admissible sequence (Vr,s )s≥s1
for which
X √
√
c
( n + r2s/2 )k∆s vk2 ≤ 3/2 ,
sup
n
v∈Vr s≥s
1

where πs v is the nearest point to v in Vr,s with respect to the Euclidean norm, ∆s v = πs+1 v−πs v
and c is an absolute constant.
We note that the exponent 3/2 above is rather arbitrary. We could easily replace it by a
larger one by adjusting constants.
Proof. Let Vr,s be a maximal εs separated subset of Vr with respect to the Euclidean norm and
s
of cardinality 22 . Thus it is also an εs -cover of Vr and
k∆s vk2 ≤ kπs+1 v − vk2 + kπs v − vk2 ≤ 2εs .
To estimate εs , observe that
by a standard volumetric estimate, see e.g. [18, Proposition C.3],
n
and summing over all r possible support subsets of [n] of cardinality r, for any 0 < ε < 1/2,
the cardinality of a maximal ε-separated subset of Vr is at most
   r 


 
n
3en r
3
n
2 r
≤
≤
.
1+
r
ε
ε
rε
r
15

Hence,
−2s /r

εs ≤ 2
and
sup

X

v∈Vr s≥s
1

2s/2 k∆s vk2 ≤ 2

X

s≥s1



3en
r



,

2s/2 εs ≤ c0

n X
s
2s/2−2 /r .
·
r
s≥s1

It is straightforward to verify that for every s ≥ s1 ,
2s /r ≥ 2(s/2).

(28)

This follows for s1 because 2s1 = ρr log(en/r) and
o
n  en 
2s1
, log(er) ≥ s1 ,
= (10 log 2 e) · max log
r
r

and for s > s1 because s 7→ 2s /s is increasing. Therefore,
sup

X

v∈Vr s≥s
1

2s/2 k∆s vk2 ≤ c0

n X −2s /(2r)
2
,
·
r
s≥s1

which is dominated by a geometric series with power
s
2−2 1 /2r = 2−(ρ/2) log(en/r) ≤ 1/4. Therefore,
 r  ρ −1
n
s1
n X −2s /2r
2 log2 e
2
. · 2−2 /(2r) ≤ e−1
.
r
r
en
s≥s1

Note that

Indeed, if r ≤ n/r, i.e., if r ≤

otherwise,

√

 r  ρ −1
1
2 log2 e
≤
.
en
(en)2

√
n, then ρ/ log2 e ≥ 10 and

 r (ρ/2 log2 e)−1  1 4
1
≤ √
;
≤
en
en
(en)2
n ≤ r ≤ n/2 and ρ/ log2 e = 10 log(er)/ log(en/r) so that


 
 en   5 log(er)

en (ρ/2 log2 e)−1
− 1 ≥ log (en)2 ,
= log
log
r
r
log(en/r)

so that (29) holds also in this case. Therefore,
X √
√
c1
( n + r2s/2 )k∆s vk2 ≤ 3/2
sup
n
v∈Vr s≥s
1

for an absolute constant c1 .

16

(29)

4

The structure of a typical {Γv ξ : v ∈ Vr }

The main component in the proof of Theorem 2.5 is a structural result on a typical realization
of the random set {Γv ξ : v ∈ Vr }.
Theorem 4.1. Recall the definitions of ρ, s0 , s1 , and αr from (24), (26), and (27), respectively.
There exist constants c0 , . . . , c3 that depend only on L and β for which the following holds.
s
s
With probability at least 1 − 2−c0 min{2 0 ,2 1 } ,
{Γv ξ : v ∈ Vr } ⊂ T1 + T2 ,
where

s1

Moreover, for each t ∈ T1 ,
√
1. ktk2 ≥ κ1 n, and

|T1 | ≤ 22

and T2 ⊂ c1 n−3/2 B2n .

√

2. ktI k2 ≤ κ14 n on the set I = I(t) ⊂ [n] of largest-magnitude coordinates of t of cardinality
n
.
|I| ≥ c2 α2 log(eα
r)
r

Theorem 4.1 implies that a typical realization of {Γv ξ : v ∈ Vr } is just a perturbation of
the (random) set T1 , and that T1 consists of vectors with a regular coordinate structure: for
√
each t ∈ T√1 consider the set J = I(t)c and observe that it follows from ktk2 ≥ κ1 n and
√
1
n and
ktI k2 ≤ κ14 n that ktJ k2 ≥ 15κ
16
1/2

X
p
κ1
1
|t∗j |2  ≤ √ αr log(eαr ).
ktJ k∞ ≤ |t∗|I(t)| | ≤ 
(30)
|I(t)|
4 c2
j∈I(t)

This implies that at least θ = c/(α2r log(eαr )) coordinates of tJ are larger than a constant.
When s0 ≥ s1 (the low-sparsity case), αr = 1, and the claim is that with probability at least
1 − 2−c0 ρr log(en/r) , for every t ∈ T1 , there is a subset I ⊂ [n] of cardinality |I| ≥ c2 n of
coordinates which are larger than a constant, and thus, each one of the vectors t ∈ T1 has a
regular coordinate structure in the sense of (17).
When s1 > s0 , a similar type of claim holds, but with probability at least 1 − 2−c0 κ4 n/r ,
and the regularity condition on the coordinates of t ∈ T1 is slightly weaker: one no longer has
a subset of cardinality that is proportional to n consisting of coordinates that are larger than
a constant, but rather a (marginally) smaller set I.
Thanks to this information on the structure of a typical {Γv ξ : v ∈ Vr }, one may establish
the required lower bound on inf v∈Vr kPΩ Γv ξk2 .
Corollary 4.2. There exist constants c0 , c1 and c2 that depend only on L and β for which the
following holds. Let
δn ≥ c0 (α2r log(eαr )) · ρr log(en/r),
with ρ defined in (24) and set (δi )i=1 to be independent selectors with mean δ. Then with
s
s
probability at least 1 − 2−c1 min{2 0 ,2 1 } ,
inf

v∈Vr

n
X

δi Γv ξ, ei

i=1

17

2

≥ c2 δn.

Proof. Let ξ be a realization of the event from Theorem 4.1 – which holds with probability at
s
s
least 1 − 2−c0 min{2 0 ,2 1 } relative to ξ – and let (δi )ni=1 be independent selectors with mean δ
that are also independent of ξ.
Using the notation of Theorem 4.1, let Γv ξ = t + y for t ∈ T1 and y ∈ T2 ; hence
!1/2
!1/2
!1/2
n
n
n
X
X
X
2
δi yi2
− sup
δi t2i
δi Γv ξ, ei
≥ inf
t∈T1

i=1

≥ inf

t∈T1

y∈T2

i=1

n
X

δi t2i

i=1

!1/2

−

i=1

c1
n3/2

(31)

for an absolute constant c1 . It suffices to show that
n
X

inf

t∈T1

i=1

δi t2i ≥ c2 δn,

the right hand being larger than 2c1 /n3 , where c2 is a suitable constant.
Fix t ∈ T1 , let J = J(t) = I c (t) be the complement of the set I(t) identified by Theorem
4.1 and put x = PJ t. Then as argued in (30) and the line above
kxk2 ≥

15c1 √
n
16

and

kxk∞ ≤ c3 αr

By Bernstein’s inequality,
Pr

p

log(eαr ).

(32)

o
X


n
w
w2
,
.
(δi − δ)x2i ≥ w ≤ 2 exp −c4 min P
δ i∈J x4i maxi∈J x2i
i∈J

P

4
2
Observe that
i∈J xi ≤ kxk∞
estimate becomes

P

i∈J

x2i , and thus, for w = (δ/2)


2 exp(−c4 δkxk22 /kxk2∞ ) ≤ 2 exp −c5 (L, β)

By a union bound, with probability at least


1 − 2|T1 |2 exp −c5

P

i∈J

x2i , the probability


δn
.
α2r log(eαr )


δn
,
α2r log(eαr )

relative to (δi )ni=1 , this implies that, for every t ∈ T1 ,
n
X
i=1

δi t2i ≥

X

i∈J(t)

δi t2i ≥

δ X 2 κ21
xi ≥ δn.
2
32
i∈J(t)

The claim follows by setting
2
s1 +1
δn ≥ c−1
= c7 (L, β) · α2r log(eαr ) · ρr log(en/r).
5 (αr log(eαr )) · 2

18

Remark 4.3. The following alternative argument starting from (32) leads to a
plower bound in
ℓq for any 1 ≤ q < ∞ – at least in the small sparsity regime s0 ≤ s1 , i.e., s ≤ c n/ log(n). For
fixed t ∈ T1 choose I = I(t) as the θn largest absolute coefficients of t where θ is defined in (34)
√
√
below (with suitable constants). We know from Theorem that ktk2 ≥ κ1 n and ktk[θn] ≤ κ4 n.
This implies that
!1/2 
n

1/2
X
1
1
2
2
∗ 2
∗
ktk2 − ktk[θn]
=
(ti )
tθn ≥
(1 − θ)n
(1 − θ)n
i=θn
1/2 √

1 2
15κ1
2
=
(κ n − κ1 n/16)
= c6 .
≥
n 1
4
For Ω = {i : δi = 1}
= I(t) ∩ Ω. Then, by Chernov’s inequality the cardinality of
P let K = K(t)
1
K satisfies |K| = j∈I(t) δi ≥ 2 δ|I| = 21 δθn probability at least 1 − e−δθn/8 . On this event,


kPΩ tkq ≥ 

X

j∈K

1/q

|tj |q 

≥ c6 (θδn/2)1/q

By the union bound, this holds for all t ∈ T1 with probability at least
s1

1 − 2|T1 | exp(−δθn) ≥ 1 − 2 · 22 exp(−δθn/8)

≥ 1 − 2 exp(−δθn/8 + ln(2)ρr log(en/r)).

Therefore, in the small sparsity regime s0 ≤ s1 , i.e., θ = c3 , a combination with a similar
estimate as in (31) gives
n
X
inf
δi hΓv ξ, ei iq ≥ cq8 δn
v∈Vr

i=1

with probability at least 1 − 2 exp(−c9 δn) provided that

δn ≥ c10 r log(en/r).
The proof of Theorem 4.1 is based on the following idea: (Vr,s )s≥s1 will be selected as an
maximal εs -separated
P subset of Vr and T1 = {Γv ξ : v ∈ Vr,s1 }. We will show that for every
v ∈ Vr , v − πs1 v = s≥s1 ∆s v is small enough to ensure that with high probability,
sup kΓv−πs1 v ξk2 ≤

v∈Vr

X

s≥s1

k∆s vk2 ≤

c′
n3/2

for c′ that depends on L and β. Then, we will turn to the more difficult part of the argument
– that with high probability, for every v ∈ Vr,s1 ,
√
√
(33)
kΓv ξk2 ≥ c n and kΓv ξk[θn] ≤ (c/4) n
for well-chosen c and
θ=





c1
α2r

c3
log(eαr )

for r ≤ c2
q

for c2

19

q

κ4 n
log(c2 n/κ4 )

κ4 n
log(c2 n/κ4 )

≤r≤

c4 n
log4 (n)

(34)

where all constants c, c1 , c2 , c3 , c4 only depend on L and β and κ4 is defined in (25), see (39) and
the following remarks as well as Lemma 4.11. Moreover, here and in the following, we assume
for simplicity that θn is an integer. (The general case may need slightly different constants.)
We begin the proof with its simpler part: a high probability estimate on supv∈Vr kΓv−πs1 v ξk2 .
Lemma 4.4. There exist constants c and c1 that depend only on L and β for which the following
s
holds. If (Vr,s )s≥s1 is an admissible sequence of Vr , then with probability at least 1 − 2−2 1 , for
every v ∈ Vr and s ≥ s1 ,
√
√ 
(35)
kΓ∆s v ξk2 ≤ c
n + 2s/2 r k∆s vk2 .
s

In particular, if Vr,s1 is a maximal separated subset of Vr , then with probability at least 1−2−2 1 ,
sup kΓv−πs1 v ξk2 ≤

v∈Vr

c1
.
n3/2

Proof. The first part of the proof is a straightforward outcome of (23). Indeed, if we set k = n
and p = 2s+3 , then by Corollary 3.8, with probability at least 1 − exp(−2s+3 ),
√
√
kΓ∆s v ξk2 ≤ 4κ3 ( nk∆s vk2 + 2s/2 · nkW ∆s vk∞ ).
Since v is r-sparse, ∆s v = πs+1 v − πs v is 2r-sparse, and since W is a Hadamard type matrix
with constant β,
√
√
1/2
nkW ∆s vk∞ = n max | Wi , ∆s v | ≤ βk∆s vk1 ≤ βk∆s vk0 · k∆s vk2 .
i∈[n]

Therefore,
2s

√
√
kΓ∆s v ξk2 ≤ 4κ3 ( n + β 2r 2s/2 )k∆s vk2 .

2s+1

(36)

2s+2

vectors of the form ∆s v, and thus, by a union bound, with
≤2
There are at most 2 · 2
s+2
probability at least 1 − 2−2 , (36) holds for every v ∈ Vr for that choice of s. Summing the
s +1
probabilities for s ≥ s1 , one has that with probability at least 1 − 2−2 1 , for every v ∈ Vr ,
X
X
kΓ∆s v ξk2
Γ∆s v ξk2 ≤
kΓv−πs1 v ξk2 = k
s≥s1

s≥s1


X √
√
√
c(L, β)
n + r2s/2 k∆s vk2 ≤
,
≤ 4 2κ3 β
n3/2
s≥s
1

where the last inequality is just Lemma 3.11.
Lemma 4.4 shows that if we set T2 = {Γv−πs1 v ξ : v ∈ Vr }, then with probability at least
s
1 − 2−2 1 , supt∈T2 ktk2 = supv∈Vr kΓv−πs1 v ξk2 ≤ c(L, β)/n3/2 , as required in Theorem 4.1.
Therefore, all that is left is to study the structure of T1 = {Γπs1 v ξ : v ∈ Vr }, and to show
that with high probability, it consists of vectors with a regular coordinate structure. To that
end we shall split the argument into two cases: the low-sparsity case, when s0 ≥ s1 and the
high-sparsity one, in which the reverse inequality holds. The analysis is based on Corollary 3.8
in both cases.
20

The low-sparsity case
Assume that 2s0 ≥ 2s1 ,i.e.,

κ4 n
r

≥ ρr log(en/r) and in particular, by the choice of κ4 in (25),
 en 
κ2 n
.
(37)
· ≥ ρr log
2 r
r

Fix v ∈ Vr,s1 . It follows from (22) that with probability at least 1 − 2−κ2 n/r ,
√
kΓv ξk2 ≥ κ1 n.

(38)

Let 0 < θ < 1 to be named later. Observe that by (23) for k = θn and p = 2ρr log(en/r) =
s +1
2s1 +1 , with probability at least 1 − e−2 1 ,
p
p
√
kΓv ξk[k] ≤2κ3 (kvk2 k log(en/k) + ρr log(en/r) nkW vk∞ )
p
√ p
√
(39)
≤2κ3 ( n θ log(e/θ) + β ρr log(en/r) · r),
√
√
because kvk2 = 1 and nkW vk∞ ≤ β r.
s
Recall that |Vr,s1 | ≤ 22 1 and thus, by (37) and the union bound, with probability at least
s
1 − 2−2 1 , (38) and (39) hold for every v ∈ Vr,s1 . All that remains is to ensure that
2κ3 β

p

√
κ1 √
θ log(e/θ) n ≤
n
8

√ p
κ1 √
and 2κ3 β r · ρr log(en/r) ≤
n.
8

The first condition holds for the right choice of the constant θ = θ(L, β). For the second, note
that by the definition of κ4 in (25)
ρr log(en/r) = 2s1 ≤ 2s0 ≤

n
κ21
· .
2
2
2
256κ3 L β r

Therefore,
√

2κ3 β r ·

p

√

κ1
·
ρr log(en/r) ≤ 2κ3 β r ·
16κ3 Lβ

r

κ1 √
n
≤
n,
r
8

because L ≥ 1.
This concludes the proof of Theorem 4.1 in the low sparsity case.
The high-sparsity case
Now consider the case 2s0 ≤ 2s1 , that is, κ4 n/r ≤ ρr log(en/r). Then there is a substantial gap
between the individual probability estimate (22) and the cardinality of Vr,s1 , so that a simple
union bound does not give a non-trivial probability estimate. The difficulty one faces here is
bridging this gap, and the key to the proof in the high-sparsity case is the following result.
Theorem 4.5. There exist constants c1 and c2 that depend only on L and β for which the
following holds. If r ≤ c1 n/ log4 n then with probability at least 1 − 2 exp(−c2 n/r),
eq inf kΓv ξk2 ≥
v∈Vr,s1

21

κ1 √
n.
2

For the proof of Theorem 4.5, one has to ‘transfer’ the lower bound on inf v∈Vr,s0 kΓv ξk2 ,
which may be obtained directly from (22) and the union bound, to the much larger set Vr,s1 .
Thus, it suffices to show that with high probability,
sup
v∈Vr,s1

kΓv ξk22 − kΓπs0 v k22 ≤

κ21
n,
4

(40)

for an approximating πs0 v ∈ Vr,s0 .
To address (40), we proceed along the lines of [25] and consider the following, more general
s
situation: let A be a class of matrices, |A| ≤ 22 1 and set (As )s≥s0 to be an admissible sequence
s
of A; that is, As is of cardinality at most 22 . Let πs A to be the nearest point to A in As with
respect to the k k2→2 norm, set ∆s A = πs+1 A − πs A, and put
γs0 ,s1 (A) = sup

sX
1 −1

A∈A s=s

0

2s/2 k∆s Ak2→2 .

Lemma 4.6. Assume A = As1 to be finite. Let ξ be an isotropic, L-subgaussian random vector
and set ξ ′ to be an independent copy of ξ. Let NA (ξ) = supA∈A kAξk2 and put
Z = sup

A∈A

Then, for every p ≥ 1,

Aξ, Aξ ′ − (πs0 A)ξ, (πs0 A)ξ ′ .

kZkLp ≤ cL sup γs0 ,s1 (A)kNA (ξ)kLp .
A∈A

for an absolute constant c.
Since the proof of Lemma 4.6 is contained in the proof of Lemma 3.3 in [25], it will not be
presented here.
We will be interested in the specific class of matrices A = {Γv : v ∈ Vr,s1 }:
Theorem 4.7. There exist constants c1 and c2 that depend only on L and β for which the
following holds. Let A = {Γv : v ∈ Vr,s1 } and set (As )s≥s0 to be an admissible sequence of A.
Then, with probability at least 1 − 2−c1 n/r ,
√ 
(41)
sup kAξk22 − kπs0 Aξk22 ≤ c2 γs0 ,s1 (A) γs0 ,s1 (A) + n .
A∈A

Before proving Theorem 4.7, let us recall a standard fact that can be established using tail
integration.
Lemma 4.8. Let Z be a nonnegative random variable and assume that
P r(Z ≥ A1 + uA2 ) ≤ 2 exp(−u2 /2)

for every u ≥ A3 .

√
Then, for every p ≥ 1, kZkLp ≤ c(A1 + A2 · max{A3 , p}), and c is an absolute constant.

22

Proof of Theorem 4.7. Denote by Aj , j ∈ [n], the columns of the matrix A and observe that
2

2

kAξk22 − kπs0 Aξk22 = Aξ, Aξ − πs0 Aξ, πs0 Aξ


X
=
ξj ξk Aj , Ak − (πs0 A)j , (πs0 A)k .
j,k

Since each A is of the form Γv for some v ∈ S n−1 , we have Aj , Aj = kvk22 = 1, and the same
holds for πs0 A. Therefore, Aj , Aj − (πs0 A)j , (πs0 A)j = 0 and all that remains is to control
the “off-diagonal” terms,


X
ξj ξk Aj , Ak − (πs0 A)j , (πs0 A)k =: FA .
j6=k

Denoting by ξ ′ an independent copy of ξ, applying a standard decoupling argument (see, for
example, [25, Theorem 2.4] or [11]) and Lemma 4.6
(E sup |FA |p )1/p = k sup (∗)A kLp
A∈A

A∈A

≤ 4 sup

A∈A

= 4 sup
A∈A

X
j,k

ξj ξk′





Aj , Ak − (πs0 A)j , (πs0 A)k

Aξ, Aξ ′ − πs0 Aξ, πs0 Aξ ′

Lp

Lp

≤ c1 Lγs0 ,s1 (A) · kNA (ξ)kLp .
Moreover,
k(NA (ξ))2 kLp ≤ sup kAξk22 − kπs0 Aξk22
A∈A

Lp

+ sup kπs0 Aξk22
A∈A

≤c1 Lγs0 ,s1 (A) · kNA (ξ)kLp + sup kπs0 Aξk22
A∈A

Lp

.
Lp

By (23) for k = n and p = u2 ≥ 2s0 +3 , it follows that with probability at least 1−2 exp(−u2 /2),
√
√
sup kπs0 Aξk2 = sup kΓv ξk2 ≤ κ3 ( n + u nkW vk∞ )
A∈A

v∈Vr,s0

√
√
≤ c2 (L, β)( n + u r),

p
where we used that kW vk∞ ≤ β r/n. Thus, the random variable Z = supA∈A kπs0 Aξk2
√
√
satisfies the conditions of Lemma 4.8 for A1 = c3 n, A2 = c3 r and A3 = 4 · 2s0 /2 , implying
that for every p ≥ 1,
sup kπs0 Aξk22

A∈A

Lp

√
√
√
≤ (EZ 2p )1/p ≤ c4 (L, β)( n + r max{2s0 /2 , p})2 .

23

Setting p = 2s0 = κ4 n/r we obtain
sup kπs0 Aξk22

A∈A

Therefore,

Lp

≤ c5 (L, β)n.


k(NA (ξ))2 kLp ≤ c6 (L, β) γs0 ,s1 (A)kNA (ξ)kLp + n ,

implying that

kNA (ξ)kLp ≤ c7 (L, β) max{γs0 ,s1 (A),
and

√

n}



√ 
p 1/p
E sup kAξk22 − kπs0 Aξk22
≤ c8 (L, β)γs0 ,s1 (A) γs0 ,s1 (A) + n .
A∈A

The claim now follows from Lemma 3.7 with α = 2 and the definition of p = κ4 n/r.
The next step is to estimate γs0 ,s1 (A) for our choice A = {Γv : v ∈ Vr,s1 }. We will construct
the admissible sequence As = {Γv : v ∈ Vr,s } for s0 ≤ s < s1 based on the fact that
√
k∆s Ak2→2 = kΓπs+1 v − Γπs+1v k2→2 = nkW ∆s vk∞ ,
for ∆s v = πs+1 v − πs v. Hence,
γs0 ,s1 (A) = sup

sX
1 −1

v∈Vr,s1 s=s
0

2s/2 ·

√
nkW ∆s vk∞ ,

and the admissible sequence will be constructed as maximal separated subsets of Vr,s1 with
√
respect to the norm nkW (·)k∞ .
We will require a well-known fact, due to Carl [8].
Lemma 4.9. There is an absolute constant c for which the following holds. Let w1 , . . . , wn ∈ Rn
that satisfy kwi k∞ ≤ K, put kzk = maxi∈[n] | z, wi | and set B to be the unit ball with respect
to that norm. Then for every t > 0,
√
K 2r
log N ( rB1n , tB) ≤ C 2 log2 (nt2 /r).
t
√
√
In the case we are interested in, wi = nWi and kwi k∞ ≤ β. Moreover, Vr,s1 ⊂ Vr ⊂ rB1n ;
therefore,
√
β2r
(42)
log N (Vr,s1 , tB) ≤ log N ( rB1n , tB) ≤ C 2 log2 (nt2 /r).
t
Corollary 4.10. There is an admissible sequence of Vr,s1 , for which, for every v ∈ Vr,s1 ,
√
√
nkW ∆s vk∞ ≤ cβ2−s/2 r log(en/2s ) for s ≤ s1 ,
for an absolute constant c. Therefore,
sup

sX
1 −1

v∈Vr,s1 s=s
0

2s/2 ·

√

√
nkW ∆s vk∞ ≤ c1 β rαr log(er/κ4 ).
24

(43)

Corollary 4.10 follows from (42), a straightforward computation and the definition of s0
and s1 . We omit the details.
Proof of Theorem 4.5. Combining the individual small ball estimate in (22), Theorem 4.7
and Corollary 4.10, one has that with probability at least 1 − 2−c1 (L,β)n/r , for every v ∈ Vr,s1 ,
√
kΓπs0 v ξk2 ≥ κ1 n,
and

√ √
kΓv ξk22 − kΓπs0 v ξk22 ≤ c2 (L, β) n · rαr log(c2 r).

It is straightforward verify that the latter term is bounded by (κ21 /4)n provided that r ≤
c3 (L, β)n/ log 4 n.
The more difficult step consists in exposing the regular coordinate structure of vectors in a
typical {Γv ξ : v ∈ Vr,s1 }, and we will do that by finding a suitable upper bound on
sup kΓv ξk[k] = sup

v∈Vr,s1

v∈Vr,s1

X
1/2
∗
.
( Γv ξ, ei )2

(44)

i≤k

Specifically, the next result bounds the largest possible k for which (44) is smaller than
√
(κ1 /4) n.
Lemma 4.11. Assume that 2s0 ≤ 2s1 , r ≤ c1 n/ log4 (n) and
k ≤ c2

n

.

(45)

κ1 √
n.
4

(46)

α2r log(eαr )

s0

Then with probability at least 1 − 2−c3 2

sup kΓv ξk[k] ≤

v∈Vr,s1

The constants c1 , c2 , c3 > 0 only depend on L and β.
Remark 4.12. One should note that an upper bound on the supremum in (46) cannot be
obtained via an individual estimate and the union bound. The subgaussian property of ξ is
enough to ensure that for a fixed v,


p
√ √
(EkΓv ξkp[k] )1/p ≤ cL kvk2 k log(en/k) + p nkW vk∞ .

√
√
However, because one only knows that for v ∈ Vr , nkW vk∞ ≤ β rkvk2 , individual tail
estimates suffice for a uniform bound in Vr,s0 , but not in the much larger set Vr,s1 .
Proof. Observe that
sup kΓv ξk[k] = sup sup

v∈Vr,s1

x∈Vk v∈Vr,s1

ξ, Γ∗v x .

We will study the supremum of the linear process w 7→ ξ, w indexed by the set
{Γ∗v x : v ∈ Vr,s1 , x ∈ Vk }.
25

Let (Vk,s )s≥s0 be an admissible sequence of Vk which will be specified later on.
s
For x ∈ Vk , we consider πs1 x ∈ Vk,s1 , whose cardinality is 22 1 , and πs0 x ∈ Vk,s0 , whose
s
cardinality is 22 0 and write, for v ∈ Vr,s1 ,
Γ∗v x = Γ∗v (x − πs1 x) + (Γ∗v πs1 x − Γ∗πs v πs0 x) + Γ∗πs v πs0 x .
{z
} |
|
{z 0
} | 0{z }
=:H1

=:H2

(47)

=:H3

While H3 corresponds to the “starting points” of every chain, the difference between H1 and
H2 lies in the “balance” between the contribution of Vk and Vr,s1 to each one of them. For H1 ,
s
there are ∼ 22 1 points v ∈ Vr,s1 , but for an admissible sequence for Vk one has
X
X
(Γ∗v ∆s x),
Γ∗v (πs+1 x − πs x) =
Γ∗v (x − πs1 x) =
s≥s1

s≥s1
s

and for s ≥ s1 , |{∆s x : x ∈ Vk }| ≥ 22 1 = |Vr,s1 |. Hence, it is possible to treat H1 for each
v ∈ Vr,s1 separately and apply a simple union bound. In contrast, the situation for H2 is “more
balanced”, and requires a different argument.
To deal with H1 in (47), fix v ∈ Vr,s1 and apply Lemma 3.5 for a standard Gaussian vector
G in Rn together with (21) to obtain
E sup G, t =EkΓv Gk[k]
t∈Γ∗v Vk

k
1/2
X
∗
=E
( G, Γ∗v ei )2
i=1

p
p
≤c k log(en/k) max kΓ∗v ei k2 ≤cβ k log(en/k),
i∈[n]

By the Majorizing Measures Theorem [42], there exists an admissible sequence of Vk for which
sup

∞
X

x∈Vk s=0

2s/2 kΓ∗v ∆s xk2 ∼ E sup G, t ≤ cβ
t∈Γ∗v Vk

p

k log(en/k).

Let us consider a part of that admissible sequence, namely, (Vk,s )s≥s1 . As ξ is an isotropic, Lsubgaussian random vector, it follows that for every s ≥ s1 and every x ∈ Vk , with probability
s+3
at least 1 − 2−2 ,
| ξ, Γ∗v ∆s x | ≤ cL2s/2 kΓ∗v ∆s xk2 .
s +2

Summing for s ≥ s1 , one has that with probability at least 1 − 2−2 1 , for every x ∈ Vk ,
X
X
2s/2 kΓ∗v ∆s xk2
| ξ, Γ∗v ∆s x | ≤ cL
| ξ, Γ∗v (x − πs1 x) | ≤
s≥s1

s≥s1

≤ cβL

p

κ1 √
k log(en/k)≤
n
16

(48)

for a suitable choice of c2 in (45). Repeating this argument for every v ∈ Vr,s1 and applying the
s +1
union bound, one has that with probability at least 1 − 2−2 1 , (48) holds for every v ∈ Vr,s1 .
Next, let us turn to H2 in (47). We will construct approximating subsets in the following
1
way: let (Vr,s )ss=s
be the admissible sequence of Vr,s1 used earlier, consisting of maximal
0
26

√
separated subsets with respect to the norm nkW (·)k∞ , and put νs to be the mesh width of
the net Vr,s . For every s0 ≤ s ≤ s1 and z ∈ Vr,s , let k kz be the ellipsoid norm
kxk2z

= kDW z U

∗

xk22

=n

n
X

Wℓ , z

2

2

U ℓ, x ,

ℓ=1

s

and set Ts (z) to be a maximal separated subset in Vk with respect to k kz , of cardinality 22 .
Denote its mesh width by εs (z). Thus, for s0 ≤ s < s1 , v ∈ Vr,s+1 and x ∈ Vk ,
Γv x = Γ∗v−v′ x + Γ∗v′ (x − x′ ) + Γ∗v′ x′ ,

(49)

√
where v ′ ∈ Vs,r satisfies nkW (v − v ′ )k∞ ≤ νs , and x′ ∈ Vk belongs to Ts (v ′ ) – the net of Vk
with respect to the norm k kv′ , and fulfills
(50)
kΓ∗v′ (x − x′ )k2 = kx − x′ kv′ ≤ εs (v ′ ).
S
s+1
s
s
Moreover, the cardinality of v′ ∈Vr,s Ts (v ′ ) is at most 22 · 22 ≤ 22 .
The required estimate on H2 follows from (43) and once we control εs (z) with respect to
each one of the k kz norms. Indeed, using the above notation
| ξ, Γ∗v x − ξ, Γ∗πs v π̃s x | ≤ | ξ, Γ∗v−πs v x | + | ξ, Γ∗πs v (x − π̃s x) |,
√
where, for v ∈ Vr,s+1 , πs v ∈ Vr,s is closest to v with respect to nkW (·)k∞ , x ∈ Ts+1 (v) and
π̃s x ∈ Ts (πs v) is closest to x with respect to k kπs v . Since ξ is isotropic and L-subgaussian, we
s+2
have with probability at least 1 − 22 , for every v ∈ Vr,s+1 and x ∈ Ts+1 (v),

| ξ, Γ∗v x − ξ, Γ∗πs v π̃s x | ≤cL 2s/2 kΓ∗v−πs v xk2 + 2s/2 kΓ∗πs v (x − π̃s x)k2

√
=cL 2s/2 · nkW (v − πs v)k∞ + 2s/2 kx − π̃s xkπs v

≤cL 2s/2 νs + 2s/2 sup εs (z) .
(51)
z∈Vr

Iterating (51), summing for s0 ≤ s < s1 and recalling that 2s0 = κ4 n/r, it follows that with
probability at least 1 − 2−c1 (L,β)n/r , for every v ∈ Vr,s1 and every x ∈ Vk ,
sX
1 −1
1 −1

sX
2s/2 sup εs (z) .
2s/2 νs +
| ξ, Γ∗v πs1 x − Γ∗πs v π̃s0 x) | ≤ c2 (L, β)
0

s=s0

s=s0

z∈Vr

The first sum in (52) has been estimated earlier, in (43). In particular,
c2

sX
1 −1
s=s0

√
κ1 √
2s/2 νs ≤ c3 rαr · log(c3 r) ≤
n
32

for c3 = c3 (L, β) and as long as r ≤ c4 (L, β)n/ log 4 n.
In order to bound the second sum in (52) we require another covering estimate.
Theorem 4.13. There exists an absolute constant c for which, for every z ∈ S n−1 ,
log N (Vk , k kz , ε) ≤ cβε−2 k log(en/k).
27

(52)

Proof. The proof of Theorem 4.13 is an outcome of Sudakov’s inequality. Fix z ∈ S n−1 and
define a linear operator S : Rn → Rn by Sei = U i . Observe that for i ∈ [n] and t ∈ Rn
√
√
√
nDW z S ∗ t, ei = n S ∗ t, DW z ei = n Wi , z S ∗ t, ei
√
= n Wi , z U i , t .
√
Therefore, k nDW z S ∗ tk2 = ktkz and
√
log N (Vk , k kz , ε) = log N ( nDW z S ∗ Vk , εB2n ).
√
Set T = nDW z S ∗ Vk and let G be a standard Gaussian vector in Rn . By Sudakov’s
inequality (see, e.g., [28]), there is an absolute constant c for which
cε2 log N (T, εB2n ) ≤ E sup G, t ,

(53)

t∈T

and
E sup G, t = E sup G,
t∈T

√

v∈Vk

=

√

nE sup

nDW z S ∗ v

n
X

v∈Vk i=1

gi Wi , z U i , v ≡ E

X
1/2
(Zj∗ )2
,
j≤k

√ P
for Zj = n ni=1 gi Wi , z U i , ej . Each one of the Zj ’s is a Gaussian variable, and since U
is a Hadamard type matrix with constant β,
EZj2

=n

n
X

Wi , z

2

U i , ej

2

i=1

Finally, Lemma 3.5 yields E
(53).

P
k

∗ 2
j=1 (Zj )

1/2

≤ cβ

p

≤ β2.

k log(en/k), which completes the proof by

Invoking Theorem 4.13, it follows that
p
p
sup εs (z) ≤ c β2−s/2 k log(en/k),

z∈Vr

and due to the definition of αr in (27) the second sum in (52) is bounded by
s1
X

s=s0

p
2s/2 sup ǫs (z) ≤ c(L, β)(s1 − s0 ) k log(en/k)
z∈Vr

≤ c1 (L, β)αr
provided that
k ≤ c2 (L, β)

α2r

p

k log(en/k) ≤

κ1 √
n
32

n
.
log(eαr )

This concludes the required estimate on H2 and leads to the condition on k.
28

(54)

The final and easiest component is to control H3 in (47). Indeed,
√
√
kΓ∗πs v πs0 xk2 ≤ nkWπs0 vk∞ ≤ β r,
0

s +1

s

s

and there are at most 22 0 · 22 0 = 22 0 pairs (πs0 v, πs0 x). Since ξ is isotropic and Lsubgaussian, one has that with probability at least 1 − 2 exp(−u2 /2),
√
| ξ, Γ∗πs v πs0 x | ≤ LukΓ∗πs v πs0 xk2 ≤ Luβ r.
0

0

For u = 2(s0 +2)/2 , the union bound yields that, with probability at least 1 − 2 exp(−c2s0 ),
r
√
√
n
2κ1
κ1 √
(s0 +2)/2
∗
sup
Lβ r ≤
| ξ, Γπs v πs0 x | ≤ 2
n,
· Lβ r ≤
0
16κ3 Lβ r
8
v∈Vr,s1 ,x∈Vk
because κ3 ≥ 1. Taking the union bound over the events in which the bounds for H1 , H2 and
H3 apply, we deduce that
κ1 √
sup kΓv ξk[k] ≤
n
4
v∈Vr,s1
′ s

s +1

s

with probability at least 1 − 2−c1 n/r − 2e−c2 2 0 − 2−2 1 ≥ 1 − 2−c 2 0 for a suitable constant c′ ,
under condition (54) on k. This completes the proof of Lemma 4.11 after relabelling constants.

5

The upper bound on one-sparse vectors

To complete the proof of Theorem 2.5 one has to show that with high probability,
√
max kPΩ Γei ξk2 ≤ c δn,
i∈[n]

for a suitable constant c and Ω = {i : δi = 1}, see also Theorem 2.3.
Theorem 5.1. There exist constants c0 , c1 and c2 that depend only on L and β for which the
following holds. If δ ≥ c0 logn n , then with probability at least 1 − 2 exp(−c1 δn),

1/2
n
X
√
2
δj Γei ξ, ej  ≤ c2 δn.
max 
i∈[n]

j=1

The proof of Theorem 5.1 is based on the fact that for every i ∈ [n], Γei ξ has a regular
coordinate structure, in the sense that is clarified in the following lemma.
Lemma 5.2. There exist an absolute constant c1 and a constant c2 that depends on β and L for
which the following holds. Let ξ be an isotropic, L-subgaussian random vector and let m ∈ [n].
Then for every i ∈ [n], with probability at least 1 − exp(−c1 m log(en/m)), Γei ξ = x + y, where
kxk2 ≤ c2

p

m log(en/m)

and

29

max p
i∈[n]

yi∗
log(en/i)

≤ c2 .

Proof. Let i ∈ [n] and set z = Γei ξ. Let I be the (random) set of the m largest coordinates of
z and define
X
X
x=
zj ej and y =
zj ej .
(55)
j∈I c

j∈I

Observe that kxk2 = kΓei ξk[m] . By (23) for p = m log(en/m), and noting that kW ei k∞ ≤
√
β/ n, one has
p
P r(kxk2 ≥ c(L, β) m log(en/m)) ≤ exp(−m log(en/m)).
Repeating this argument for m ≤ ℓ ≤ n, it follows that with probability at least
1−

n
X

ℓ=m

exp(−ℓ log(en/ℓ)) ≥ 1 − exp(−c1 m log(en/m)),

for every m ≤ ℓ ≤ n,

p
1
zℓ∗ ≤ √ kzk[ℓ] ≤ 2c(β, L) log(en/ℓ),
ℓ

and the claim follows.

The coordinate structure of Γei ξ comes into play thanks to a fact from [31].
Lemma 5.3. Let a ∈ Rn , set kakψ1n = max1≤j≤n a∗j / log(en/j) and put 0 < t < kakψ1n /2. Then
Pr

n
X
j=1


(δj − δ)aj > tδn ≤ 2 exp(−ct2 δn/kak2ψ1n ),

where c is an absolute constant and (δi )nj=1 are independent selectors with mean δ.
In particular, if aj = log(en/j) then with probability at least 1 − 2 exp(−c1 δn),
n
X
i=1

δj log(en/j) ≤ 5δn.

Proof of Theorem 5.1. Let m = δn/ log(e/δ) and consider the decomposition of Γei ξ =
x + y established in Lemma 5.2. Conditioned on the event from that lemma which holds with
probability at least 1 − 2 exp(−c0 δn),
n
X
j=1

δj x2j

1/2

≤

n
X
j=1

x2j

1/2

p
√
≤ c1 (L, β) m log(en/m) ≤ c2 (L, β) δn.

Also, by Lemma 5.3, with probability at least 1 − 2 exp(−c3 δn),
n
X
j=1

δj yj2 ≤ c4 (L, β)

n
X
i=1

δj log(en/j) ≤ c5 (L, β)δn.

Hence, with probability at least 1 − 2 exp(−c6 δn) with respect to both ξ and (δj )nj=1 , one has
that
n

X
√
2 1/2
≤ c7 (L, β) δn.
δj Γei ξ, ej
j=1

30

Recalling that δn ≥ c8 log n for a well chosen c8 , it follows from the union bound that with
probability at least 1 − 2n exp(−c6 δn) ≥ 1 − 2 exp(−c9 δn),
max
i∈[n]

n
X
j=1

δj Γei ξ, ej


2 1/2

√
≤ c7 (L, β) δn.

Acknowledgement
The authors would like to thank Grigoris Paouris for very valuable discussions on the subject of
this article. The authors would also like to thank Sjoerd Dirksen for pointing out a substantial
simplification for the proof of a part of our main result, as well as the anonymous referees for
their careful reading and helpful comments which greatly improved this paper. HR was partially
funded by the German Israel Foundation (GIF) through the project Analysis of structured
random measurements in recovery problems (G-1266-304.6/2014). RW was partially funded by
NSF CAREER grant #1255631. The authors acknowledge support during their stay at the
trimester program, ”Mathematics of Signal Processing” at the Hausdorff Research Institute for
Mathematics, University of Bonn in 2016, where parts of this work have been developed.

References
[1] N. Ailon and E. Liberty. Fast dimension reduction using Rademacher series on dual BCH
codes. Discr. Comput. Geom., 42(4):615–630, 2009.
[2] N. Ailon and H. Rauhut. Fast and RIP-optimal transforms. Discr. Comput. Geom.,
52(4):780–798, 2014.
[3] W. U. Bajwa, J. D. Haupt, G. M. Raz, S. J. Wright, and R. D. Nowak. Toeplitz-structured
compressed sensing matrices. In 2007 IEEE/SP 14th Workshop on Statistical Signal Processing, pages 294–298. IEEE, 2007.
[4] R. G. Baraniuk, M. Davenport, R. A. DeVore, and M. Wakin. A simple proof of the
restricted isometry property for random matrices. Constr. Approx., 28(3):253–263, 2008.
[5] J. Bourgain. An improved estimate in the restricted isometry problem. In Geometric
Aspects of Functional Analysis, pages 65–70. Springer, 2014.
[6] E. J. Candès, J., T. Tao, and J. K. Romberg. Robust uncertainty principles: exact
signal reconstruction from highly incomplete frequency information. IEEE Trans. Inform.
Theory, 52(2):489–509, 2006.
[7] E. J. Candès and T. Tao. Near optimal signal recovery from random projections: universal
encoding strategies? IEEE Trans. Inform. Theory, 52(12):5406–5425, 2006.
[8] B. Carl. Inequalities of Bernstein-Jackson-type and the degree of compactness of operators
in Banach spaces. Ann. Inst. Fourier (Grenoble), 35(3):79–118, 1985.

31

[9] V. Chandrasekaran, B. Recht, P. Parrilo, and A. S. Willsky. The convex geometry of linear
inverse problems. Found. Comput. Math., 12(6):805–849, 2012.
[10] S. S. Chen, D. L. Donoho, and M. A. Saunders. Atomic decomposition by basis pursuit.
SIAM J. Sci. Comput., 20(1):33–61, 1998.
[11] V. de la Pena and E. Giné. Decoupling. From Dependence to Independence. Probability
and its Applications (New York). Springer-Verlag, 1999.
[12] S. Dirksen, H. Jung, and H. Rauhut. One-bit compressed sensing with partial Gaussian
circulant matrices. Preprint arXiv:1710.03287, 2017.
[13] S. Dirksen, G. Lecué, and H. Rauhut. On the gap between restricted isometry properties
and sparse recovery conditions. IEEE Trans. Inform. Theory, 2016.
[14] D. L. Donoho. Compressed sensing. IEEE Trans. Inform. Theory, 52(4):1289–1306, 2006.
[15] D. L. Donoho and J. Tanner. Counting faces of randomly-projected polytopes when the
projection radically lowers dimension. J. Amer. Math. Soc., 22(1):1–53, 2009.
[16] D. Dorsch and H. Rauhut. Refined analysis of sparse MIMO radar. Journal of Fourier
Analysis and Applications, 23(3):485–529, 2017.
[17] S. Foucart, A. Pajor, H. Rauhut, and T. Ullrich. The Gelfand widths of ℓp -balls for
0 < p ≤ 1. J. Complexity, 26(6):629–640, 2010.
[18] S. Foucart and H. Rauhut. A Mathematical Introduction to Compressive Sensing. Applied
and Numerical Harmonic Analysis. Birkhäuser, 2013.
[19] J. Haupt, W. U. Bajwa, G. Raz, and R. Nowak. Toeplitz compressed sensing matrices with
applications to sparse channel estimation. IEEE Trans. Inform. Theory, 56(11):5862–5875,
2010.
[20] I. Haviv and O. Regev. The restricted isometry property of subsampled Fourier matrices. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete
Algorithms, SODA ’16, pages 288–297, 2016.
[21] M. Hügel, H. Rauhut, and T. Strohmer. Remote sensing via l1-minimization. Found.
Comput. Math., 14:115–150, 2014.
[22] D. James and H. Rauhut. Nonuniform sparse recovery with random convolutions. In Proc.
SampTA 2015, Washington, 2015.
[23] M. Kabanava and H. Rauhut. Analysis ℓ1 -recovery with frames and Gaussian measurements. Acta Appl. Math., 140(1):173–195, 2015.
[24] B. Klartag. 5n Minkowski symmetrizations suffice to arrive at an approximate Euclidean
ball. Ann. of Math. (2), 156(3):947–960, 2002.
[25] F. Krahmer, S. Mendelson, and H. Rauhut. Suprema of chaos processes and the restricted
isometry property. Comm. Pure Appl. Math., 67(11):1877–1904, 2014.
32

[26] F. Krahmer and R. Ward. New and improved Johnson-Lindenstrauss embeddings via the
restricted isometry property. SIAM Journal on Mathematical Analysis, 43(3):1269–1281,
2011.
[27] G. Lecué and S. Mendelson. Sparse recovery under weak moment assumptions. J. Eur.
Math. Soc. (JEMS), 19(3):881–904, 2017.
[28] M. Ledoux and M. Talagrand. Probability in Banach Spaces. Springer-Verlag, 1991.
[29] S. Mendelson, A. Pajor, and N. Tomczak Jaegermann. Reconstruction and subgaussian
operators in asymptotic geometric analysis. Geom. Funct. Anal., 17(4):1248–1282, 2007.
[30] S. Mendelson, A. Pajor, and N. Tomczak Jaegermann. Uniform uncertainty principle for
Bernoulli and subgaussian ensembles. Constr. Approx., 28(3):277–289, 2009.
[31] S. Mendelson and R. Vershynin. Remarks on the geometry of coordinate projections in
Rn . Israel J. Math., 140:203–220, 2004.
[32] R. Oliveira. The lower tail of random quadratic forms, with applications to ordinary least
squares and restricted eigenvalue properties. ArXiv:1312.2903, 2013.
[33] G. E. Pfander, H. Rauhut, and J. A. Tropp. The restricted isometry property for timefrequency structured random matrices. Probab. Theory Relat. Fields, (156):707–737, 2013.
[34] H. Rauhut. Circulant and Toeplitz matrices in compressed sensing. In Proc. SPARS’09,
2009.
[35] H. Rauhut. Compressive sensing and structured random matrices. In M. Fornasier, editor,
Theoretical foundations and numerical methods for sparse recovery, volume 9 of Radon
Series Comp. Appl. Math., pages 1–92. deGruyter, 2010.
[36] H. Rauhut and G. E. Pfander. Sparsity in time-frequency representations. J. Fourier
Anal. Appl., 16(2):233–260, 2010.
[37] H. Rauhut, J. K. Romberg, and J. A. Tropp. Restricted isometries for partial random
circulant matrices. Appl. Comput. Harmon. Anal., 32(2):242–254, 2012.
[38] H. Rauhut and R. Ward. Interpolation via weighted ℓ1 minimization. Appl. Comput.
Harm. Anal., 40(2):321–351, 2016.
[39] J. K. Romberg. Compressive sensing by random convolution. SIAM J. Imaging Sci.,
2(4):1098–1128, 2009.
[40] M. Rudelson and R. Vershynin. On sparse reconstruction from Fourier and Gaussian
measurements. Comm. Pure Appl. Math., 61:1025–1045, 2008.
[41] M. Rudelson and R. Vershynin. Small ball probabilities for linear images of highdimensional distributions. Internat. Math. Res. Notices, 2015(19):9594–9617, 2015.

33

[42] M. Talagrand. Upper and Lower Bounds For Stochastic Processes, volume 60 of Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in
Mathematics [Results in Mathematics and Related Areas. 3rd Series. A Series of Modern
Surveys in Mathematics]. Springer, Heidelberg, 2014.
[43] J. A. Tropp, M. B. Wakin, M. F. Duarte, D. Baron, and R. G. Baraniuk. Random filters
for compressive sampling and reconstruction. In 2006 IEEE International Conference on
Acoustics Speech and Signal Processing Proceedings, volume 3, pages III–III. IEEE, 2006.
[44] R. Vershynin. Introduction to the non-asymptotic analysis of random matrices. In Y. Eldar
and G. Kutyniok, editors, Compressed Sensing: Theory and Applications, pages 210–268.
Cambridge Univ Press, 2012.

34

