UNIVERSALITY LAWS FOR RANDOMIZED DIMENSION REDUCTION,
WITH APPLICATIONS

arXiv:1511.09433v3 [math.PR] 17 Sep 2017

SAMET OYMAK AND JOEL A. TROPP
A BSTRACT. Dimension reduction is the process of embedding high-dimensional data into a lower dimensional space to facilitate its analysis. In the Euclidean setting, one fundamental technique for dimension
reduction is to apply a random linear map to the data. This dimension reduction procedure succeeds when it
preserves certain geometric features of the set. The question is how large the embedding dimension must be
to ensure that randomized dimension reduction succeeds with high probability.
This paper studies a natural family of randomized dimension reduction maps and a large class of data
sets. It proves that there is a phase transition in the success probability of the dimension reduction map as
the embedding dimension increases. For a given data set, the location of the phase transition is the same for
all maps in this family. Furthermore, each map has the same stability properties, as quantified through the
restricted minimum singular value. These results can be viewed as new universality laws in high-dimensional
stochastic geometry.
Universality laws for randomized dimension reduction have many applications in applied mathematics,
signal processing, and statistics. They yield design principles for numerical linear algebra algorithms, for
compressed sensing measurement ensembles, and for random linear codes. Furthermore, these results
have implications for the performance of statistical estimation methods under a large class of random
experimental designs.

Date: 30 November 2015. Revised 7 August 2017 and 5 September 2017 and 14 September 2017.
2010 Mathematics Subject Classification. Primary: 60D05, 60F17. Secondary: 60B20.
Key words and phrases. Conic geometry, convex geometry, dimension reduction, invariance principle, limit theorem, random
code, random matrix, randomized numerical linear algebra, signal reconstruction, statistical estimation, stochastic geometry,
universality.

ii

S. OYMAK AND J. A. TROPP

C ONTENTS
1. Overview of the Universality Phenomenon
1.1. Randomized Dimension Reduction
1.2. Technical Setting
1.3. A Phase Transition for Uniformly Random Partial Isometries
1.4. Other Types of Random Linear Maps?
1.5. A Universality Law for the Embedding Dimension
1.6. A Universality Law for the Restricted Minimum Singular Value
1.7. Applications of Universality
1.8. The Scope of the Universality Phenomenon
1.9. Reproducible Research
1.10. Roadmap
1.11. Notation

1
1
1
1
2
4
4
5
6
7
7
8

Part I. Main Results
2. Random Matrix Models
2.1. Bounded Random Matrix Model
2.2. Heavy-Tailed Random Matrix Model
3. A Universality Law for the Embedding Dimension
3.1. Embedding Dimension: Problem Formulation
3.2. Some Concepts from Spherical Geometry
3.3. The Statistical Dimension Functional
3.4. Theorem I: Universality of the Embedding Dimension
3.5. Theorem I: Proof Strategy
3.6. Theorem I: Extensions
4. A Universality Law for the Restricted Minimum Singular Value
4.1. Restricted Minimum Singular Value: Problem Formulation
4.2. The Excess Width Functional
4.3. Theorem II: Universality for the Restricted Minimum Singular Value
4.4. Theorem II: Proof Strategy
4.5. Theorem II: Extensions

9
9
9
9
10
11
11
11
13
14
15
15
15
15
16
17
18

Part II. Applications
5. Recovery of Structured Signals from Random Measurements
5.1. The Phase Transition for Sparse Signal Recovery
5.2. Other Signal Recovery Problems
5.3. Complements
6. Decoding with Structured Errors
6.1. Decoding with Sparse Errors
6.2. Other Demixing Problems
7. Randomized Numerical Linear Algebra
7.1. Subspace Embeddings
7.2. Sketching and Least Squares
8. The Prediction Error for LASSO
8.1. The Sparse Linear Model and the LASSO
8.2. Proof of Proposition 8.1

19
19
19
22
22
23
23
26
26
26
28
31
31
33

Part III. Universality of the Restricted Minimum Singular Value: Proofs of Theorem II and
Theorem I(a)

36

UNIVERSALITY OF RANDOMIZED DIMENSION REDUCTION

9. The Restricted Singular Values of a Bounded Random Matrix
9.1. Theorem 9.1: Main Result for the Bounded Random Matrix Model
9.2. Proof of Theorem 9.1(1): Concentration
9.3. Setup for Proof of Theorem 9.1(2) and (3): Dissection of the Index Set
9.4. Proof of Theorem 9.1(2): Lower Bound for the RSV
9.5. Proof of Theorem 9.1(3): Upper Bound for the RSV of a Convex Set
10. The Restricted Singular Values of a Heavy-Tailed Random Matrix
10.1. Corollary 10.1: Main Result for the p-Moment Random Matrix Model
10.2. Proof of Theorem II from Corollary 10.1
10.3. Proof of Theorem I(a) from Corollary 10.1
11. Theorem 9.1: Concentration for Restricted Singular Values
11.1. Proposition 11.1: The Lower Tail of the RSV
11.2. Proposition 11.1: The Upper Tail of the RSV
12. Theorem 9.1: Probability Bounds for Dissections
12.1. Dissection of the Excess Width
12.2. Dissection of the Restricted Singular Value
13. Theorem 9.1: Replacing Most Entries of the Random Matrix
13.1. Proof of Proposition 13.1
13.2. Proposition 13.1: Discretizing the Index Set
13.3. Proposition 13.1: Smoothing the Minimum
13.4. Proposition 13.1: Exchanging the Entries of the Random Matrix
14. Theorem 9.1: Bounding the Restricted Singular Value by the Excess Width
14.1. Proof of Proposition 14.1
14.2. Proposition 14.1: Moment Comparison Inequality for the Hybrid RSV
14.3. Proposition 14.1: The Role of the Gaussian Minimax Theorem
14.4. Proposition 14.1: Reducing the Gaussian Matrix to Some Gaussian Vectors
14.5. Proposition 14.1: Removing the Remaining Part of the Original Random Matrix
14.6. Proposition 14.1: Replacing the Coordinates Missing from the Excess Width
15. Proof of Corollary 10.1 from Theorem 9.1 by Truncation
15.1. Proof of Corollary 10.1
15.2. Corollary 10.1: Truncation of Individual Random Variables
Part IV. Universality of the Embedding Dimension: Proof of Theorem I(b)
16. When Embedding Fails for a Bounded Random Matrix
16.1. The RAP Functional: Dual Condition for Failure
16.2. Theorem 16.2: Main Result for the Bounded Random Matrix Model
16.3. Proof of Theorem 16.2: Lower Tail Bound
16.4. Proof of Theorem 16.2: Truncation and Dissection
16.5. Proof of Theorem 16.2: Lower Bound for RAP Functional
17. When Embedding Fails for a Heavy-Tailed Random Matrix
17.1. Corollary 17.1: Main Result for the p-Moment Random Matrix Model
17.2. Proof of Theorem I(b) from Corollary 17.1
17.3. Proof of Proposition 6.1: Application of RAP functional to decoding with structured errors
18. Theorem 16.2: Truncation of the Cone
19. Theorem 16.2: Replacing Most Entries of the Random Matrix
19.1. Proof of Proposition 19.1
19.2. Proposition 19.1: Discretizing the Index Sets
19.3. Proposition 19.1: Smoothing the Minimum
19.4. Proposition 19.1: Exchanging the Entries of the Random Matrix
20. Theorem 16.2: Bounding the RAP Functional by the Excess Width

iii

36
36
36
37
37
38
39
39
39
40
41
41
42
43
43
44
45
45
46
47
47
52
53
53
54
57
58
59
59
59
60
63
63
63
63
64
64
64
65
65
66
66
67
68
68
69
69
69
70

iv

S. OYMAK AND J. A. TROPP

20.1.
20.2.
20.3.
20.4.

Proof of Proposition 20.1
Proposition 20.1: Duality for the RAP Functional
Proposition 20.1: Reducing the Gaussian Matrix to Some Gaussian Vectors
Proposition 20.1: Finding the Gaussian Width

Part V. Back Matter
Appendix A. Tools from Gaussian Analysis
A.1. Concentration for Gaussian Lipschitz Functions
A.2. The Gaussian Minimax Theorem
Appendix B. Spectral Bounds for Random Matrices
Acknowledgments
References

71
71
72
72
79
79
79
79
80
81
81

L IST OF F IGURES
1.1 Geometry of a Random Linear Map

2

1.2 Universality of the Embedding Dimension

3

1.3 Geometry of the Restricted Minimum Singular Value

4

1.4 Universality of the Restricted Minimum Singular Value

5

1.5 Non-Universality of the `1 Restricted Minimum Singular Value

7

1.6 Non-Universality of the Restricted Maximum Singular Value

8

5.1 Universality of the `1 Recovery Phase Transition

20

6.1 Universality of the `1 Decoding Phase Transition

24

8.1 Universality of the LASSO Prediction Error

32

UNIVERSALITY OF RANDOMIZED DIMENSION REDUCTION

1

1. O VERVIEW OF THE U NIVERSALITY P HENOMENON
This paper concerns a fundamental question in high-dimensional stochastic geometry:
(Q1) Is it likely that a random subspace of fixed dimension does not intersect a given set?
This problem has its roots in the earliest research on spherical integral geometry [San52, San76], and
it also arises in asymptotic convex geometry [Gor88]. In recent years, this question has attracted fresh
attention [Don06c, RV08, Sto09, DT09b, CRPW12, ALMT14, Sto13, MT13, OH13, OTH13, TOH15, TAH15]
because it is central to the analysis of randomized dimension reduction.
This paper establishes that a striking universality phenomenon takes place in the stochastic geometry
problem (Q1). For a given set, the answer to this question is essentially the same for every distribution on
random subspaces that is induced by a natural model for random linear maps. Universality also manifests
itself in metric variants of (Q1), where we ask how far the random subspace lies from the set. We discuss
the implications of these results in high-dimensional geometry, random matrix theory, numerical analysis,
optimization, statistics, signal processing, and beyond.
1.1. Randomized Dimension Reduction. Dimension reduction is the operation of mapping a set from a
large space into a smaller space. Ideally, this action distills the “information” in the set, and it allows us to
develop more efficient algorithms for processing that information. In the setting of Euclidean spaces, a
fundamental method for dimension reduction is to apply a random linear map to each point in the set. It
is important that the random linear map preserve geometric features of the set. In particular, we do not
want the linear map to map a point in the set to the origin. Equivalently, the null space of the random
linear map should not intersect the set. We see that (Q1) emerges naturally in the context of randomized
dimension reduction.
1.2. Technical Setting. Let us introduce a framework in which to study this problem. It is natural to treat
(Q1) as a question in spherical geometry because it is scale invariant. Fix the ambient dimension D, and
consider a closed subset Ω of the Euclidean unit sphere in RD . For the moment, we also assume that Ω is
spherically convex; that is, Ω is the intersection of a convex cone1 with the unit sphere. Construct a random
linear map Π : RD → Rd , where the embedding dimension d does not exceed the ambient dimension D. As
we vary the distribution of the random linear map Π, the map Π 7→ null(Π) induces different distributions
on the subspaces in RD with codimension at most d . We may now reformulate (Q1) in this language:
(Q2) For a given embedding dimension d , what is the probability that Ω ∩ null(Π) = ;? Equivalently,
what is the probability that 0 ∉ Π(Ω)?
We say that the random projection succeeds when 0 ∉ Π(Ω). Conversely, when 0 ∈ Π(Ω), we say that the
random projection fails. See Figure 1.1 for an illustration.
We have the intuition that, for a fixed choice of Ω, the projection is more likely to succeed as the
embedding dimension d increases. Furthermore, a random linear map Π with fixed embedding dimension
d is less likely to succeed as the size of the set increases. We will justify these heuristics in complete detail.
1.3. A Phase Transition for Uniformly Random Partial Isometries. We begin with a case where the
literature already contains a comprehensive answer to the question (Q2).
The most natural type of random embedding is a uniformly random partial isometry. That is, Π :
RD → Rd is a partial isometry2 whose null space, null(Π), is drawn uniformly at random from the Haar
measure on the Grassmann manifold of subspaces in RD with codimension d . The invariance properties
of the distribution of Π allow for a complete analysis of its action on Ω, the spherically convex set [SW08,
Chap. 6.5]. Recent research [ALMT14, MT14a, GNP14] has shown how to convert the complicated exact
formulas into interpretable results.
1A convex cone is a convex set K that satisfies αK = K for all α > 0.
2A partial isometry Π satisfies the condition ΠΠ∗ = I, where ∗ is the transpose operation and I is the identity map.

2

S. OYMAK AND J. A. TROPP

range(P )
Ω

Ω

range(P )

P (Ω)

P (Ω)
null(P )

null(P )
F IGURE 1.1: Geometry of a Random Linear Map. We can identify a linear map Π : RD → Rd with an
orthogonal projector P : RD → RD whose range is the orthogonal complement of null(Π). In this diagram,
P : R2 → R2 is a random orthogonal projector applied to a closed, spherically convex set Ω. The likelihood
of a given configuration depends on the statistical dimension δ(Ω) of the set. L EFT: Success Regime. The
null space, null(P ), does not intersect Ω, and the image P (Ω) does not contain the origin. R IGHT: Failure
Regime. The null space, null(P ), intersects the set Ω, and the image P (Ω) contains the origin.

The modern theory is expressed in terms of a geometric functional δ(Ω), called the statistical dimension:
·µ
¶2 ¸
δ(Ω) := E max g · t
, where g is NORMAL(0, I).
t ∈Ω

+

The statistical dimension is increasing with respect to set inclusion, and its values range from zero (for the
empty set) up to D (for the whole sphere). Furthermore, the functional can be computed accurately in
many cases of interest. See Section 3.3 for more details.
The statistical dimension demarcates a phase transition in the behavior of a uniformly random partial isometry Π as the embedding dimension d varies. For a closed, spherically convex set Ω, the results [ALMT14, Thm. I and Prop. 10.2] demonstrate that
p
d ≤ δ(Ω) − C δ(Ω) implies 0 ∈ Π(Ω) with high probability;
(1.1)
p
d ≥ δ(Ω) + C δ(Ω) implies 0 ∉ Π(Ω) with high probability.
The number C is a positive universal constant. In other terms, a uniformly random projection Π(Ω) of a
spherically convex set Ω is likely to succeed precisely when the embedding dimension d is larger than
the statistical dimension δ(Ω). See Figure 1.2 for a plot of the exact probability that a uniformly random
partial isometry annihilates a point in a specific set Ω.
Remark 1.1 (Related Work). The results [ALMT14, Thm. 7.1] and [MT13, Thm. A] contain good bounds
for the probabilities in (1.1). The probabilities can be approximated more precisely by introducing a
second geometric functional [GNP14]. These estimates depend on the spherical Crofton formula [SW08,
Eqns. (6.62), (6.63)], which gives the exact probabilities in a less interpretable form. Related phase
transition results can also be obtained via the Gaussian Minimax Theorem; see [Gor88, Cor. 3.4], [ALMT14,
Rem. 2.9], [Sto13], or [TOH15, Thm. II.1]. See [TH15] for other results on uniformly random partial
isometries.
1.4. Other Types of Random Linear Maps? The research outlined in Section 1.3 delivers a complete
account of how a uniformly random partial isometry behaves in the presence of some convexity. In

UNIVERSALITY OF RANDOMIZED DIMENSION REDUCTION

3

Probability of Success, Random Embedding of Nonnegative Unit Vectors in R 64
1
0.9

Probability of Success

0.8

Uniformly Random (theory)
Rademacher (empirical)
20% Nonzero Rademacher (empirical)
Student t with 5 dof (empirical)

0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

20

25

30

35

Embedding Dimension (d)

40

45

F IGURE 1.2: Universality of the Embedding Dimension. This plot describes the behavior of four types
of random linear maps applied to the set Ω of unit vectors with nonnegative coordinates: Ω := {t ∈ R64 :
kt k = 1, t i ≥ 0}. The dashed line marks the statistical dimension of the set: δ(Ω) = 32. The gray curve
interpolates the exact probability that a uniformly random partial isometry Π : R64 → Rd succeeds (i.e.,
0 ∉ Π(Ω)) as a function of the embedding dimension d . The markers indicate the empirical probability
(over 100 trials) that dimension reduction succeeds for a random linear map with the specified distribution.
See Sections 1.4 and 1.9 for further details.

contrast, the literature contains almost no precise information about the behavior of other random linear
maps.
Nevertheless, in applications, we may prefer—or be forced—to work with other types of random linear
maps. Here is a motivating example. Many algorithms for numerical linear algebra now depend on
randomized dimension reduction. In this context, uniformly random partial isometries are expensive to
construct, to store, and to perform arithmetic with. It is more appealing to implement a random linear
map that is discrete, or sparse, or structured. The lack of detailed theoretical information about how these
linear maps behave makes it difficult to design numerical methods with guaranteed performance.
We can, however, use computation to investigate the behavior of other types of random linear maps.
Figure 1.2 presents the results of the following experiment. Consider the set Ω of unit vectors in R64 with
nonnegative coordinates:
©
ª
Ω := t ∈ R64 : kt k = 1 and t i ≥ 0 for i = 1, . . . , 64 .
According to (3.6), below, the statistical dimension δ(Ω) = 32, so the formula (1.1) tells us to expect a phase
transition in the behavior of a uniformly random partial isometry when the embedding dimension d = 32.
Using [ALMT14, Ex. 5.3 and Eqn. (5.10)], we can compute the exact probability that a uniformly random
partial isometry Π : R64 → Rd succeeds as a function of d . Against this baseline, we compare the empirical
probability (over 100 trials) that a random linear map with independent Rademacher3 entries succeeds.
We also display experiments for a 20% nonzero Rademacher linear map and for a linear map with Student
t 5 entries. See Section 1.9 for more details.
From this experiment, we discover that all three linear maps act almost exactly the same way as
a uniformly random partial isometry! This universality phenomenon is remarkable because the four
3A Rademacher random variable takes the two values ±1 with equal probability.

4

S. OYMAK AND J. A. TROPP

null(P )
E

range(P )

σmin (P ; E )
P (E )

F IGURE 1.3: Geometry of the Restricted Minimum Singular Value. We can identify a partial unitary linear
map Π : RD → Rd with an orthogonal projector P : RD → RD whose range is the orthogonal complement of
null(Π). In this diagram, P : R2 → R2 is an orthogonal projector applied to a compact convex set E . The
restricted minimum singular value σmin (P ; E ) is the distance from the origin to the image P (E ).

linear maps have rather different distributions. At present, the literature contains no information about
when—or why—this phenomenon occurs.
1.5. A Universality Law for the Embedding Dimension. The central goal of this paper is to show that
there is a substantial class of random linear maps for which the phase transition in the embedding
dimension is universal. Here is a rough statement of the main result.
Let Ω be a closed, spherically convex set in RD . Suppose that the entries of the matrix of the random
linear map Π : RD → Rd are independent, standardized,4 and symmetric,5 with a modest amount of
regularity.6 In particular, we may consider random linear maps that have an arbitrarily small, but constant,
proportion of nonzero entries. For this class of random linear maps, we will demonstrate that
d ≤ δ(Ω) − o(D) implies 0 ∈ Π(Ω) with high probability;
d ≥ δ(Ω) + o(D) implies 0 ∉ Π(Ω) with high probability.

(1.2)

The little-o notation suppresses constants that depend only on the regularity of the random variables that
populate Π. See Theorem I in Section 3.4 for a more complete statement.
The result (1.2) states that a random linear map Π is likely to succeed for a spherically convex set Ω
precisely when the embedding dimension d exceeds the statistical dimension δ(Ω) of the set. We learn
that the phase transition in the embedding dimension is universal over our class of random linear maps,
provided that Ω is not too small as compared with the ambient dimension D. Note that a random linear
map Γ : RD → Rd with standard normal entries has the same behavior as a d × D uniformly random
partial isometry because, almost surely, the null space of Γ is a uniformly random subspace of RD with
codimension d . This analysis explains the dominant features of the experiment in Figure 1.2!
1.6. A Universality Law for the Restricted Minimum Singular Value. It is also a matter of significant
interest to understand the stability of randomized dimension reduction. We quantify the stability of the
random linear map Π : RD → Rd on a compact, convex set E in RD using the restricted minimum singular
value:
σmin (Π; E ) := min kΠt k .
t ∈E

4A standardized random variable has mean zero and variance one.
5A symmetric random variable X has the same distribution as its negation −X .
6

For concreteness, we may assume that the entries of Π have five uniformly bounded moments.

UNIVERSALITY OF RANDOMIZED DIMENSION REDUCTION

5

Restricted Minimum Singular Value

Restricted Minimum Singular Value, Random Embedding of Probability Simplex in R
0.5

64

d-Excess Width (asymptotic theory)
Rademacher (empirical)
20% Nonzero Rademacher (empirical)
Student t with 5 dof (empirical)

0.4

0.3

0.2

0.1

0

20

25

30

35

40

45

Embedding Dimension (d)

50

55

60

F IGURE 1.4: Universality of the Restricted Minimum Singular Value. This plot describes the behavior of
P
three types of random linear maps applied to the probability simplex ∆64 := {t ∈ R64 : i t i = 1, t i ≥ 0}. The
dashed line marks the minimum dimension d = 32 where uniformly random¡embedding
of the set ∆64
¢
is likely to succeed. The gray curve interpolates the value of the positive part Ed (∆64 ) + of the d -excess
width of ∆64 , obtained from the asymptotic calculation (4.4). The markers give an empirical estimate (over
100 trials) for the restricted minimum singular value σmin (Π; ∆64 ) of a random linear map Π : R64 → Rd
drawn from the specified distribution. See Section 1.9 for more information.

When the restricted minimum singular value σmin (Π; E ) is large, the random image Π(E ) is far from the
origin, so the embedding is very stable. That is, we can deform either the linear map Π or the set E and
still be sure that the embedding succeeds. When the restricted minimum singular value is small, the
random dimension reduction map is unstable. When it is zero, the random dimension reduction map
fails. See Figure 1.3 for a diagram.
Our second major theorem is a universality law for the restricted minimum singular values of a random
linear map. This result is expressed using a geometric functional Ed (E ), called the d -excess width of E :
¢
¡p
Ed (E ) := E min d kt k + g · t , where g is NORMAL(0, I).
t ∈E

The d -excess width increases
p with the parameter d , and it decreases with respect to set inclusion. The
typical scale of Ed (E ) is O( d ). In addition, the excess width can be evaluated precisely in many situations
of interest. See Section 4.2 for more details.
Now, suppose that the entries of the matrix of Π : RD → Rd are independent, standardized, and
symmetric, with a modest amount of regularity. For a compact, convex subset E of the unit ball in RD , we
will establish that
p
¡
¢
σmin (Π; E ) = Ed (E ) + + o( d ) with high probability.
(1.3)
The little-o notation suppresses constants that depend only on the regularity of the random variables.
Theorem II in Section 4.3 contains a more detailed statement of (1.3).
In summary, provided that the set E is not too small, the restricted minimum singular value σmin (Π; E )
depends primarily on the geometry of the set E and the embedding dimension d , rather than on the
distribution of the random linear map Π. See Figure 1.4 for a numerical illustration of this fact.
1.7. Applications of Universality. Randomized dimension reduction and, more generally, random matrices have become ubiquitous in the information sciences. As a consequence, the universality laws that we
outlined in Section 1.5 and 1.6 have a wide range of implications.

6

S. OYMAK AND J. A. TROPP

Signal Processing: The main idea in the field of compressed sensing is that we can acquire information
about a structured signal by taking random linear measurements. The literature contains extensive
empirical evidence that many types of random measurements behave in an indistinguishable
fashion. Our work gives the first explanation of this phenomenon. (Section 5)
Stochastic Geometry: Our results also indicate that the facial structure of the convex hull of independent
random vectors, drawn from an appropriate class, does not depend heavily on the distribution.
(Section 5.3.1)
Coding Theory: Random linear codes provide an efficient way to protect transmissions against error. We
demonstrate that a class of random codes is resilient against sparse corruptions. The number of
errors that can be corrected does not depend on the specific choice of codebook. (Section 6)
Numerical Analysis: Our research provides an engineering design principle for numerical algorithms
based on randomized dimension reduction. We can select the random linear map that is most
favorable for implementation and still be confident about the detailed behavior of the algorithm.
This approach allows us to develop efficient numerical methods that also have rigorous performance guarantees. (Section 7)
Random Matrix Theory: Our work leads to a new proof of the Bai–Yin law for the minimum singular
value of a random matrix with independent entries. (Section 7.1)
High-Dimensional Statistics: The LASSO is a widely used method for performing regression and variable
selection. We demonstrate that the prediction error associated with a LASSO estimator is universal
across a large class of random designs and statistical error models. We also show that leastabsolute-deviation (LAD) regression can correct a small number of arbitrary statistical errors for a
wide class of random designs. (Section 8 and Remark 6.2)
Neuroscience: Our universality laws may even have broader scientific significance. It has been conjectured, with some experimental evidence, that the brain may use dimension reduction to compress
information [GG15]. Our universality laws suggest that many types of uncoordinated (i.e., random)
activity lead to dimension reduction methods with the same behavior. This result indicates that
the hypothesis of neural dimensionality reduction may be biologically plausible.
1.8. The Scope of the Universality Phenomenon. The universality phenomenon developed in this paper
extends beyond the results that we establish, but there are some (apparently) related problems where
universality does not hold. Let us say a few words about these examples and non-examples.
First, it does not appear important that the random linear map Π has independent entries. There
is extensive evidence that structured random linear maps also have some universality properties; for
example, see [DT09a].
Second, the restricted minimum singular value is not the only type of functional where universality is
visible. For instance, suppose that f is a convex, Lipschitz function. Consider the quantity
¡
¢
min kΠt k2 + f (t ) .
t ∈E

Optimization problems of this form play a central role in contemporary statistics and machine learning.
It is likely that the value of this optimization problem is universal over a wide class of random linear maps.
Furthermore, we believe that our techniques can be adapted to address this question. On the other hand,
geometric functionals involving non-Euclidean norms need not exhibit universality. Consider the `1
restricted minimum singular value
(1.4)
min kΠt k`1 .
t ∈E

There are nontrivial sets E where the value of the optimization problem (1.4) varies a lot with the choice
of the random linear map Π. For instance, let e1 ∈ RD be the first standard basis vector, and define the
shifted Euclidean ball
©
ª
E α := t ∈ RD : kt − e1 k ≤ α for 0 ≤ α ≤ 1.

UNIVERSALITY OF RANDOMIZED DIMENSION REDUCTION

7

l1 Restricted Minimum Singular Value, Random Embedding of Shifted Euclidean Ball in R
Rademacher (empirical)
Gaussian (empirical)
Student t with 5 dof (empirical)
20% Nonzero Rademacher (empirical)

20

l1 Restricted Minimum Singular Value

64

15

10

5

0

0

10

20

30

40

Embedding Dimension (d)

50

60

F IGURE 1.5: Non-Universality of the `1 Restricted Minimum Singular Value. This plot describes the behavior of four types of random linear maps applied to the set E 1/2 := {t ∈ R64 : kt − e1 k ≤ 1/2}, where e1 is the
first standard basis vector. The dashed line stands at the phase transition d ≈ 16 for the embedding dimension of the set E 1/2 . The markers give an empirical estimate (over 100 trials) for the `1 restricted minimum
singular value mint ∈E 1/2 kΠt k`1 of a random linear map Π : R64 → Rd with the specified distribution as a
function of the embedding dimension d . See Section 1.9 for more details.

Using Theorem I and the calculation [ALMT14, Sec. 3.4] of the statistical dimension of a circular cone,
we can verify that there is a universal phase transition for successful embedding of the set E α when the
embedding dimension d = α2 D + O(1). The result (1.3) implies that the minimum restricted singular
value of E α also takes a universal value. At the same time, Figure 1.5 illustrates that the functional (1.4) is
not universal for the set E α .
Finally, functionals involving maximization do not necessarily exhibit universality. The restricted
maximum singular value is defined as
σmax (Π; E ) := max kΠt k .
t ∈E

It is not hard to produce examples where the restricted maximum singular value depends on the choice
of the random matrix Π. For instance, Figure 1.6 demonstrates that the random linear map Π has a
substantial impact on the maximum singular value σmax (Π; ∆D ) restricted to the probability simplex
∆D in RD . This observation may surprise researchers in random matrix theory because the ordinary
maximum singular value is universal over the class of random matrices with independent entries [BS10,
Thm. 3.10].
1.9. Reproducible Research. This paper is accompanied by MATLAB code [Tro15a] that reproduces each
figure from stored data. This software can also repeat the numerical experiments to obtain new instances
of each figure. By modifying the parameters in the code, the reader may explore how changes affect the
universality phenomenon. We omit meticulous descriptions of the numerical experiments from the text
because these recitations are tiresome for the reader and the code offers superior documentation.
1.10. Roadmap. This paper is divided into five parts. Part I offers a complete presentation of our universality laws, some comments about the proofs, and some prospects for further research. Part II outlines
the applications of universality in several disciplines, and it contains more empirical confirmation of
our analysis. Part III presents the proof that the restricted minimum singular value exhibits universal

8

S. OYMAK AND J. A. TROPP

Restricted Maximum Singular Value

Restricted Maximum Singular Value, Random Embedding of Probability Simplex in R64
10
8
6
4
Student t with 5 dof (empirical)
20% Nonzero Rademacher (empirical)
Gaussian (empirical)
Rademacher (empirical)

2
0

0

10

20

30

40

Embedding Dimension (d)

50

60

F IGURE 1.6: Non-Universality of the Restricted Maximum Singular Value. This plot describes the behavior
P
of four types of random linear maps applied to the probability simplex ∆64 := {t ∈ R64 : i t i = 1, t i ≥ 0}. The
markers give an empirical estimate (over 100 trials) for the restricted maximum singular value σmax (Π; ∆64 )
of a random linear map Π : R64 → Rd with the specified distribution. See Section 1.9 for more details.

behavior; this argument also yields the condition in which randomized embedding is likely to succeed.
Part IV contains the proof of the condition in which randomized embedding is likely to fail. Finally, Part V
includes background results, the acknowledgments, and the list of works cited.
1.11. Notation. Let us summarize our notation. We use italic lowercase letters (for example, a) for scalars,
boldface lowercase letters (a) for vectors, and boldface uppercase letters (A) for matrices. Uppercase italic
letters (A) may denote scalars, sets, or random variables, depending on the context. Roman letters (c, C)
denote universal constants that may change from appearance to appearance. We sometimes delineate
specific constant values with subscripts (Crad ).
Given a vector a and a set J of indices, we write a J for the vector restricted to those indices. In particular,
a j is the j th coordinate of the vector. Given a matrix A and sets I and J of row and column indices, we
write A I J for the submatrix indexed by I and J . In particular, a i j is the component in the (i , j ) position of
A. If there is a single index A J , it always refers to the column submatrix indexed by J .
We always work in a real Euclidean space. The symbol Bn is the unit ball in Rn , and Sn−1 is the unit
sphere in Rn . The unadorned norm k·k refers to the `2 norm of a vector or the `2 operator norm of a
matrix. We use the notation s · t for the standard inner product of vectors s and t with the same length.
We write ∗ for the transpose of a vector or a matrix.
For a real number a, we define the positive-part and negative-part functions:
(a)+ := max{a, 0} and (a)− := max{−a, 0}.
These functions bind before powers, so (a)2+ is the square of the positive part of a.
The symbols E and Var refer to the expectation and variance of a random variable, and P {·} returns the
probability of an event. We use the convention that powers bind before the expectation, so E X 2 returns
the expectation of the square. We write 1 A for the 0–1 indicator random variable of the event A.
A standardized random variable has mean zero and variance one. A symmetric random variable X has
the same distribution as its negation −X . We reserve the letter γ for a standard normal random variable;
the boldface letters γ, g , h are always standard normal vectors; and Γ is a standard normal matrix. The
dimensions are determined by context.

UNIVERSALITY OF RANDOMIZED DIMENSION REDUCTION

9

Part I. Main Results
This part of the paper introduces two new universality laws, one for the phase transition in the embedding dimension and a second one for the restricted minimum singular values of a random linear map. We
also include some high-level remarks about the proofs, but we postpone the details to Parts III and IV.
In Section 2, we introduce two models for random linear maps that we use throughout the paper.
Section 3 presents the universality result for the embedding dimension, and Section 4 presents the result
for restricted singular values.
2. R ANDOM M ATRIX M ODELS
To begin, we present two models for random linear maps that arise in our study of universality. One
model includes bounded random matrices with independent entries, while the second allows random
matrices with heavy-tailed entries.
2.1. Bounded Random Matrix Model. Our first model contains matrices whose entries are uniformly
bounded. This model is useful for some applications, and it plays a central role in the proofs of our
universality results.
Model 2.1 (Bounded Matrix Model). Fix a parameter B ≥ 1. A random matrix in this model has the
following properties:
•
•
•
•

Independence. The entries are stochastically independent random variables.
Standardization. Each entry has mean zero and variance one.
Symmetry. Each entry has a symmetric distribution.
Boundedness. Each entry X of the matrix is uniformly bounded: |X | ≤ B .

Identical distribution of entries is not required. In some cases, which we will note, the symmetry requirement can be dropped.
This model includes several types of random matrices that appear frequently in practice.
Example 2.2 (Rademacher Matrices). Consider a random matrix whose entries are independent, Rademacher random variables. This type of random matrix meets the requirements of Model 2.1 with B = 1.
Rademacher matrices provide the simplest example of a random linear map. They are appealing for many
applications because they are discrete.
Example 2.3 (Sparse Rademacher Matrices). Let α ∈ (0, 1] be a thinning parameter. Consider a random
variable X with distribution
 −1/2
, with probability α/2;

+α
X=

−α−1/2 , with probability α/2;


0,
otherwise.

A random matrix whose entries are independent copies of X satisfies Model 2.1 with B = α−1/2 . These
random matrices are useful because we can control the sparsity.
2.2. Heavy-Tailed Random Matrix Model. Next, we introduce a more general class of random matrices
that includes heavy-tailed examples. Our main results concern random linear maps from this model.
Model 2.4 (p-Moment Model). Fix parameters p > 4 and ν ≥ 1. A random matrix in this model has the
following properties:
•
•
•
•

Independence. The entries are stochastically independent random variables.
Standardization. Each entry has mean zero and variance one.
Symmetry. Each entry has a symmetric distribution.
Bounded Moments. Each entry X has a uniformly bounded pth moment: E |X |p ≤ νp .

Identical distribution of entries is not required.

10

S. OYMAK AND J. A. TROPP

Model 2.4 subsumes Model 2.1, but it also encompasses many other types of random matrices.
Example 2.5 (Gaussian Matrices). Consider an m × n random matrix Γ whose entries are independent,
standard normal random variables. The matrix Γ satisfies the requirements of Model 2.4 for each p > 4
p
with ν ≤ p.
In some contexts, we can use a Gaussian random matrix to study the behavior of a uniformly random
partial isometry. Indeed, the null space, null(Γ), of the standard normal matrix is a uniformly random
subspace of Rn with codimension min{m, n}, almost surely.
Model 2.4 contains several well-studied classes of random matrices.
Example 2.6 (Subgaussian Matrices). Suppose that the entries of the random matrix are independent,
and each entry X is symmetric, standardized, and uniformly subgaussian. That is, there is a parameter
α > 0 where
¡
¢1/p
p
E |X |p
≤ α p for all p ≥ 1.
p
These matrices are included in Model 2.4 for each p > 4 with ν ≤ α p. Rademacher, sparse Rademacher,
and Gaussian matrices fall in this category.
Example 2.7 (Log-Concave Entries). Suppose that the entries of the random matrix are independent, and
each entry X is a symmetric, standardized, log-concave random variable. Recall that a real log-concave
random variable X has a density f of the form
f (x) :=

1 −h(x)
e
Z

where h : R → R is convex and Z is a normalizing constant. It can be shown [BGVV14, Thm. 2.4.6] that
these matrices are included in Model 2.4 for any p > 4.
In contrast with most research on randomized dimension reduction, we allow the random linear map
to have entries with heavy tails. Here is one such example.
Example 2.8 (Student t Matrices). Suppose that each entry of the random matrix is an independent
Student t random variable with α degrees of freedom, for α > 4. This matrix also follows Model 2.4 for
each p < α.
Finally, we present a general construction that takes a matrix from Model 2.4 and produces a sparse
matrix that also satisfies the model, albeit with a larger value of the parameter ν.
Example 2.9 (Sparsified Random Matrix). Let Φ be a random matrix that satisfies Model 2.4 for some
value p > 4 and ν ≥ 1. Let α ∈ (0, 1] be a thinning parameter, and construct a new random matrix Φ(α)
whose entries ϕ(α)
are independent random variables with the distribution
ij
ϕ(α)
ij

=

(
α−1/2 ϕi j , with probability α

0,

with probability 1 − α.

Then the sparsified random matrix Φ(α) still follows Model 2.4 with the same value of p and with a
modified value ν0 of the other parameter: ν0 = α−1/p ν.

3. A U NIVERSALITY L AW FOR THE E MBEDDING D IMENSION
In this section, we present detailed results which show that, for a large class of sets, the embedding
dimension is universal over a large class of linear maps.

UNIVERSALITY OF RANDOMIZED DIMENSION REDUCTION

11

3.1. Embedding Dimension: Problem Formulation. Let us begin with a more rigorous statement of the
problem.
• Fix the ambient dimension D.
• Let E be a nonempty, compact subset of RD that does not contain the origin.
• Let Π : RD → Rd be a random linear map with embedding dimension d .
We are interested in understanding the probability that the random projection Π(E ) does not contain the
origin. That is, we want to study the following predicate:
0 ∉ Π(E ) or, equivalently, E ∩ null(Π) = ;.

(3.1)

We say that the random projection succeeds when the property (3.1) holds; otherwise, the random projection fails.
Our goal is to argue that there is a large class of sets and a large class of random linear maps where
the probability that (3.1) holds depends primarily on the choice of the embedding dimension d and an
appropriate measure of the size of the set E . In particular, the probability does not depend significantly
on the distribution of the random linear map Π.
3.2. Some Concepts from Spherical Geometry. The property (3.1) does not reflect the scale of the points
in the set E . As a consequence, it is appropriate to translate the problem into a question about spherical
geometry. We begin with a definition.
Definition 3.1 (Spherical Retraction). The spherical retraction map θ : RD → RD is defined as
(
t / kt k , t 6= 0
θ(t ) :=
0,
t = 0.
For every set E in RD , we have the equivalence
0 ∉ Π(E ) if and only if 0 ∉ Π(θ(E )).

(3.2)

Therefore, we may pass to the spherical retraction θ(E ) of the set E without loss of generality.
To obtain a complete analysis of when random projection succeeds or fails, we must restrict our
attention to sets that have a convexity property.
Definition 3.2 (Spherical Convexity). A nonempty subset Ω of the unit sphere in RD is spherically convex
when the pre-image θ −1 (Ω) ∪ {0} is a convex cone. By convention, the empty set is also spherically convex.
In particular, suppose that T is a compact, convex set that does not contain the origin. Then the retraction
θ(T ) is compact and spherically convex.
Next, we introduce a polarity operation for spherical sets that supports some crucial duality arguments.
Definition 3.3 (Spherical Polarity). Let Ω be a subset of the unit sphere SD−1 in RD . The polar of Ω is the
set
©
ª
Ω◦ := x ∈ SD−1 : x · t ≤ 0 for all t ∈ Ω .
By convention, the polar of the empty set is the whole sphere: ;◦ := SD−1 .
This definition is simply the spherical analog of polarity for cones. It can be verified that Ω◦ is always
closed and spherically convex. Furthermore, the polarity operation is an involution on the class of closed,
spherically convex sets in SD−1 .
3.3. The Statistical Dimension Functional. We have the intuition that, for a given compact subset E of
RD , the probability that a random linear map Π : RD → Rd succeeds decreases with the “content” of the
set E . In the present context, the correct notion of content involves a geometric functional called the
statistical dimension.

12

S. OYMAK AND J. A. TROPP

Definition 3.4 (Statistical Dimension). Let Ω be a nonempty subset of the unit sphere in RD . The statistical
dimension δ(Ω) is defined as
h³
´2 i
δ(Ω) := E sup g · t
(3.3)
t ∈Ω

+

In addition, define δ(;) := 0. We extend the statistical dimension to a general subset T in RD using the
spherical retraction:
δ(T ) := δ(θ(T )).

(3.4)

D

Recall that the random vector g ∈ R has the standard normal distribution.
The statistical dimension has a number of striking properties. We include a short summary; see [ALMT14,
Prop. 3.1] and the citations there for further information.
• For a set T in RD , the statistical dimension δ(T ) takes values in the range [0, D].
• The statistical dimension is increasing with respect to set inclusion: S ⊂ T implies that δ(S) ≤ δ(T ).
• The statistical dimension agrees with the linear dimension on subspaces:
δ(L) = dim(L) for each subspace L in RD .
• The statistical dimension interacts nicely with polarity:
δ(Ω◦ ) = D − δ(Ω) for each spherically convex set Ω ∈ RD .

(3.5)

The same relation holds if we replace Ω by a convex cone K in RD and use conic polarity.
As a specific example of (3.5), we can evaluate the statistical dimension of the nonnegative orthant RD
+.
Indeed, the orthant is a self-dual cone, so
δ(RD
+ ) = D/2.

(3.6)

There is also powerful machinery, developed in [Sto09, OH10, CRPW12, ALMT14, FM14], for computing
the statistical dimension of a descent cone of a convex function. Finally, we mention that the statistical
dimension can often be evaluated by sampling Gaussian vectors and approximating the expectation
in (3.3) with an empirical average.
Remark 3.5 (Gaussian Width). The statistical dimension is related to the Gaussian width functional. For
a bounded set T in RD , the Gaussian width W (T ) is defined as

W (T ) := E sup g · t .

(3.7)

t ∈T

For a subset Ω of the unit sphere in RD , we have the inequalities

W 2 (Ω) ≤ δ(Ω) ≤ W 2 (Ω) + 1.

(3.8)

See [ALMT14, Prop. 10.3] for a proof. The relation (3.8) allows us to pass between the squared width and
the statistical dimension.
The Gaussian width of a set is closely related to its mean width [Ver15, Sec. 1.3.5]. The mean width is
a canonical functional in the Euclidean setting [Gru07, Sec. 7.3], but it is not quite the right choice for
spherical geometry. We have chosen to work with the statistical dimension because it has many geometric
properties that the width lacks in the spherical setting.
Remark 3.6 (Convex Cones). The papers [ALMT14, MT14a] define the statistical dimension of a convex
cone using intrinsic volumes. It can be shown that the statistical dimension is the canonical (additive,
continuous) extension of the linear dimension to the class of closed convex cones [ALMT14, Sec. 5.6]. Our
general definition (3.4) agrees with the original definition on this class.

UNIVERSALITY OF RANDOMIZED DIMENSION REDUCTION

13

3.4. Theorem I: Universality of the Embedding Dimension. We are now prepared to state our main
result on the probability that a random linear map succeeds or fails for a given set.
Theorem I (Universality of the Embedding Dimension). Fix the parameters p > 4 and ν ≥ 1 for Model 2.4.
Choose parameters % ∈ (0, 1) and ε ∈ (0, 1). There is a number N := N (p, ν, %, ε) for which the following
statement holds. Suppose that
•
•
•
•

The ambient dimension D ≥ N .
E is a nonempty, compact subset of RD that does not contain the origin.
The statistical dimension of E is proportional to the ambient dimension: δ(E ) ≥ %D.
The d × D random linear map Π obeys Model 2.4 with parameters p and ν.

Then
d ≥ (1 + ε) δ(E ) implies P {0 ∉ Π(E )} ≥ 1 − Cp D 1−p/4 .

(a)

Furthermore, if θ(E ) is spherically convex, then
d ≤ (1 − ε) δ(E ) implies P {0 ∈ Π(E )} ≥ 1 − Cp D 1−p/4 .

(b)

The constant Cp depends only on the parameter p in the random matrix model.
Section 3.5 summarizes our strategy for establishing Theorem I. The detailed proof of Theorem I(a)
appears in Section 10.3; the detailed proof of Theorem I(b) appears in Section 17.2. Let us mention that
stronger probability bounds hold when the random linear map is drawn from Model 2.1.
For any random linear map Π drawn from Model 2.4, Theorem I(a) ensures that the random dimension
reduction Π(E ) is likely to succeed when the embedding dimension d exceeds the statistical dimension
δ(E ). Similarly, Theorem I(b) shows that Π(E ) is likely to fail when the embedding dimension d is smaller
than the statistical dimension δ(E ), provided that θ(E ) is spherically convex. Note that both of these
interpretations require that the statistical dimension δ(E ) is not too small as compared with the ambient
dimension D.
We have already seen a concrete example of Theorem I at work. In view of the calculation (3.6) of the
statistical dimension of the orthant, the theorem provides a satisfying explanation of Figure 1.2!
Remark 3.7 (Prior Work). When the random linear map Π is Gaussian, the result Theorem I(a) follows
from Gordon [Gor88, Cor. 3.4], while the conclusion (b) seems to be more recent [ALMT14, Thm. I]. To
our knowledge, the literature contains no precedent for Theorem I for general sets and for non-Gaussian
linear maps. We can identify only a few sporadic special cases. Donoho & Tanner [DT10] studied the
problem of recovering a “saturated vector” from random measurements via `∞ minimization. Their work
can be interpreted as a statement about random embeddings of the set of unit vectors with nonnegative
coordinates. They demonstrate that the phase transition in the embedding dimension is universal when
the rows of the linear map matrix are independent, symmetric random vectors with a density; this result
actually follows from classical work of Schäfli [Sch50] and Wendel [Wen62]. Let us emphasize that this
result does not apply to discrete random linear maps.
Bayati et al. [BLM15] have studied the problem of recovering a sparse vector from random measurements via `1 minimization. Their work can be interpreted as a result on the embedding dimension of the
set of descent directions of the `1 norm at a sparse vector. They showed that, asymptotically, the phase
transition in the embedding dimension is universal. Their result requires the linear map matrix to contain
independent, subgaussian entries that are absolutely continuous with respect to the Gaussian density.
See Section 5.1 for more discussion of this result.
There are also many papers in asymptotic convex geometry and mathematical signal processing that
contain theory about the order of the embedding dimension for linear maps from Model 2.4; see [MPTJ07,
Men10, Men14, Tro15b, Ver15]. These results do not allow us to reach any conclusions about the existence
of a phase transition or its location. There is also an extensive amount of empirical work, such as [DT09a,

14

S. OYMAK AND J. A. TROPP

Sto09, OH10, CSPW11, DGM13, MT14b], that suggests that phase transitions are ubiquitous in highdimensional signal processing problems, but there has been no theoretical explanation of the universality
phenomenon until now.
3.5. Theorem I: Proof Strategy. The proof of Theorem I depends on converting the geometric question
to an analytic problem. First, recall the equivalence (3.2), which allows us to pass from the compact set E
to its spherical retraction Ω := θ(E ). Next, we identify two analytic quantities that determine whether a
linear map annihilates a point in the set Ω.
Proposition 3.8 (Analytic Conditions for Embedding). Let Ω be a nonempty, closed subset of the unit
sphere SD−1 in RD , and let A : RD → Rd be a linear map. Then
min kAt k > 0 implies 0 ∉ A(Ω).
t ∈Ω

(3.9)

Furthermore, if Ω is spherically convex and cone(Ω) is not a subspace,
min

min

kt k=1 s∈cone(Ω◦ )

ks − A ∗ t k > 0 implies 0 ∈ A(Ω).

(3.10)

Finally, if cone(Ω) is a subspace, select an arbitrary subset Ω0 ⊂ Ω with the property that cone(Ω0 ) is a
(dim(Ω) − 1)-dimensional subspace. Then
min

min

kt k=1 s∈cone(Ω◦0 )

ks − A ∗ t k > 0 implies 0 ∈ A(Ω).

(3.11)

Recall that cone(S) is the smallest convex cone containing the set S.
Proof. The implication (3.9) is quite easy to check. At each point t ∈ Ω, we have kAt k > 0, which implies
that At 6= 0. In other words, 0 ∉ A(Ω).
The second implication (3.10) follows from a spherical duality principle. Suppose that Ω and Υ are
closed and spherically convex, and assume cone(Ω) is not a subspace. If Ω◦ and −Υ◦ do not intersect,
then Ω and Υ must intersect; see [Kle55, Thm (2.7)]. The analytic condition
min

min

kt k=1 s∈cone(Ω◦ )

ks − A ∗ t k > 0

ensures that cone(Ω◦ ) lies at a positive distance from θ(range(A ∗ )). It follows that Ω◦ does not intersect
θ(range(A ∗ )). By duality, we conclude that Ω ∩ θ(null(A)) 6= ;, which yields (3.10).
Finally, if cone(Ω) is a subspace, we use a dimension counting argument. As before, the analytic
condition (3.11) implies that Ω◦0 ∩ θ(range(A ∗ )) = ;. Since these sets do not intersect, the sum of their
dimensions cannot exceed the ambient dimension:
D ≥ dim(Ω◦0 ) + dim(range(A ∗ )) = (D − dim(Ω0 )) + (D − dim(null(A)))
= 2D + 1 − dim(Ω) − dim(null(A)).
We see that dim(Ω) + dim(null(A)) ≥ D + 1. As a consequence, the subspace cone(Ω) and (A) must have a
nontrivial intersection.

In view of Proposition 3.8, we can establish Theorem I(a) by showing that
d ≥ (1 − ε) δ(Ω) implies

min kΠt k > 0 with high probability.
t ∈Ω

This condition follows from a universality result, Corollary 10.1, for the restricted minimum singular value.
The proof appears in Section 10.3. Similarly, we can establish Theorem I(b) by showing that
d ≤ (1 + ε) δ(Ω) implies

min

min

kt k=1 s∈cone(Ω◦ )

ks − Π∗ t k > 0 with high probability.

This condition follows from a specialized argument that culminates in Corollary 17.1. The proof appears
in Section 17.2. We need not lavish extra attention on the case where cone(Ω) is a subspace. Indeed, the
dimension of Ω and Ω0 only differ by one, which is invisible in the final results.

UNIVERSALITY OF RANDOMIZED DIMENSION REDUCTION

15

3.6. Theorem I: Extensions. It is an interesting challenge to delineate the scope of the universality
phenomenon described in Theorem I. We believe that there remain many opportunities for improving on
this result.
• Theorem I only shows that the width of the phase transition
©p is o(D).
ª [ALMT14, Thm. 7.1]
p It is known
that the width of the phase transition has order min δ(E ), D − δ(E ) for a linear map with
standard normal entries. How wide is the phase transition for more general random linear maps?
• A related question is whether Theorem I holds for those sets E whose statistical dimension δ(E ) is
much smaller than the ambient dimension.
• There is empirical evidence that the location of the phase transition is universal over a class wider
than Model 2.4. In particular, results like Theorem I may be valid for structured random linear
maps.
• Figure 1.2 suggests that the probability of successful embedding is universal. Under what conditions can this observation be formalized?
In summary, Theorem I is just the first step toward a broader theory of universality in high-dimensional
stochastic geometry.
4. A U NIVERSALITY L AW FOR THE R ESTRICTED M INIMUM S INGULAR VALUE
This section describes a quantitative universality law for random linear maps. We show that the
restricted minimum singular value of a random linear map takes the same value for every linear map in a
substantial class. This type of result provides information about the stability of randomized dimension
reduction.
4.1. Restricted Minimum Singular Value: Problem Formulation. Let us frame our assumptions:
• Fix the ambient dimension D.
• Let E be a nonempty, compact subset of the unit ball BD .
• Let Π : RD → Rd be a random linear map with embedding dimension d .
In this section, our goal is to understand the distance from the random projection Π(E ) to the origin.
The following definition captures this property.
Definition 4.1 (Restricted Minimum Singular Value). Let A : RD → Rd be a linear map, and let T be a
nonempty subset of RD . The restricted minimum singular value of A with respect to the set T is the
quantity
σmin (A; T ) := inf kAt k .
t ∈T

More briefly, we write restricted singular value or RSV.
Proposition 3.8 shows that the restricted minimum singular value is a quantity of interest when studying
the embedding dimension of a linear map. It is also productive to think about σmin (A; T ) as a measure
of the stability of inverting the map A on the image A(T ). In particular, note that the restricted singular
value σmin (A; T ) is a generalization of the ordinary minimum singular value σmin (A), which we obtain
from the selection T = SD−1 .
4.2. The Excess Width Functional. It is clear that the restricted singular value σmin (A; ·) decreases with
respect to set inclusion. In other words, the restricted singular value depends on the “content” of the set
T . In the case of a random linear map, the following geometric functional provides the correct notion of
content.
Definition 4.2 (Excess Width). Let m be a positive number, and let T be a nonempty, bounded subset of
RD . The m-excess width of T is the quantity
¡p
¢
Em (T ) := E inf m kt k + g · t .
(4.1)
t ∈T

16

S. OYMAK AND J. A. TROPP

Versions of the excess width appear as early as the work of Gordon [Gor88, Cor. 1.1]. It has also come up in
recent papers [Sto13, OTH13, TOH15, TAH15] on the analysis of Gaussian random linear maps.
The excess width has a number of useful properties. These results are immediate consequences of the
definition.
• For a subset T of the unit ball in RD , the m-excess width satisfies the bounds
p
p
p
m − D ≤ Em (T ) ≤ m.
•
•
•
•

In particular, the excess width can be positive or negative.
The m-excess width is weakly increasing in m. That is, m ≤ n implies Em (T ) ≤ En (T ).
The m-excess width is decreasing with respect to set inclusion: S ⊂ T implies Em (S) ≥ Em (T ).
The m-excess width is absolutely homogeneous: Em (αT ) = |α| Em (T ) for α ∈ R.
The excess width (4.1) is related to the Gaussian width (3.7):
p
(4.2)
Em (Ω) = m − W (Ω) for Ω ⊂ SD−1 .
Using (3.8), we can also relate the excess width to the statistical dimension:
p
p
p
p
m − 1 + δ(Ω) ≤ Em (Ω) ≤ m − δ(Ω) for Ω ⊂ SD−1 .

(4.3)

The term “excess width” is not standard, but the formula (4.2) suggests that this moniker is appropriate.
According to Theorem I, the sign (±) of the excess width Ed (Ω) indicates that random dimension reduction
Π(Ω) with embedding dimension d succeeds (+) or fails (−) with high probability.
The papers [Sto13, OTH13, TOH15] develop methods for computing the excess width in a variety of
situations. For instance, if L is a k-dimensional subspace of RD , then
p
p
Em (L ∩ SD−1 ) ≈ m − k.
For a more sophisticated example, consider the probability simplex
n
o
XD
∆D := t ∈ RD : i =1 t i = 1, t i ≥ 0 for i = 1, . . . , D .
We can develop an asymptotic expression for its excess width:
³
p
£
¡
¢´
¤
lim Ed (∆D ) = inf α − inf s + α %q(s)
where q(s) := E (γ − s)2+ .
D,d →∞
D/d =%

α≥0

s∈R

(4.4)

The proof of the formula (4.4) is involved, so we must omit the details; see [TAH15] for a framework for
making such computations. See Part II for some other examples. It is also possible to estimate the excess
width numerically by approximating the expectation in (4.1) with an empirical average.
4.3. Theorem II: Universality for the Restricted Minimum Singular Value. With this preparation, we
can present our main result about the universality properties of the restricted minimum singular value of
a random linear map.
Theorem II (Universality for the Restricted Minimum Singular Value). Fix the parameters p and ν for
Model 2.4. Choose parameters λ ∈ (0, 1) and % ∈ (0, 1) and ε ∈ (0, 1). There is a number N := N (p, ν, λ, %, ε)
for which the following statement holds. Suppose that
•
•
•
•
•

The ambient dimension D ≥ N .
E is a nonempty, compact subset of the unit ball BD in RD .
The embedding dimension d is in the range λD ≤ dp≤ D 6/5 .
The d -excess width of E is not too small: Ed (E ) ≥ % d .
The random linear map Π : RD → Rd obeys Model 2.4 with parameters p and ν.

Then
©
¡
¢ ª
P σmin (Π; E ) ≥ (1 − ε) Ed (E ) + ≥ 1 − Cp D 1−p/4 .

(a)

UNIVERSALITY OF RANDOMIZED DIMENSION REDUCTION

Furthermore, if E is convex, then
©
¡
¢ ª
P σmin (Π; E ) ≤ (1 + ε) Ed (E ) + ≥ 1 − Cp D 1−p/4 .

17

(b)

The constant Cp depends only on the parameter p in the random matrix model.
Section 4.4 contains an overview of the argument. The detailed proof of Theorem II appears in Section 10.2.
Stronger probability bounds hold when the random linear map is drawn from Model 2.1.
For any random linear map Π drawn from Model 2.4, Theorem II asserts that the distance of the random
projection Π(E ) from the origin is typically not much smaller than the d -excess width Ed (E ). Similarly,
when E is convex, the distance of the random image from the origin is typically not much larger than the
d -excesspwidth. These conclusions require that the excess width Ed (E ) is not too small as compared with
the root d of the embedding dimension.
Theorem IIpis vacuous when Ed (E ) ≤ 0. Nevertheless, in case θ(E ) is spherically convex, the condition
Ed (θ(E )) + o( D) ≤ 0 implies that σmin (Π; E ) = 0 with high probability because of (4.3) and Theorem I.
We have already seen an illustration of Theorem II in action. In view of the expression (4.4) for the
excess width of the probability simplex, the theorem explains the experiment documented in Figure 1.4!
Remark 4.3 (Prior Work). When the random linear map Π is Gaussian, Gordon’s work [Gor88, Cor. 1.1]
yields the conclusion Theorem II(a), while the second conclusion (b) appears to be more recent; see [Sto13,
OTH13, TOH15, TAH15].
Korada & Montanari [KM11] have established universality laws for some optimization problems that
arise in communications. The mathematical challenge in their work is similar to showing that the RSV of
a cube is universal for Model 2.4 with p ≥ 6. We have adopted some of their arguments in our work. On
the other hand, the cube does not present any of the technical difficulties that arise for general sets.
For other types of random linear maps and other types of sets, we are not aware of any research that
yields the precise value of the restricted singular value, which is required to assert universality. The
literature on asymptotic convex geometry and mathematical signal processing, e.g., [MPTJ07, Men10,
Men14, Tro15b, Ver15], contains many results on the restricted singular value that provide bounds of the
correct order with unspecified multiplicative constants.
4.4. Theorem II: Proof Strategy. One standard template for proving a universality law factors the problem
into two parts. First, we compare a general random structure with a canonical structure that has additional
properties. Then we use these extra properties to obtain a complete analysis of the canonical structure.
Because of the comparison, we learn that the general structure inherits some of the behavior of the
canonical structure. This recipe describes Lindeberg’s approach [Lin22] to the central limit theorem;
see [Tao12, Sec. 2.2.4]. More recently, similar methods have been directed at harder problems, such as the
universality of local spectral statistics of a non-symmetric random matrix [TV15]. Our research is closest
in spirit to the papers [MOO10, Cha06, KM11].
Let us imagine how we could apply this technique to prove Theorem II. Suppose that E is a compact,
convex set. After performing standard discretization and smoothing steps, we might invoke the Lindeberg
exchange principle to compare the restricted singular value of the d × D random linear map Π with that
of a d × D standard normal matrix Γ:
E σmin (Π; E ) ≈ E σmin (Γ; E ).

To evaluate the restricted minimum singular value of a standard normal matrix, we can use the Gaussian
Minimax Theorem, as in [Gor88, Cor. 1.1]:
¡
¢
E σmin (Γ; E ) ' Ed (E ) + .
Last, we can incorporate a convex duality argument, as in [Sto13, OTH13, TOH15, TAH15], to obtain the
reverse inequality:
¡
¢
E σmin (Γ; E ) / Ed (E ) + .

18

S. OYMAK AND J. A. TROPP

Unfortunately, this simple approach is not adequate. Our argument ultimately follows a related pattern,
but we have to overcome a number of technical obstacles.
Let us explain the most serious issue and our mechanism for handling it. We would like to apply the
Lindeberg exchange principle to σmin (Π; E ) to replace each entry of Π with a standard normal variable.
The problem is that E may contain a vector t 0 with large entries. If we try to replace the columns of Π
associated with the large components of t 0 , we incur an intolerably large error. Moreover, for any given
coordinate j , the set E may contain a vector t j that takes a large value in the distinguished coordinate j .
This fact seems to foreclose the possibility of replacing any part of the matrix Π.
We address this challenge by dissecting the index set E . For each (small) subset J of {1, . . . , D}, we define
the set E J of vectors in E whose components in J c are small. First, we argue that the restricted singular
value of a subset does not differ much from the restricted singular value of the entire set:
E σmin (Π; E ) ≈ min J E σmin (Π; E J ).

We may now use the Lindeberg method to make the comparison
E σmin (Π; E J ) ≈ E σmin (Ψ; E J ),

where the matrix Ψ is a hybrid of the form Ψ J = Π J and Ψ J c = Γ J c . That is, we only replace the columns of
Π listed in the set J c with independent standard normal variables. At this point, we need to compare the
minimum singular value of Ψ restricted to the subset E J against the excess width of the full set:
¡
¢
E σmin (Ψ; E J ) ≈ Ed (E ) + .
In other words, the remaining part Ψ J of the original matrix plays a negligible role in determining
the restricted singular value. We perform this estimate using the Gaussian Minimax Theorem [Gor85],
some convex duality arguments [TOH15], and some coarse results from nonasymptotic random matrix
theory [Ver12, Tro15c].
See Part III for detailed statements of the main technical results that support Theorem II and the proofs
of these results. Most of the ingredients are standard tools from modern applied probability, but we have
combined them in a subtle way. To make the long argument clearer, we have attempted to present the
proof in a multi-resolution fashion where pieces from each level are combined explicitly at the level above.
4.5. Theorem II: Extensions. We expect that there are a number of avenues for extending Theorem II.
• Our
p analysis shows that the error in estimating σmin (Π; E ) by the excess width Ed (E ) is at most
o( D). In case Π is a standard normal matrix, the error actually has constant order [TOH15,
Thm. II.1]. Can we improve the error bound for more general random linear maps?
• A related question is whether thep
universality of σmin (Π; E ) persists when the excess width Ed (E )
is very small in comparison with d .
• There is some empirical evidence that the restricted minimum singular value may have universality
properties for a class of random linear maps wider than Model 2.4.
• Our proof can probably be adapted to show that other types of functionals exhibit universal
behavior. For example, we can study
¡
¢
min kΠt k2 + f (t )
t ∈E

where f is a convex, Lipschitz function. This type of optimization problem plays an important
role in statistics and machine learning.
At the same time, we know that many natural functionals do not exhibit universal behavior. In particular,
consider the restricted maximum singular value:
σmax (A; T ) := sup kAt k .
t ∈T

There are many sets T where the maximum singular value σmax (·; T ) does not take a universal value for
linear maps in Model 2.4; for example, see Figure 1.6. It is an interesting challenge to determine the full
scope of the universality principle uncovered in Theorem II.

UNIVERSALITY OF RANDOMIZED DIMENSION REDUCTION

19

Part II. Applications
In this part of the paper, we outline some of the implications of Theorems I and II in the information
sciences. We focus on problems involving least squares and `1 minimization to reduce the number of
distinct calculations that we need to perform; nevertheless the techniques apply broadly. In an effort to
make the presentation shorter and more intuitive, we have also chosen to sacrifice some precision.
Section 5 discusses structured signal recovery and, in particular, the compressed sensing problem.
Section 6 presents an application in coding theory. Section 7 describes how the results allow us to analyze
randomized algorithms for numerical linear algebra. Finally, Section 8 gives a universal formula for the
prediction error in a sparse regression problem.
5. R ECOVERY OF S TRUCTURED S IGNALS FROM R ANDOM M EASUREMENTS
In signal processing, dimension reduction arises as a mechanism for signal acquisition. The idea is that
the number of measurements we need to recover a structured signal is comparable with the number of
degrees of freedom in the signal, rather than the ambient dimension. Given the measurements, we can
reconstruct the signal using nonlinear algorithms that take into account our prior knowledge about the
structure. The field of compressed sensing is based on the idea that random linear measurements offer an
efficient way to acquire structured signals. The practical challenge in implementing this proposal is to
find technologies that can perform random sampling.
Our universality laws have a significant implication for compressed sensing. We prove that the number
of random measurements required to recover a structured signal does not have a strong dependence on
the distribution of the random measurements. This result is important because most applications offer
limited flexibility in the type of measurement that we can take. Our theory justifies the use of a broad class
of measurement ensembles.
5.1. The Phase Transition for Sparse Signal Recovery. In this section, we study the phase transition that
appears when we reconstruct a sparse signal from random measurements via `1 minimization. For a large
class of random measurements, we prove that the distribution does not affect the location of the phase
transition. This result resolves a major open question [DT09a] in the theory of compressed sensing.
Let us give a more precise description of the problem. Suppose that x ? ∈ Rn is a fixed vector with
precisely s nonzero entries. Let Φ : Rn → Rm be a random linear map, and suppose that we have access to
the image y = Φx ? . We interpret this data as a list of m samples of the unknown signal.
A standard approach [CDS98, DH01, Tro06, CRT06, Don06a] for reconstructing the sparse signal x ?
from the data is to solve a convex optimization problem:
minimize
n
x∈R

kxk`1

subject to Φx = y.

(5.1)

Minimizing the `1 norm promotes sparsity in the optimization variable x, and the constraint ensures
that the virtual measurements Φx are consistent with the observed data y. We say that the optimization
problem (5.1) succeeds if it has a unique solution xb that coincides with x ? . Otherwise, it fails. In this
setting, the following challenge arises.
The Compressed Sensing Problem: Is the optimization problem (5.1) likely to succeed
or to fail to recover x ? as a function of the sparsity s, the number m of measurements, the
ambient dimension n, and the distribution of the random measurement matrix Φ?
This question has been a subject of inquiry in thousands of papers over the last 10 years; see the
books [EK12, FR13] for more background and references.
In a series of recent papers [DT09b, Sto09, CRPW12, BLM15, ALMT14, Sto13, OTH13, FM14, GNP14],
the compressed sensing problem has been solved completely in the case where the random measurement
matrix Φ follows the standard normal distribution. See Remark 5.2 for a narrative of who did what when.

20

S. OYMAK AND J. A. TROPP

Probability of Exact Recovery
(20% Nonzero Rademacher)

Probability of Exact Recovery
(Student t with 5 dof)

Number of Measurements (m)

0.8

50

0.7
0.6

40

0.5

30

0.4

20

0.3
0.2

10

Theory
0

0

10

20

30

40

Sparsity (s)

50

60

0.1
0

0.9

60

0.8

50

0.7
0.6

40

0.5

30

0.4

20

0.3
0.2

10

Theory
0

Empirical Probability

0.9

60

0

10

20

30

40

Sparsity (s)

50

60

0.1
0

F IGURE 5.1: Universality of the `1 Recovery Phase Transition. These plots depict the empirical probability
that the `1 minimization problem (5.1) recovers a vector x ? ∈ R64 with s nonzero entries from a vector
of random measurements y = Φx ? ∈ Rm . The heatmap indicates the empirical probability, computed
over 100 trials. The white curve is the phase transition nψ`1 (s/n) promised by Proposition 5.1. L EFT: The
random measurement matrix Φ is a sparse Rademacher matrix with an average of 20% nonzero entries.
R IGHT: The random measurement matrix Φ has independent Student t 5 entries. See Section 1.9 for more
details.

In brief, there exists a phase transition function ψ`1 : [0, 1] → [0, 1] defined by
!
Ã
r Z
2 ∞
2
2 −ζ2 /2
ψ`1 (%) := inf %(1 + τ ) + (1 − %)
(ζ − τ) e
dζ .
τ≥0
π τ

(5.2)

The phase transition function is increasing and convex, and it satisfies ψ`1 (0) = 0 and ψ`1 (1) = 1. When
the measurement matrix Φ is standard normal,
m/n < ψ`1 (s/n) − o(1) implies (5.1) fails with probability 1 − o(1);
m/n > ψ`1 (s/n) + o(1) implies (5.1) succeeds with probability 1 − o(1).

(5.3)

In other words, as the number m of measurements increases, the probability of success jumps from zero
to one at the point nψ`1 (s/n) over a range of o(n) measurements. The error terms in (5.3) can be improved
substantially, but this presentation suffices for our purposes.
Donoho & Tanner [DT09a] have performed an extensive empirical investigation of the phase transition
in the `1 minimization problem (5.1). Their work suggests that the Gaussian phase transition (5.3) persists
for many other types of random measurements. See Figure 5.1 for a small illustration. Our universality
results provide the first rigorous explanation of this phenomenon for measurement matrices drawn from
Model 2.4.
Proposition 5.1 (Universality of `1 Phase Transition). Assume that
•
•
•
•

The ambient dimension n and the number m of measurements satisfy m ≤ n.
The vector x ? ∈ Rn has exactly s nonzero entries.
The random measurement matrix Φ : Rn → Rm follows Model 2.4 with parameters p and ν.
We observe the vector y = Φx ? .

UNIVERSALITY OF RANDOMIZED DIMENSION REDUCTION

21

Then, as the ambient dimension n → ∞,
m/n < ψ`1 (s/n) − o(1) implies (5.1) fails with probability 1 − o(1);
m/n > ψ`1 (s/n) + o(1) implies (5.1) succeeds with probability 1 − o(1).
The little-o suppresses constants that depend only on p and ν.
Proposition 5.1 follows directly from our universality result, Theorem I, and the established calculation (5.3) of the phase transition in the standard normal setting.
Proof. The approach is quite standard. Let Ω be the set of unit-norm descent directions of the `1 norm at
the point x ? . That is,
©
ª
Ω := u ∈ Sn−1 : kx ? + λuk1 ≤ kx ? k1 for some λ > 0 .
The primal optimality condition for (5.1) demonstrates that the reconstruction succeeds if and only if
Ω∩null(Φ) = ;. Since the `1 norm is a closed convex function, the set θ −1 (Ω)∪{0} of all descent directions
forms a closed, convex cone. Therefore, the set Ω is closed and spherically convex. It follows from
Theorem I that the behavior of (5.1) undergoes a phase transition at the statistical dimension δ(Ω) for any
random linear map drawn from Model 2.4.
The result [ALMT14, Prop. 4.5] contains the first complete and accurate computation of the statistical
dimension of a descent cone of the `1 norm:
p
nψ`1 (s/n) − O( n) ≤ δ(Ω) ≤ nψ`1 (s/n).
(5.4)
See also [FM14, Prop. 1]. This fact completes the proof.



Note that Proposition 5.1 requires the sparsity level s to be proportional to the ambient dimension
n before it provides any information. By refining our argument, we can address the case when s is
proportional to n 1−ε for a small number ε that depends on the regularity of the random linear map. The
empirical work [DT09a] of Donoho & Tanner is unable to provide statistical evidence for the universality
hypothesis in the regime where s is very small. It remains an open problem to understand how rapidly
s/n can vanish before the universality phenomenon fails.
The paper [DT09a] also contains numerical evidence that the `1 phase transition persists for random
measurement systems that have more structure than Model 2.4. It remains an intriguing open question to
understand these experiments.
Remark 5.2 (Prior Work). In early 2005, Donoho [Don06c] and Donoho & Tanner [DT06] observed that
there is a phase transition in the number of standard normal measurements needed to reconstruct a
sparse signal via `1 minimization. Using methods from integral geometry, they were able to perform a
heuristic computation of the location of the phase transition function (5.2). In subsequent work [DT09b],
they proved that the transition (5.3) is valid in some parameter regimes. They later reported extensive
empirical evidence [DT09a] that the distribution of the random measurement map has little effect on the
location of the phase transition.
In early 2005, Rudelson & Vershynin [RV08] proposed a different approach to studying `1 minimization
by adapting results of Gordon [Gor88] that depend on Gaussian process theory. Stojnic [Sto09] refined
this argument to obtain an empirically sharp success condition for standard normal linear maps, but his
work did not establish a matching failure condition. Stojnic’s calculations were clarified and extended to
other signal recovery problems in the papers [OH10, CRPW12, ALMT14, FM14].
Bayati et al. [BLM15] is the first paper to rigorously demonstrate that the phase transition (5.3) is valid
for standard normal measurements. The argument is based on a state evolution framework for an iterative
algorithm inspired by statistical physics. This work also gives the striking conclusion that the `1 phase
transition is universal over a class of random measurement maps. This result requires the measurement
matrix to have independent, standardized, subgaussian entries that are absolutely continuous with respect
to the Gaussian distribution. As a consequence, the paper [BLM15] excludes discrete and heavy-tailed

22

S. OYMAK AND J. A. TROPP

models. Furthermore, it only applies to `1 minimization. In contrast, Proposition 5.1 and its proof have a
much wider compass.
The paper [ALMT14] of Amelunxen et al. contains the first complete integral-geometric proof of (5.3)
for standard normal measurements. This work is significant because it established for the first time that
phase transitions are ubiquitous in signal reconstruction problems. It also forged the first links between
the approach to phase transitions based on integral geometry and those based on Gaussian process theory.
The papers [MT14a, GNP14] build on these ideas to obtain precise estimates of the success probability
in (5.3).
Subsequently, Stojnic [Sto13] refined the Gaussian process methods to obtain more detailed information about the behavior of the errors in noisy variants of the `1 minimization problem. His work has been
extended in a series [OTH13, TOH15, TAH15] of papers by Abbasi, Oymak, Thrampoulidis, Hassibi, and
their collaborators. Because of this research, we now have a very detailed understanding of the behavior
of convex signal recovery methods with Gaussian measurements.
To our knowledge, the current paper is the first work that extends the type of general analysis in [ALMT14,
OTH13, TAH15] beyond the confines of the standard normal model.
5.2. Other Signal Recovery Problems. The compressed sensing problem is the most prominent example
from a large class of related questions. Our universality results have implications for this entire class of
problems. We include a brief explanation.
Let f : Rn → R be a proper7 convex function whose value increases with the “complexity” of its argument.
The `1 norm is an example of a complexity measure that is appropriate for sparse signals [CDS98].
Similarly, the Schatten 1-norm is a good complexity measure for low-rank matrices [Faz02].
Let x ? ∈ Rn be a vector with “low complexity.” Draw a random linear map Φ : Rn → Rm , and suppose we
have access to x ? only through the measurements y = Φx ? . We can attempt to reconstruct x ? by solving
the convex optimization problem
minimize
n
x∈R

f (x) subject to Φx = y.

In other words, we find the vector with minimum complexity that is consistent with the observed data.
We say that (5.2) succeeds when it has a unique optimal point that coincides with x ? ; otherwise, it fails.
The paper [ALMT14] proves that there is a phase transition in the behavior of (5.2) when Φ is standard
normal. Our universality law, Theorem I, allows us to extend this result to include every random linear
map from Model 2.4. Define the set Ω of unit-norm descent directions of f at the point x ? :
©
ª
Ω := u ∈ Sn−1 : f (x ? + λu) ≤ f (x ? ) for some λ > 0 .
Then, as the ambient dimension n → ∞,
m < δ(Ω) − o(n) implies (5.2) fails with probability 1 − o(1);
m > δ(Ω) + o(n) implies (5.2) succeeds with probability 1 − o(1).
In other words, there is a phase transition in the behavior of (5.2) when the number m of measurements
equals the statistical dimension δ(Ω) of the set of descent directions of f at the point x ? . See the papers [CRPW12, ALMT14, FM14] for some general methods for computing the statistical dimension of a
descent cone.
5.3. Complements. We conclude this section with a few additional remarks about the scope of our results
on signal recovery. First, we discuss some geometric applications. Second, we mention some other signal
processing problems that can be studied using the same methods.
7A proper convex function takes at least one finite value and never takes the value −∞.

UNIVERSALITY OF RANDOMIZED DIMENSION REDUCTION

23

5.3.1. Geometric Implications. Proposition 5.1 can be understood as a statement about the facial structure
of a random projection of the `1 ball. Equivalently, it provides information about the facial structure of
the convex hull of random points.
Suppose that Bn1 is the n-dimensional `1 ball, and fix an (s−1)-dimensional face F of Bn1 . Let Φ : Rn → Rm
be a random linear map from Model 2.4. We say that Φ preserves the face F when Φ(F ) is an (s − 1)dimensional face of the projection Φ(Bn1 ). We can reinterpret Proposition 5.1 as saying that
m/n < ψ`1 (s/n) − o(1) implies Φ is unlikely to preserve F ;
m/n > ψ`1 (s/n) + o(1) implies Φ is likely to preserve F .
The connection between `1 minimization and the facial structure of the `1 ball was identified in [Don06b];
see also [ALMT14, Sec. 10.1.1].
Here is another way of framing the same result. Fix an index set J ⊂ {1, . . . , n} with cardinality #J = s
and a vector η ∈ Rn with ±1 entries. Let ϕ1 , . . . , ϕn ∈ Rm be independent random vectors, drawn from
Model 2.4, and consider the absolute convex hull E := conv{±ϕ1 , . . . , ±ϕn }. The question is whether the
set F := conv{η j ϕ j : j ∈ J } is an (s − 1)-dimensional face of E . We have the statements
s/n < ψ−1
`1 (m/n) − o(1) implies F is likely to be an (s − 1)-dimensional face of E ;
s/n > ψ−1
`1 (m/n) + o(1) implies F is unlikely to be an (s − 1)-dimensional face of E .
See the paper [DT09b] for more discussion of the connection between the facial structure of polytopes
and signal recovery. Some universality results of this type also appear in Bayati et al. [BLM15].
5.3.2. Other Signal Processing Applications. We often want to perform signal processing tasks on data
after reducing its dimension. In this section, we have focused on the problem of reconstructing a sparse
signal from random measurements. Here are some related problems:
• Detection. Does an observed signal consist of a template corrupted with noise? Or is it just noise?
• Classification. Does an observed signal belong to class A or to class B?
The literature contains many papers that propose methods for solving these problems after dimension
reduction; for example, see [DDW+ 07]. The existing analysis is either qualitative or it assumes that the
dimension reduction map is Gaussian. Our universality laws can be used to study the precise behavior of
compressed detection and classification with more general types of random linear maps. For brevity, we
omit the details.
6. D ECODING WITH S TRUCTURED E RRORS
One of the goals of coding theory is to design codes and decoding algorithms that can correct gross
errors in transmission. In particular, it is common that some proportion of the received symbols are
corrupted. In this section, we show that a large family of random codes can be decoded in the presence
of structured errors. The number of errors that we can correct is universal over this family. This result is
valuable because it applies to random codebooks that are closer to realistic coding schemes.
The result on random decoding can also be interpreted as a statement about the behavior of the
least-absolute-deviation (LAD) method for regression. We also discuss how our universality results apply
to a class of demixing problems.
6.1. Decoding with Sparse Errors. We work with a random linear code over the real field. Consider a
fixed message x ? ∈ Rm . Let Φ ∈ Rn×m be a random matrix, which is called a codebook in this context.
Instead of transmitting the original message x ? , we transmit the coded message Φx ? . Suppose that we
receive a version y of the message where some number s of the entries are corrupted. That is, y = Φx ? +z ?
where the error vector z ? has at most s nonzero entries. For simplicity, we assume that z ? does not depend
on the codebook Φ.

24

S. OYMAK AND J. A. TROPP

Empirical Probability of Decoding a Message of Length m = 64
(20% Nonzero Rademacher Codebook)
30

0

Theory

0.1

Number of Errors (s)

0.3

20

0.4
0.5

15

0.6

10

0.7
0.8

5
0

Empirical Probability

0.2

25

0.9

70

80

90

100

Length of Code (n)

110

120

F IGURE 6.1: Universality of the `1 Decoding Phase Transition. This plot shows the empirical probability
that the `1 method (6.1) decodes the message x ? ∈ R64 from the received message y = Φx ? + z ? ∈ Rn where
the corruption z ? ∈ Rn has exactly s nonzero entries. The codebook Φ ∈ Rn×64 is a sparse Rademacher
matrix with an average of 20% nonzero entries. The heatmap gives the empirical probability of correct
decoding, computed over 100 trials. The white curve is the exact phase transition nψ−1
(1−64/n) promised
`1
by Proposition 6.1. See Section 1.9 for more details.

In this setting, one can attempt to decode the message using an `1 minimization method [DH01,
CRTV05, DT06, MT14b]. We solve the optimization problem
minimize
m
n
x∈R ,z∈R

kzk`1

subject to

y = Φx + z.

(6.1)

In other words, we search for a message x and a sparse corruption z that match the received data. We
say that the optimization (6.1) succeeds if it has a unique optimal point (xb, zb) that coincides with (x ? , z ? );
otherwise it fails.
The question is when the optimization problem (6.1) is effective at decoding the received transmission.
That is, how many errors s can we correct as a function of the message length m and the code length n?
The following result gives a solution to this problem for any codebook drawn from Model 2.4.
Proposition 6.1 (Universality of Sparse Error Correction). Assume that
•
•
•
•
•

The message length m and the code length n satisfy m ≤ n.
The message x ? ∈ Rm is arbitrary.
The error vector z ? ∈ Rn has exactly s nonzero entries, where s ≤ (1 − ξ)n for some ξ > 0.
The random codebook Φ ∈ Rn×m follows Model 2.4 with parameters p and ν.
We observe the vector y = Φx ? + z ? .

Then, as the message length m → ∞,
s/n < ψ−1
`1 (1 − m/n − o(1)) implies
s/n

> ψ−1
`1 (1 − m/n + o(1))

implies

(6.1) succeeds with probability 1 − o(1);
(6.1) fails with probability 1 − o(1).

The function ψ`1 is defined in (5.2). The little-o suppresses constants that depend only on ξ and p and ν.

UNIVERSALITY OF RANDOMIZED DIMENSION REDUCTION

25

This result is significant because it allows us to understand the behavior of this method for a sparse,
discrete codebook. This type of code is somewhat closer to a practical coding mechanism than the ultrarandom codebooks that have been studied in the past; see Remark 6.3. Figure 6.1 contains an illustration
of how the theory compares with the actual performance of this coding scheme.
Proof. To analyze the decoding problem (6.1), we change variables: u := x − x ? and v := z − z ? . We obtain
the equivalent optimization problem
minimize
m
n
u∈R ,v ∈R

kz ? + v k`1

subject to Φu = v .

(6.2)

b vb) of the problem (6.2)
The decoding procedure (6.1) succeeds if and only if the unique optimal point (u,
is the pair (0, 0).
Introduce the set Ω of unit-norm descent directions of the `1 norm at z ? :
©
ª
Ω := v ∈ Sn−1 : kz ? + λv k`1 ≤ kz ? k`1 for some λ > 0 .

The primal optimality condition for (6.2) shows that decoding succeeds if and only if Ω ∩ range(Φ) = ;.
Let us compute the statistical dimension of Ω◦ :
δ(Ω◦ ) = n − δ(Ω) = n − (nψ`1 (s/n) + o(n)) = n(1 − ψ`1 (s/n) + o(1)).

(6.3)

The first relation is the polar identity (3.5) for the statistical dimension, and the value of the statistical
dimension appears in (5.4). Since s ≤ (1 − ξ)n, the properties of the function ψ`1 ensure that δ(Ω◦ ) ≥ %n
for some % > 0.
First, we demonstrate that decoding fails when the number s of errors is too large. To do so, we must
show that Ω ∩ range(Φ) 6= ;. By polarity [Kle55, Thm. (2.7)], it suffices to check that
Ω◦ ∩ null(Φ∗ ) = ;.
With probability at least 1 − o(1), this relation follows from Theorem I(a), provided that
m > δ(Ω◦ ) + o(n) = n(1 − ψ`1 (s/n)) + o(n).
Finally, revert the inequality so that it is expressed in terms of s.
Last, we must check that decoding succeeds when the number s of errors is sufficiently small. To do so,
we must verify that Ω ∩ range(Φ) = ; with high probability. This relation follows from ideas closely related
to the proof of Theorem I, but it is not a direct consequence. See Section 17.3 for the details.

Remark 6.2 (Least-Absolute-Deviation Regression). Proposition 6.1 can also be interpreted as a statement
about the performance of the least-absolute deviation method for fitting models with outliers. Suppose
that we observe the data y = X β? + z. Each of the n rows of X is interpreted as a vector of m measured
variables for an independent subject in an experiment. The vector β? lists the coefficients in the true linear
model, and the sparse vector z contains a small number s of arbitrary statistical errors. The least-absolute
deviation method fits a model by solving
minimize
β∈Rm

kX β − yk`1 .

Proposition 6.1 shows that the procedure identifies the true model β? exactly, provided that the number s
of contaminated data points satisfies s/n < ψ−1
(1 − m/n) − o(1).
`
1

Remark 6.3 (Prior Work). The idea of using `1 minimization for decoding in the presence of sparse errors
dates at least as far back as the paper [DH01]. This scheme received further attention in the work [CRTV05].
Later, Donoho & Tanner [DT06] applied phase transition calculations to assess the precise performance
of this coding scheme for a standard normal codebook; the least-absolute-deviation interpretation of this
result appears in [DT09a, Sec. 1.3]. The paper [MT14b] revisits the coding problem and develops a sharp
analysis in the case where the codebook is a random orthogonal matrix. The current paper contains the
first precise result that extends to codebooks with more general distributions.

26

S. OYMAK AND J. A. TROPP

6.2. Other Demixing Problems. The decoding problem (6.1) is an example of a convex demixing problem [MT14b, ALMT14]. Our universality results can be used to study other questions of this species.
Let f 0 : Rn → R and f 1 : Rn → R be proper convex functions that measure the complexity of a signal.
Suppose that x ?0 ∈ Rn and x ?1 ∈ Rn are signals with “low complexity.” Draw random matrices Φ0 : Rn → Rm
and Φ1 : Rn → Rm from Model 2.4. Suppose that we observe the vector y = Φ0 x ?1 + Φ1 x ?1 . We interpret the
random matrices as known transformations of the unknown signals. For example, the matrices Φi might
denote dictionaries in which the two components of y are sparse.
We can attempt to reconstruct the original signal pair by solving
©
ª
minimize max f 0 (z 0 ), f 1 (z 1 ) subject to Φ0 z 0 + Φ1 z 1 = y.
(6.4)
z 0 ∈Rn ,z 1 ∈Rn

In other words, we witness a superposition of two structured signals, and we attempt to find the lowest
complexity pair (z 0 , z 1 ) that reproduces the observed data. The demixing problem succeeds if it has a
unique optimal point that equals (x ?0 , x ?1 ).
To analyze this problem, we introduce two descent sets:
©
ª
Ωi := u ∈ Sn−1 : f i (x ?i + λu) ≤ f i (x ?i ) for some λ > 0 for i = 1, 2.
Up to scaling, the descent directions of max{ f 0 (·), f 1 (··)} at the pair (x ?0 , x ?1 ) coincide with the direct
product Ω0 × Ω1 . The statistical dimension of a direct product of two spherical sets satisfies δ(Ω0 × Ω1 ) =
δ(Ω0 ) + δ(Ω1 ). Therefore, Theorem I demonstrates that
m < δ(Ω0 ) + δ(Ω1 ) − o(n) implies (6.4) fails with probability 1 − o(1);
m > δ(Ω0 ) + δ(Ω1 ) + o(n) implies (6.4) succeeds with probability 1 − o(1).
In other words, the amount of information needed to extract a pair of signals from the superposition
equals the total complexity of the two signals. This result holds true for a wide class of distributions on Φ0
and Φ1 .
7. R ANDOMIZED N UMERICAL L INEAR A LGEBRA
Numerical linear algebra (NLA) is the study of computational methods for problems in linear algebra,
including the solution of linear systems, spectral calculations, and matrix approximations. Over the last
15 years, researchers have developed many new algorithms for NLA that exploit randomness to perform
these computations more efficiently. See the surveys [Mah11, HMT11, Woo14] for an overview of this
field.
In this section, we apply our universality techniques to obtain new results on dimension reduction in
randomized NLA. This discussion shows that a broad class of dimension reduction methods share the
same quantitative behavior. Therefore, within some limits, we can choose the random linear map that is
most computationally appealing when we design numerical algorithms based on dimension reduction.
As an added bonus, the arguments here lead to a new proof of the Bai–Yin limit for the minimum
singular value of a random matrix drawn from Model 2.4.
7.1. Subspace Embeddings. In randomized NLA, one of the key primitives is a subspace embedding. A
subspace embedding is nothing more than a randomized linear map that does not annihilate any point in
a fixed subspace.
Definition 7.1 (Subspace Embedding). Fix a natural number k, and let L be an arbitrary k-dimensional
subspace. We say that a randomized linear map Π : RD → Rd is an oblivious subspace embedding of order
k if
¡
¢
0 ∉ Π L ∩ SD−1 with high probability.
The term “oblivious” indicates that the linear map Π is chosen without knowledge of the subspace L.

UNIVERSALITY OF RANDOMIZED DIMENSION REDUCTION

27

In the definition of a subspace embedding, some authors include quantitative bounds on the stability of
the embedding. These estimates are useful for analyzing certain algorithms, but we have left them out
because they are not essential.
A standard normal matrix provides an important theoretical and practical example of a subspace
embedding.
Example 7.2 (Gaussian Subspace Embedding). For any natural number k, a standard normal matrix
Γ ∈ Rd ×D is a subspace embedding with probability one when the embedding dimension d ≥ k. In
practice, it is preferable to select the embedding dimension d ≥ k +10 to ensure that the restricted singular
value σmin (Γ; L ∩ SD−1 ) is sufficiently positive, which makes the embedding more stable. See [HMT11] for
more details.
A Gaussian subspace embedding has superb dimension reduction properties. On the other hand,
standard normal matrices are expensive to generate, to store, and to perform arithmetic with. Therefore,
in most randomized NLA algorithms, it is better to use subspace embeddings that are discrete or sparse.
Our universality results demonstrate that, in a certain range of parameters, every matrix that follows
Model 2.4 enjoys the same subspace embedding properties as a Gaussian matrix.
Proposition 7.3 (Universality for Subspace Embedding). Suppose that
• The ambient dimension D is sufficiently large.
• The embedding dimension satisfies d ≤ D 6/5 .
• The random linear map Π : RD → Rd follows Model 2.4 with parameters p and ν.
Then, for each k-dimensional subspace L of RD ,
p
p
p
σmin (Π; L ∩ SD−1 ) ≥ d − k − o( D) with probability 1 − o(1).
In particular, Π is a subspace embedding of order k whenever d ≥ k + o(D). In these expressions, the little-o
suppresses constants that depend only on p and ν.
Proof. Proposition 7.3 is a consequence of Theorem II(a) and (4.3) because
p
p
p
p
p
p
Ed (L ∩ SD−1 ) ≥ d − δ(L ∩ SD−1 ) = d − δ(L) = d − k.
The last identity¡holds
p ¢ because the k-dimensional subspace L has statistical dimension k. We introduce
the error term o D to make sure that the stated result is only valid when the hypotheses of Theorem II
are in force.

Note that Proposition 7.3 applies to a sparse Rademacher linear map with a fixed, but arbitrarily
small, proportion of nonzero entries. This particular example has received extensive attention in recent
years [CW13, NN13, KN14, BDN15], although these works typically focus on the regime where the subspace dimension k is small and the sparsity level of the random linear map is a vanishing proportion of
the embedding dimension d .
Remark 7.4 (Prior Work). For the simple problem considered in Proposition 7.3, much sharper results are
available in the random matrix literature. See the paper [KY14] for a recent analysis, as well as additional
references.
Remark 7.5 (The Bai–Yin Limit for the Minimum Singular Value). One of the most important problems
in random matrix theory is to obtain bounds for the extreme singular values of a random matrix. The
Bai–Yin law [BY93] gives a near-optimal result in case the entries of the random matrix are independent
and standardized. We can reproduce a slightly weaker version of the Bai–Yin law for the minimum singular
value by modifying the proof of Proposition 7.3.
Fix an aspect ratio % ∈ (0, 1). For each natural number d , define k := k(d ) := b%d c. Draw a d × k random
matrix Φ(d ) from Model 2.4 with fixed parameters p and ν. For each ε > 0, we can apply Theorem II(a)
with E = Sk−1 to see that
n
o
¡
¢
p
P d −1/2 σmin Φ(d ) ≥ 1 − % − ε → 1 as d → ∞.

28

S. OYMAK AND J. A. TROPP

Here, σmin denotes the kth largest singular value of Φ(d ) .
Under these assumptions, it is known [Yin86] that the empirical distribution of the singular values of
p
(d )
Φ converges in probability to the Marčenko–Pastur density, whose support is the interval 1 ± %. It
follows that
n
o
¡
¢
p
P d −1/2 σmin Φ(d ) ≤ 1 − % + ε → 1 as d → ∞.
Therefore, we may conclude that
¡
¢
p
d −1/2 σmin Φ(d ) → 1 − % in probability.

In comparison, the Bai–Yin law [BY93, Thm. 2] gives the same conclusion almost surely when the entries
of Φ(d ) have four finite moments. See the recent paper [Tik15] for an optimal result.
7.2. Sketching and Least Squares. In randomized NLA, one of the core applications of dimension reduction is to solve over-determined least-squares problems, perhaps with additional constraints. This
idea is attributed to Sarlós [Sar06], and it has been studied intensively over the last decade; see the surveys [Mah11, Woo14] for more information. In this section, we develop sharp bounds for the simplest
version of this approach.
Suppose that A is a fixed D × n matrix with full column rank. Let y ∈ RD be a vector, and consider the
over-determined least-squares problem
kAx − yk2 .

minimize
n
x∈R

(7.1)

This problem can be expensive to solve when D À n. One remedy is to apply dimension reduction. Draw
a random linear map Π : RD → Rd from Model 2.4, and consider the compressed problem
kΠ(Ax − y)k2 .

minimize
n
x∈R

(7.2)

The question is how the quality of the solution of (7.2) depends on the embedding dimension d . The
following result provides an optimal estimate.
Proposition 7.6 (Randomized Least Squares: Error Bound). Instate the prevailing notation. Fix parameters
λ ∈ (0, 1) and % ∈ (0, 1) and ι ∈ (0, 1). Assume that
• The number D of constraints is sufficiently large as a function of the parameters.
• The embedding dimension d is comparable with the number D of constraints: λD ≤ d ≤ D.
• The embedding dimension d is somewhat larger than the number n of variables: d ≥ (1 + %)n.
With high probability, the solution xb to the reduced least-squares problem (7.2) satisfies
kA(xb − x ? )k2
2

kAx ? − yk

≤

n + ιd
,
d −n

(7.3)

where x ? is the solution to the original least-squares problem (7.1). In particular,
kA xb − yk2
2

kAx ? − yk

≤ (1 + ι)

d
d −n

In other words, the excess error kA(xb − x ? )k incurred in solving the compressed least-squares problem (7.2) is negligible as compared with the optimal value of the least-squares problem (7.1) if we choose
the embedding dimension d sufficiently large. Proposition 7.6 improves substantially on the most recent work [PW15, Cor. 2(a)], both in terms of the error bound and in terms of the assumptions on the
randomized linear map.
Let us remark that there is nothing special about ordinary least squares. We can also solve least-squares
problems with a convex constraint set by dimension reduction. For this class of problems, we can also
obtain optimal bounds by adapting the argument below. For example, see the results in Section 8.

UNIVERSALITY OF RANDOMIZED DIMENSION REDUCTION

29

Proof. Let x ? ∈ Rn be the solution to the original least-squares problem (7.1). Define the optimal residual
z ? := y − Ax ? ∈ RD , and recall that z ? is orthogonal to range(A). Moreover,
minn kAx − yk2 = kAx ? − yk2 = kz ? k2 .
x∈R

Without loss of generality, we may scale the problem so that kz ? k2 = 1.
Next, change variables. Define w := A(x − x ? ), and note that w is orthogonal to z ? . We can write the
reduced least-squares problem (7.2) as
minimize
w ∈range(A)

kΠ(w − z ? )k .

(7.4)

b to (7.4) to be close to zero.
When dimension reduction is effective, we expect the solution w
Since d ≥ (1 + %)n, we can use the fact (Proposition 7.3) that Π is a subspace embedding to obtain an a
b k ≤ R ∞ that holds with high probability. The number R ∞ is a constant that depends on
priori bound kw
nothing but ε. We only need this observation to ensure that we are optimizing over a compact set with
constant radius, so we omit the details.
Next, we invoke Theorem II(b) to bound the optimal value of the reduced least-squares problem (7.4).
Define the compact, convex set
E := {w ∈ range(A) : kw k ≤ R ∞ }.

Let ε > 0 be a parameter that will depend on the parameter ι. With high probability,
min

w ∈range(A)

kΠ(w − z ? )k = min kΠ(w − z ? )k ≤ (1 + ε) Ed (E − z ? ).
w ∈E

By direct calculation, we can bound the excess width above. Let P be the orthogonal projector onto the
range of A, and observe that
¢
¡p
Ed (E − z ? ) = E inf d kw − z ? k + g · (w − z ? )
w ∈E
¢
¡p
= E inf
d (kw k2 + 1)1/2 + g · w
w ∈E
¡p
¢
= E inf
d (kw k2 + 1)1/2 − kP g k kw k
w ∈E
¡p
p ¢
d (α2 + 1)1/2 − nα
≤ inf
0≤α≤R ∞
p
= d − n.
The first line is Definition 4.2, of the excess width. Next, simplify via the orthogonality of w and z ? and
the scaling kz ? k2 = 1. Use translation invariance of the infimum to remove z ? from the Gaussian term.
p
Apply Jensen’s inequality to draw the expectation inside the infimum, and note that E kP g k ≤ n because
rank(P ) = n. Then make the change of variables α = kw k, and solve the scalar convex optimization
problem. The infimum occurs at the value
n
α2opt :=
.
d −n
Since d ≥ (1 + %)n, we may be confident that αopt < R ∞ .
We have shown that, with high probability,
p
min kΠ(w − z ? )k ≤ (1 + ε) d − n.
(7.5)
w ∈range(A)

b k ≈ αopt . To prove the main result, we
Furthermore, we have evidence that the norm of the minimizer kw
p
compute the value of the optimization problem (7.4) restricted to points with kw k ≥ αopt 1 + ι0 , where
ι0 is a small positive number to be chosen later. Then we verify that the optimal value of the restricted
problem is usually larger than the bound (7.5) for the optimal value of (7.2). This argument implies that
p
kw
b k < αopt 1 + ι0 with high probability.
p
To that end, define R + := αopt 1 + ι0 , and introduce the compact set

E + := {w ∈ range(A) : R + ≤ kw k ≤ R ∞ }.

30

S. OYMAK AND J. A. TROPP

Theorem II(a) shows that, with high probability,
min kΠ(w − z ? )k ≥ (1 − ε) Ed (E + − z ? ).

w ∈E +

(7.6)

Calculating the excess width as before,
¢
¡p
d (α2 + 1)1/2 − kP g k α
R + ≤α≤R ∞
¡
¡p
p ¢
p ¢
≥ inf
d (α2 + 1)1/2 − nα − R ∞ E kP g k − n +
R + ≤α≤R ∞
¡p
¢
p
2
≥ d (R +
+ 1)1/2 − nR + − R ∞ .

Ed (E + − z ? ) = E

inf

(7.7)

p
p
Add and subtract nα to reach the second line, and use the fact that E kP g k ≤ n. Then apply the
Gaussian variance inequality, Fact A.1, to bound the expectation by one. The infimum occurs at R +
because the objective is convex and R + exceeds the unconstrained minimizer αopt .
Next, we simplify the expression involving R + . Setting ι0 := ιd /n, we find that
p
p
1 + ι0 n/d − n 1 + ι0
p
d −n


s
r
ι(d /n − 1) 
1+ι 
d −n 1+
=
d −n
1+ι
r
µ
¶
ι(d − n)
1 + ι/2 p
1+ι
≥
d −n −
=p
d − n.
d −n
2(1 + ι)
1+ι

p
p
d
2
+ 1)1/2 − nR + =
d (R +

(7.8)

The inequality follows from the linear upper bound for the square root at one.
Combine (7.6), (7.7), and (7.8) to arrive at
min kΠ(w − z ? )k ≥

w ∈E +

(1 − ε)(1 + ι/2) p
d − n.
p
1+ι

Comparing (7.5) with the last display, we discover that the choice ε := cι2 is sufficient to ensure that, with
high probability,
min kΠ(w − z ? )k > min kΠ(w − z ? )k .

w ∈E +

w ∈E

It follows that the minimum of (7.4) usually occurs on the set E \ E + . We determine that
kw
b k2 ≤ (1 + ιd /n) α2opt .
Reinterpret this inequality to obtain the stated result (7.3).
b k by considering the set of vectors E − := {w ∈ range(A) :
We can obtain a matching lower bound for kw
p
kw k ≤ R − } where R − := αopt 1 − ι0 . We omit the details.

Remark 7.7 (Prior Work). The idea of using random linear maps to accelerate the solution of least-squares
problems appears in the work of Sarlós [Sar06]. This approach has been extended and refined in the
literature on randomized NLA; see the surveys [Mah11, Woo14] for an overview. Most of this research is
concerned with randomized linear maps that have favorable computational properties, but the results are
much less precise than Proposition 7.6. Recently, Pilanci & Wainright [PW15] have offered a more refined
analysis of randomized dimension reduction for constrained least-squares problems, but it still falls short
of describing the actual behavior of these methods. Parts of the argument here is adapted from the work
of Oymak, Thrampoulidis, and Hassibi [OTH13, TOH15].

UNIVERSALITY OF RANDOMIZED DIMENSION REDUCTION

31

8. T HE P REDICTION E RROR FOR LASSO
Universality results have always played an important role in statistics. The most fundamental example
is the law of large numbers, which justifies the use of the sample average to estimate the mean of a general
distribution. Similarly, the central limit theorem permits us to build a confidence interval for the mean of
a distribution.
High-dimensional statistics relies on more sophisticated methods, often based on optimization, to
estimate population parameters. In particular, applied statisticians frequently employ the LASSO estimator [Tib96] to perform regression and variable selection in linear models. It is only recently that researchers
have developed theory [KM11, BM12, OTH13, DJM13, JM14, TAH15] that can predict the precise behavior
of the LASSO when the data are assumed to be Gaussian. It is a critical methodological challenge to
develop universality results that expand the range of models in which we can make confident assertions
about the performance of the LASSO.
In this section, we prove the first general universality result for the prediction error using a LASSO
model estimate. This theory offers a justification for using a LASSO model to make predictions when
the data derives from a sparse model. We expect that further developments in this direction will play an
important role in applied statistics.
8.1. The Sparse Linear Model and the LASSO. The LASSO is designed to perform simultaneous regression and variable selection in a linear model. Let us present a simple statistical model in which to study
the behavior of the LASSO estimator. Suppose that the random variable Y takes the form
Y = x · β? + σZ

(8.1)

where
•
•
•
•

The deterministic vector β? ∈ Rp of model parameters has at most s nonzero entries.
The random vector x ∈ Rp of predictor variables is drawn from Model 2.4.
The noise variance σ2 > 0 is known.
The statistical error Z is drawn from Model 2.4, independent of x.

We interpret x = (X 1 , . . . , X p ) as a family of predictor variables that we want to use to predict the value of
the response variable Y . Only the variables X j where (β? ) j 6= 0 are relevant to the prediction, while the
others are confounding. The observed value Y of the response is contaminated with a statistical error σZ .
These assumptions are idealized, but let us emphasize that our analysis holds even when the predictors
and the noise are heavy-tailed.
Suppose that we observe independent pairs (x 1 , Y1 ), . . . , (x n , Yn ) drawn from the model above, and let
z ∈ Rn be the unknown vector of statistical errors. One of the goals of sparse regression is to use this
b ∈ Rp of the model coefficients so that we can predict future responses.
data to construct an estimate β
That is, given a fresh random vector x 0 of predictor variables, we can predict the (unknown) response
Y0 = x 0 · β? + σZ0 using the linear estimate
b
Yb0 := x 0 · β.

We want to control the mean squared error in prediction, which is defined as
£
¤
MSEP := E |Yb0 − Y0 |2 | X , z .

(8.2)

Using the statistical model (8.1), it is easy to verify that
£
¤
b − β? ) + σZ0 |2 | X , z = kβ
b − β? k2 + σ2 .
MSEP = E |x 0 · (β

(8.3)

In other words, the prediction error is controlled by the squared error in estimating the model coefficients.
b of the model coefficients. The estimator
The LASSO uses convex optimization to produce an estimate β
is chosen arbitrarily from the set of solutions to the problem
minimize
p
β∈R

kX β − yk2

subject to

kβk`1 ≤ kβ? k`1 .

(8.4)

32

S. OYMAK AND J. A. TROPP

Mean Squared Error in Prediction (MSEP), LASSO Estimate, 16-Sparse Model in R 64
10

Asymptotic Theory
Rademacher (empirical)
20% Nonzero Rademacher (empirical)
Student t with 5 dof (empirical)

Empirical MSEP / Variance

9
8
7
6
5
4
3
2
1
0
40

50

60

70

80

90

100

Number of Subjects (n)

F IGURE 8.1: Universality of the LASSO Prediction Error. This plot shows the MSEP (8.2) obtained with the
LASSO estimator (8.4), averaged over design matrices X and statistical errors z. In the linear model (8.1),
the number of predictors p = 64; the number of active predictors s = 16; each nonzero coefficient (β? ) j in
the model has unit magnitude; the statistical error Z is Gaussian; the variance σ2 = 1; and the number n
of subjects varies. The dashed line marks the location of the phase transition for the number of subjects
required to identify the model exactly when the noise variance is zero. The gray curve delineates the
asymptotic upper bound n/(n − pψ`1 (s/p)) for the normalized MSEP from Proposition 8.1. The markers
give an empirical estimate (over 100 trials) for the MSEP when the design matrix X has the specified
distribution.

In this formula, the rows of the n × p matrix X are the observed predictor vectors x i . The entries of the
vector y ∈ Rn are the measured responses. For simplicity, we also assume that we have the exact side
information kβ? k`1 .
We can prove the following result on the squared error in the LASSO estimate of the sparse coefficient
model. This is the first universal statement that offers a precise analysis for this class of statistical models.
Proposition 8.1 (Universality of LASSO Prediction Error). Instate the prevailing notation. Choose parameters λ ∈ (0, 1) and % ∈ (0, 1) and ι ∈ (0, 1). Assume that
• The number n of subjects is sufficiently large as a function of the parameters.
• The number p of predictors satisfies λp ≤ n ≤ p 6/5 .
• The number n of subjects satisfies n ≥ (1 + %) pψ`1 (s/p).
With high probability over the observed data, the mean squared error in prediction (8.2) satisfies
MSEP ≤ (1 + ι)

σ2 n
.
n − pψ`1 (s/p)

(8.5)

The function ψ`1 is defined in (5.2). Furthermore, the bound (8.5) is sharp when n À pψ`1 (s/p) or when
σ2 → 0.
Proposition 8.1 gives an upper bound for the MSEP, which matches the low-noise limit (σ → 0) obtained
in the Gaussian case [OTH13]. See Figure 8.1 for a numerical experiment that confirms our theoretical
predictions. The proof of the result appears below in Section 8.2.
The assumptions in Proposition 8.1 are somewhat restrictive, in that the number n of subjects must be
roughly comparable with the number p of predictors. This condition can probably be relaxed, but the
error bound in Theorem II does not allow for a stronger conclusion. The argument can also be extended
to give even more precise formulas for the MSEP under the same assumptions. We also note that there is
nothing special about the `1 constraint in (8.4); similar results are valid for many other convex constraints.

UNIVERSALITY OF RANDOMIZED DIMENSION REDUCTION

33

8.2. Proof of Proposition 8.1. Without loss of generality, we may assume that the statistical model is
scaled so the noise level σ = 1. Define the sublevel set E of the `1 norm at the true parameter vector β? :
©
ª
E := u ∈ Rp : kβ? + uk`1 ≤ kβ? k`1 .
Note£that E¤ is a compact, convex set that contains the origin. Define the n × (p + 1) random matrix
Φ := X z , and note that Φ also follows Model 2.4. Making the change of variables u := β − β? , we can
rewrite the LASSO problem (8.4) in the form
° · ¸°
°
u °
°.
minimize °
Φ
(8.6)
°
°
−1
u∈E
This expression depends on the assumption that σ = 1. Let ub be an optimal point of the problem (8.6).
b 2 leads to a formula for the MSEP.
Referring to (8.3), we see that a formula for kuk
It will be helpful to introduce some additional sets. For a parameter α > 0, define the compact (but
typically nonconvex) set
©
ª
E α := u ∈ E : kuk = α .
We also define the compact and convex set
©
ª
E ≤α := u ∈ E : kuk ≤ α .

Observe that E α ⊂ E ≤α . Furthermore,
α ≤ α+

implies (1/α+ )E α+ ⊂ (1/α)E α .

(8.7)

The inclusion (8.7) holds because E is convex and contains the origin.
Let R ∞ be a constant that depends only on the parameters % and ι. Suppose that 0 ≤ R ≤ R + ≤ R ∞ . To
b < R + , it suffices to establish the inequality
prove that kuk
° · ¸°
° · ¸°
°
°
°
u °
° < min °Φ u ° .
min °
Φ
(8.8)
°
°
°
−1
−1 °
u∈E ≤R
u∈E R+
Indeed, recall that ub is the minimizer of the objective over E , and let u 0 be the point in E ≤R where the
left-hand minimum in (8.8) is attained. The objective is a convex function of u, so it does not decrease as
b ≥ R + , this line segment muss pass through E R+ , which is
u traverses the line segment from ub to u 0 . If kuk
impossible because the ordering (8.8) forces the objective to decrease on the way from E R+ to u 0 .
Fix the parameter R in the range 0 ≤ R ≤ R ∞ ; we will select a suitable value later. Theorem II(b)
demonstrates that, with high probability,
° · ¸°
°
¡
¢
¡
¢
p
p
u °
° ≤ En E ≤R × {−1} + o( n) ≤ En E R × {−1} + o( n).
min °
Φ
°
°
−1
u∈E ≤R
The second relation holds because the excess width decreases with respect to set inclusion. Observe that
¡
¢
¡p
¢
En E R × {−1} = E inf n(kt k2 + 1)1/2 + g · t
t ∈E R

p
= n(R 2 + 1)1/2 − E sup g · t
t ∈E R

¡
¢
p
= n(R 2 + 1)1/2 − R W (1/R)E R .

The last identity holds when we factor out kt k and identify the Gaussian width (3.7).
Fix the second parameter R + , such that R ≤ R + ≤ R ∞ . Theorem II(a) demonstrates that, with high
probability,
° · ¸°
°
¡
¢
p
u °
° ≥ En E R × {−1} − o( n).
min °
Φ
+
°
°
−1
u∈E R+
Much as before, we calculate the excess width:
¡
¢ p
¡
¢
En E R+ × {−1} = n(R +2 + 1)1/2 − R + W (1/R + )E R+
¡
¢
p
2
≥ n(R +
+ 1)1/2 − R + W (1/R)E R .

34

S. OYMAK AND J. A. TROPP

The last inequality holds because of (8.7) and the fact that the Gaussian width is increasing with respect to
set inclusion.
Combine the last four displays to reach
° · ¸°
°
¡
¢
p
p
u °
° ≤ n(R 2 + 1)1/2 − R W (1/R)E R + o( n)
min °
Φ
°
°
−1
u∈E ≤R
° · ¸°
°
¡
¢
p
p
u °
2
°.
≤ n(R +
+ 1)1/2 − R + W (1/R)E R − o( n) ≤ min °
Φ
°
−1 °
u∈E
R+

It follows that we can establish (8.8) by finding parameters for which 0 ≤ R ≤ R + ≤ R ∞ and
¡
¢¤
¡
¢¤ £p
£p
p
2
n(R +
+ 1)1/2 − R + W (1/R)E R − n(R 2 + 1)1/2 − R W (1/R)E R ≥ o( n).
To that end, we replace the Gaussian width by a number that does not depend on the parameter R:
¡
¢
¡
¢
¡
¢
W 2 (1/R)E R ≤ δ (1/R)E R ≤ δ cone(E ) ≤ pψ`1 (s/p) =: d .
The first relation is (3.8); the second follows from Definition 3.4; the last is the estimate (5.4). Moreover,
these bounds are sharp when R is sufficiently close to zero. Therefore, we just need to verify that
hp
p i hp
p i
p
2
n(R +
+ 1)1/2 − R + d − n(R 2 + 1)1/2 − R d ≥ o( n).
(8.9)
Once we choose R and R + appropriately, we can adapt the analysis in the proof of Proposition 7.6.
For α ≥ 0, introduce the function
p
p
f (α) := n(α2 + 1)1/2 − α d .
As in the proof of Proposition 7.6, by direct calculation, f is minimized at the value
R :=

d
.
n −d

¡
¢
Note that R is very close to zero when n À d , in which case d is an accurate bound for W 2 (1/R)E R .
Furthermore,
p
f (R) = n − d .
(8.10)

Now, make the selection

d + ιn
.
(8.11)
n −d
Since n ≥ (1 + %) d , we see that R + is bounded by a constant R ∞ that depends only on ι and %. Repeating
the calculation in (7.8), mutatis mutandis, we have
1 + ι/2 p
f (R + ) ≥ p
n − d.
(8.12)
1+ι
2
R+
:= (1 + ιn/d )R 2 =

Combining (8.10) and (8.12), we determine that
p
p
1 + ι/2 − 1 + ι p
n − d ≥ o( n).
f (R + ) − f (R) ≥
p
1+ι
The last inequality holds because ι is a fixed positive constant and we have assumed that n ≥ (1 + %)d .
In conclusion, we have confirmed the claim (8.9) for R and the value R + designated in (8.11). It follows
b ≤ R + with high probability.
that (8.8) holds with high probability, and so the optimizer of (8.6) satisfies kuk
Therefore, the formula (8.2) for the mean squared error yields the bound
n
2
b 2 + 1 ≤ R+
MSEP = kuk
+ 1 = (1 + ι)
.
n −d
Once again, we have used the assumption that σ = 1. By homogeneity, the MSEP must be proportional to
σ2 , which leads to the stated result (8.5). Finally, if we allow σ → 0 with the other parameters fixed, the
analysis here can be adapted to show that the error bound (8.5) is sharp.

UNIVERSALITY OF RANDOMIZED DIMENSION REDUCTION

35

Remark 8.2 (Prior Work). In the special case of a standard normal design X and a standard normal error
z, the result of Proposition 8.1 appeared in the paper [OTH13]. Our extension to more general random
models is new. Nevertheless, our proof has a lot in common with the analysis in [OTH13, TAH15].

36

S. OYMAK AND J. A. TROPP

Part III. Universality of the Restricted Minimum Singular Value: Proofs of Theorem II and
Theorem I(a)
In this part of the paper, we present a detailed proof of the universality law for the restricted singular
value of a random matrix, Theorem II, and the first part of the universality law for the embedding
dimension, Theorem I(a).
Section 9 contains our main technical result, which establishes universality for the bounded random
matrix model, Model 2.1. Section 10 extends the result for bounded random matrices to the heavy-tailed
random matrix model, Model 2.4. In Section 10.2, we obtain Theorem II as an immediate consequence
of the result for heavy-tailed matrices. Section 10.3 shows how to derive Theorem I(a) as an additional
consequence. The remaining sections in this part lay out the calculations that undergird the result for
bounded random matrices.
9. T HE R ESTRICTED S INGULAR VALUES OF A B OUNDED R ANDOM M ATRIX
The key challenges in establishing universality for the restricted minimum singular value are already
present in the case where the random matrix is drawn from the bounded model, Model 2.1. This section
presents a universality law for bounded random matrices, and it gives an overview of the calculations that
are required to establish this result.
9.1. Theorem 9.1: Main Result for the Bounded Random Matrix Model. The main technical result in
this paper is a theorem on the behavior of the restricted minimum singular value of a bounded random
matrix.
Theorem 9.1 (RSV: Bounded Random Matrix Model). Place the following assumptions:
• Let m and n be natural numbers with m ≤ n 6/5 .
• Let T be a closed subset of the unit ball Bn in Rn .
• Draw an m × n random matrix Φ from Model 2.1 with bound B .
Then the squared restricted singular value σ2min (Φ; T ) has the following properties:

p
(1) The squared restricted singular value concentrates about its mean on a scale of B 2 m + n. For each
ζ ≥ 0,
©
ª
2
P σ2min (Φ; T ) ≤ E σ2min (Φ; T ) − CB 2 ζ ≤ e−ζ /m , and
p
ª
©
2
P σ2min (Φ; T ) ≥ E σ2min (Φ; T ) + CB 2 ζ ≤ Ce−ζ /(m+ζ n) .

(2) The expectation of the squared restricted singular value is bounded below in terms of the excess
width:
¡
¢2
E σ2min (Φ; T ) ≥ Em (T ) + − CB 2 (m + n)0.92 .
(3) If T is a convex set, the squared restricted singular value is bounded above in terms of the excess
width:
¡
¢2
E σ2min (Φ; T ) ≤ Em (T ) + + CB 4 (m + n)0.94 .
Furthermore, the entries of Φ need not be symmetric for this result to hold.
The proof of this result will occupy us for the rest of this part of the paper. This section summarizes the
required calculations, with cross-references to the detailed arguments.
9.2. Proof of Theorem 9.1(1): Concentration. Theorem 9.1(1) states that the squared restricted singular
value σ2min (Φ; T ) concentrates around its mean. We prove this claim in Proposition 11.1, which appears
below. The argument depends on some concentration inequalities that are derived using the entropy
method. This approach is more or less standard, so we move on to the more interesting part of the proof.

UNIVERSALITY OF RANDOMIZED DIMENSION REDUCTION

37

9.3. Setup for Proof of Theorem 9.1(2) and (3): Dissection of the Index Set. Let us continue with the
proof of Theorem 9.1, conclusions (2) and (3). The overall approach is the same in both cases, but some of
the details differ.
The first step is to dissect the index set T into appropriate subsets. For each set J ⊂ {1, . . . , n}, we
introduce a closed subset T J of T via the rule
©
ª
T J := t ∈ T : |t j | ≤ (#J )−1/2 for all j ∈ J c ,
(9.1)
where J c := {1, . . . , n} \ J . In other words, T J contains all the vectors in T where the coordinates listed in J c
are sufficiently small. Note that convexity of the set T implies convexity of each subset T J .
Fix a number k ∈ {1, . . . , n}. Since T is a subset of the unit ball Bn , every vector t ∈ T satisfies
©
ª
# j : |t j | > k −1/2 ≤ k.
Therefore, t belongs to some subset T J where the cardinality #J = k, and we have the decomposition
[
T = #J =k T J .
(9.2)
It is clear that the number of subsets T J in this decomposition satisfies
Ã !
³ en ´k
n
#{T J : #J = k} =
≤
.
k
k

(9.3)

We must limit the cardinality k of the subsets, so we can control the number of subsets we need to
examine.
9.4. Proof of Theorem 9.1(2): Lower Bound for the RSV. Let us proceed with the proof of Theorem 9.1(2),
the lower bound for the RSV. For the time being, we fix the parameter k that designates the cardinality of
the sets J . We require that k ≥ m 2/3 .
First, we pass from the restricted singular value σmin (Φ; T ) over the whole set T to a bound that depends
on σmin (Φ; T J ) for the subsets T J . Proposition 12.2 gives the comparison
q
E σ2min (Φ; T ) ≥ min E σ2min (Φ; T J ) − CB 2 km log(n/k).
(9.4)
#J =k

We have used the decomposition (9.2) and the bound (9.3) on the number of subsets in the decomposition
to invoke the proposition. The main ingredient in the proof of this estimate is the concentration inequality
for restricted singular values, Proposition 11.1.
Let us focus on a specific subset T J . To study the restricted singular value σmin (Φ; T J ), we want to
replace the entries of the random matrix Φ with standard normal random variables. Proposition 13.1
allows us to make partial progress toward this goal. Let Γ be an m×n standard normal matrix, independent
from Φ. Define an m × n random matrix Ψ := Ψ(J ) where Ψ J = Φ J and Ψ J c = Γ J c . Then
E σ2min (Φ; T J ) ≥ E σ2min (Ψ; T J ) −

CB 2 m 1/3 n log(mn)
k 1/2

.

(9.5)

This bound requires the assumption that k ≥ m 2/3 . The argument is based on the Lindeberg exchange
principle, but we have used this method in an unusual way. For a vector t ∈ T J , the definition (9.1) gives us
control on the magnitude of the entries listed in J c , which we can exploit to replace the column submatrix
Φ J c with Γ J c . The coordinates of t listed in J may be large, so we cannot replace the column submatrix Φ J
without incurring a significant penalty. Instead, we just leave it in place.
Next, we want to compare the expected RSV on the right-hand side of (9.5) with the excess width of the
set T J . Proposition 14.1 provides the bound
³
p ´2 ³
p ´2
E σ2min (Ψ; T J ) ≥ Em (T J ) − CB 2 k ≥ Em (T ) − CB 2 k .
(9.6)
+

+

The second inequality is a consequence of the facts that T J ⊂ T and that the excess width is decreasing
with respect to set inclusion. The calculation in Proposition 14.1 uses the Gaussian Minimax Theorem (see

38

S. OYMAK AND J. A. TROPP

Fact A.3) to simplify the average with respect to the standard normal matrix Γ. We also invoke standard
results from nonasymptotic random matrix theory to control the expectation over Φ J .
We can obtain a simple lower bound on the last term in (9.6) by linearizing the convex function (·)2+ at
the point Em (T ):
³
p
p ¡
p ´2 ¡
¡
¢2
¢2
¢
(9.7)
Em (T ) − CB 2 k ≥ Em (T ) + − CB 2 k Em (T ) + ≥ Em (T ) + − CB 2 km.
+

The last estimate follows from the observation that
¢ p
¡p
¢
¡p
Em (T ) = E inf m kt k + g · t ≤ E m kt0 k + g · t0 ≤ m.
t ∈T

(9.8)

In this calculation, t 0 is an arbitrary point in T .
Finally, we sequence the four displays (9.4), (9.5), (9.6), and (9.7) and combine error terms to obtain
q
¡
¢2 CB 2 m 1/3 n log(mn)
2
E σ2min (Φ; T ) ≥ Em (T ) + −
−
CB
km log(n/k).
k 1/2
Up to logarithms, an optimal choice of the cardinality parameter is k = dm −1/6 ne. Since m ≤ n 6/5 , this
choice ensures that k ≥ m 2/3 . We conclude that
¡
¢2
E σ2min (Φ; T ) ≥ Em (T ) + − CB 2 m 5/12 n 1/2 log(mn)
¡
¢2
≥ Em (T ) + − CB 2 (m + n)11/12 log(m + n).
Combine the logarithm with the power, and adjust the constants to complete the proof of Theorem 9.1(2).
9.5. Proof of Theorem 9.1(3): Upper Bound for the RSV of a Convex Set. At a high level, the steps in the
proof of Theorem 9.1(3) are similar with the argument in the last section. Many of the technical details,
however, depend on convex duality arguments.
As before, we fix the cardinality parameter k, with the requirement k ≥ m 2/3 . The first step is to pass
from σmin (Φ; T ) to σmin (Φ; T J ). We have
E σ2min (Φ; T ) ≤ min E σ2min (Φ; T J ).
#J =k

(9.9)

This bound is a trivial consequence of the facts that T J ⊂ T for each subset J of {1, . . . , n} and that σmin (Φ; ·)
is decreasing with respect to set inclusion.
Select any subset T J . We invoke Proposition 13.1 to exchange most of the entries of the random matrix
Φ for standard normal variables. Using the same random matrix Ψ from the last section, we have
E σ2min (Φ; T J ) ≤ E σ2min (Ψ; T J ) +

CB 2 m 1/3 n log(mn)

.
(9.10)
k 1/2
The bound (9.10) requires the assumption k ≥ m 2/3 , and the proof is identical with the proof of the lower
bound (9.5).
Next, we compare the expected RSV on the right-hand side of (9.10) with the excess width. Proposition 14.1 delivers
³
p ´2
E σ2min (Ψ; T J ) ≤ Em (T J ) + CB 2 k .
(9.11)
+

This argument is more complicated than the analogous lower bound (9.6), and it depends on the convexity
of T J . We also apply the assumption that k ≥ m 2/3 here.
Proposition 12.1 allows us to replace the excess width of T J in (9.11) with the excess width of T :
q
(9.12)
Em (T J ) ≤ Em (T ) + C k log(n/k).
We use the decomposition (9.2) and the bound (9.3) on the number of sets T J to invoke the proposition.
This proof depends on the Gaussian concentration inequality.
Sequence the bounds (9.9), (9.10), (9.11), and (9.12), and combine the error terms to arrive at
q
³
´2 CB 2 m 1/3 n log(mn)
E σ2min (Φ; T ) ≤ Em (T ) + CB 2 k log(n/k) +
.
+
k 1/2

UNIVERSALITY OF RANDOMIZED DIMENSION REDUCTION

39

Expand the square using (9.8) to reach
E σ2min (Φ; T ) ≤

Em (T )

¡

¢2

+ + CB

2

µ

m 1/3 n log(mn)
k 1/2

¶
q
2
+ km log(n/k) + B k log(n/k) .

Select k = dn 4/5 e to arrive at
¡
¢2
E σ2min (Φ; T ) ≤ Em (T ) + + CB 2 (m 1/3 n 3/5 + n 2/5 m 1/2 ) log(n) + CB 4 n 4/5 log(mn)
¡
¢2
≤ Em (T ) + + CB 4 (m + n)14/15 log(m + n).

Combine the power with the logarithm, and adjust constants to finish the proof of Theorem 9.1(3).
10. T HE R ESTRICTED S INGULAR VALUES OF A H EAVY-TAILED R ANDOM M ATRIX
In this section, we present an extension of Theorem 9.1 to the heavy-tailed matrix model, Model 2.4.
In Section 10.2, we explain how the universality result for the restricted singular value, Theorem II, is an
immediate consequence. In Section 10.3, we show how to derive the first half of the universality result for
the embedding dimension, Theorem I(a).
10.1. Corollary 10.1: Main Result for the p-Moment Random Matrix Model. We can extend Theorem 9.1 to the heavy-tailed random matrix model, Model 2.4 using a truncation argument. The following
corollary contains a detailed statement of the result.
Corollary 10.1 (RSV: p-Moment Random Matrix Model). Fix parameters p > 4 and ν ≥ 1. Place the
following assumptions:
• Let m and n be natural numbers with m ≤ n 6/5 .
• Let T be a closed subset of the unit ball Bn in Rn .
• Draw an m × n random matrix Φ that satisfies Model 2.4 with given p and ν.
Then the restricted singular value σmin (Φ; T ) has the following properties:
(1) With high probability, the restricted singular value is bounded below by the excess width:
©
¡
¢
ª
P σmin (Φ; T ) ≤ Em (T ) + − Cp ν(m + n)1/2−κ(p) ≤ Cp (m + n)1−p/4 .

(10.1)

(2) If T is a convex set, with high probability, the restricted singular value is bounded above by the
excess width:
©
¡
¢
ª
P σmin (Φ; T ) ≥ Em (T ) + + Cp ν2 (m + n)1/2−κ(p) ≤ Cp (m + n)1−p/4 .
(10.2)
The function κ(p) is strictly positive for p > 4, and the constant Cp depends only on p.
The proof of Corollary 10.1 appears below in Section 15. The main idea is to truncate each entry of the
heavy-tailed random matrix Φ individually. We can treat the bounded part of the random matrix using
Theorem 9.1. We show that the tails are negligible by means of a relatively simple norm bound for random
matrices, Fact B.2.
10.2. Proof of Theorem II from Corollary 10.1. Theorem II is an easy consequence of Corollary 10.1.
Recall the assumptions of the theorem:
•
•
•
•

The embedding dimension satisfies λD ≤ d ≤ D 6/5 .
E is a closed subset of the unit ball in RD . p
The d -excess width of E satisfies Ed (E ) ≥ % d .
The d × D random linear map Π follows Model 2.4 with parameters p > 4 and ν ≥ 1.

Therefore, we may apply Corollary 10.1 with Φ = Π and T = E to see that
©
¡
¢
ª
P σmin (Π; E ) ≤ Ed (E ) + − Cp ν(d + D)1/2−κ(p) ≤ Cp D 1−p/4 , and
©
¡
¢
ª
P σmin (Π; E ) ≥ Ed (E ) + + Cp ν2 (d + D)1/2−κ(p) ≤ Cp D 1−p/4 if E is convex.

40

S. OYMAK AND J. A. TROPP

For simplicity, we have dropped the embedding dimension d from the right-hand side of the bounds in
the last display.
To prove Theorem II, it suffices to check that we can make the error term Cp ν2 (d + D)1/2−κ(p) smaller
than εEd (E ) if we select the ambient dimension D large enough. Indeed, the conditions D ≤ λ−1 d and
d 1/2 ≤ %−1 Ed (E ) ensure that
(d + D)1/2−κ(p) ≤ (1 + λ−1 )1/2 d 1/2−κ(p)
≤ (1 + λ−1 )1/2 %−1 Ed (E )d −κ(p)
(1 + λ−1 )1/2 %−1 λ−κ(p)

Ed (E )
D κ(p)
Since κ(p) is positive, there is a number N := N (p, ν, λ, %, ε) for which D ≥ N implies
≤

Cp ν2 (d + D)1/2−κ(p) ≤ εEd (E ).
This is what we needed to show.
10.3. Proof of Theorem I(a) from Corollary 10.1. Theorem I(a) is also an easy consequence of Corollary 10.1. Recall the assumptions of the theorem:
• E is a compact subset of RD that does not contain the origin.
• The statistical dimension of E satisfies δ(E ) ≥ %D.
• The d × D random linear map Π follows Model 2.4 with parameters p > 4 and ν ≥ 1.
In this section, we consider the regime where the embedding dimension d ≥ (1 + ε) δ(E ). We need to
demonstrate that
P {0 ∉ Π(E )} = P {E ∩ null(Π) = ;} ≥ 1 − Cp D 1−p/4 .
(10.3)
We begin with a reduction to a specific choice of the embedding dimension d . Let Πm be the m × D
matrix formed from the first m rows of the random linear map Π. The function m 7→ P {E ∩ null(Πm ) = ;}
is weakly increasing because m 7→ null(Πm ) is a decreasing sequence of sets. Therefore, it suffices to
verify (10.3) in the case where d = d(1 + ε) δ(E )e. Note that d ≤ 2D + 1 because the statistical dimension
δ(E ) ≤ D and ε < 1.
Introduce the spherical retraction Ω := θ(E ). Proposition 3.8 and (3.2) demonstrate that
σmin (Π; Ω) > 0 implies 0 ∉ Π(Ω) implies 0 ∉ Π(E ).
Therefore, to check (10.3), it suffices to produce a high-probability lower bound on the restricted singular
value σmin (Π; Ω). With the choices Φ = Π and T = Ω, Corollary 10.1 yields
©
¡
¢
ª
P σmin (Π; Ω) ≥ Ed (Ω) + − Cp ν(d + D)1/2−κ(p) ≥ 1 − Cp D 1−p/4 .
To complete the proof, we need to verify that our hypotheses imply

Ed (Ω) > Cp ν(d + D)1/2−κ(p) .
This point follows from two relatively short calculations.
Since Ω is a subset of the unit sphere, we quickly compute ite excess width:
p
¡p
¢ p
Ed (Ω) = E inf d kxk + g · x ≥ d − δ(Ω)
x∈Ω
p
p
¡p
¢p
= d − δ(E ) ≥ 1 + ε − 1 δ(E ).

(10.4)

(10.5)

The second identity holds because Ω is a subset of the unit sphere, and we have used the relation (4.3).
Recall that the statistical dimension of a general set E is defined as δ(E ) = δ(θ(E )), and then introduce the
value d = d(1 + ε) δ(E )e of the embedding dimension.
Meanwhile, we can bound the dimensional term in (10.4) above:
p
(d + D)1/2−κ(p) ≤ CD 1/2−κ(p) ≤ C%−1/2 D −κ(p) δ(E ).

UNIVERSALITY OF RANDOMIZED DIMENSION REDUCTION

41

The first inequality holds because d ≤ 2D + 1, and the second inequality uses the assumption D ≤ %−1 δ(E ).
Since κ(p) is positive, we can find a number N := N (p, ν, %, ε) for which D ≥ N implies that
¢p
¡p
Cp ν(d + D)1/2−κ(p) < 1 + ε − 1 δ(E ).
Combine the last display with (10.5) to determine that the claim (10.4) is valid.
11. T HEOREM 9.1: C ONCENTRATION FOR R ESTRICTED S INGULAR VALUES
In this section, we demonstrate that the restricted minimum singular value of a bounded random
matrix concentrates about its mean value. This result yields Theorem 9.1(1).
Proposition 11.1 (Theorem 9.1: Concentration). Let S be a closed subset of Bn . Let Φ be an m × n random
matrix drawn from Model 2.1 with uniform bound B . For all ζ ≥ 0,
©
ª
2
P σ2min (Φ; S) ≤ E σ2min (Φ; S) − CB 2 ζ ≤ e−ζ /m
(11.1)
p
© 2
ª
2
P σmin (Φ; S) ≥ E σ2min (Φ; S) + CB 2 ζ ≤ e−ζ /(m+ζ n) .
(11.2)
The proof relies on some modern concentration inequalities that are derived using the entropy method.
We establish the bound (11.1) on the lower tail in Section 11.1; the bound (11.2) on the upper tail appears
in Section 11.2.
In several other parts of the paper, we rely on variants of Proposition 11.1 that follow from essentially
the same arguments. We omit the details of these proofs to avoid repetition.
11.1. Proposition 11.1: The Lower Tail of the RSV. First, we establish that the restricted singular value
is unlikely to be much smaller than its mean. The proof depends on an exponential moment inequality
derived using Massart’s modified logarithmic Sobolev inequality [Mas00]. For instance, see [BLM13,
Thm. 6.27] or [Mau12, Thm. 19].
Fact 11.2 (Self-Bounded Random Variable: Lower Tail). Let (X 1 , . . . , X p ) be an independent sequence of
real random variables. For a nonnegative function f : Rp → R+ , define
Y :=
supi Y :=

f (X 1 , . . . , X i −1 , X i , X i +1 , . . . , X p ),
sup

α∈supp(X i )

and

f (X 1 , . . . , X i −1 , α, X i +1 , . . . , X p ) for i = 1, . . . , p.

Suppose that
∆− :=
Then, for ζ ≥ 0,

Xp ¡
i =1

supi Y − Y

¢2

≤ aY + b

where a, b ≥ 0.

¶
−ζ2 /2
.
a EY +b
The function supp(·) returns the support of a random variable.
P {Y ≤ E Y − ζ} ≤ exp

µ

With this fact at hand, we may derive the lower tail bound.
Proof of Proposition 11.1, Eqn. (11.1). Introduce the random variable
´2
Xm ³Xn
Y := σ2min (Φ; S) = min kΦsk2 = min i =1
ϕ
s
.
j =1 i j j
s∈S

s∈S

(i j )

For each index pair (i , j ) and real number α, define a random matrix Φα by replacing the (i , j ) entry ϕi j
of Φ with the number α. Now, the random variable
¡ (i j ) ¢
(i j )
supi j Y = max σ2min Φα ; S = max min kΦα sk2 .
|α|≤B

|α|≤B s∈S

We must evaluate the lower variance proxy
Xm Xn ¡
¢2
∆− := i =1 j =1 supi j Y − Y .

42

S. OYMAK AND J. A. TROPP

To that end, select a point t ∈ arg mins∈S kΦsk2 . For each index pair (i , j ),
(i j )

(i j )

supi j Y − Y = max min kΦα sk2 − min kΦsk2 ≤ max kΦα t k2 − kΦt k2 .
|α|≤B s∈S

s∈S

|α|≤B

(i j )

The matrix Φα differs from Φ only in the i th row. Therefore, when we expand the squared norms into
components, all of the components cancel except for the i th one. We discover that
³¡
Xn
¢2 ¡ Xn
¢2 ´
supi j Y − Y ≤ max (α − ϕi j )t j + `=1 ϕi ` t ` −
ϕi ` t `
`=1
|α|≤B
³
´
Xn
= max (α − ϕi j )2 t 2j + 2(α − ϕi j )t j `=1 ϕi ` t `
|α|≤B
(11.3)
³
¯Xn
¯´
≤ max (α − ϕi j )2 t 2j + 2 |α − ϕi j | |t j | ¯ `=1 ϕi ` t ` ¯
|α|≤B
¯Xn
¯
≤ 4B 2 t 2j + 4B |t j | ¯ `=1 ϕi ` t ` ¯ .
The last inequality holds because |α| ≤ B and |ϕi j | ≤ B . As a consequence,
¯Xn
¯ ´2
¢2 ³
¢2
¡
¡Xn
supi j Y − Y ≤ 4B 2 t 2j + 4B |t j | ¯ `=1 ϕi ` t ` ¯ ≤ 32B 4 t 4j + 32B 2 t 2j
ϕ t .
`=1 i ` `
Sum over pairs (i , j ) to arrive at
Xm Xn ¡
¢2 Xm Xn ³
¡Xn
¢2 ´
4 4
2 2
sup
Y
−
Y
≤
32B
t
+
32B
t
ϕ
t
ij
j
j
i =1
j =1
i =1
j =1
`=1 i ` `
X
X
¡
¢2
m
n
≤ 32B 4 m + 32B 2 i =1
ϕ t
`=1 i ` `
= 32B 4 m + 32B 2 kΦt k2
= 32B 4 m + 32B 2 min kΦsk2 .
s∈S

To reach the second line, we used the fact that kt k`4 ≤ kt k ≤ 1. The last line depends on the definition of t .
In summary, we have demonstrated that
∆− ≤ 32B 2 Y + 32B 4 m.
To apply Fact 11.2, we need a bound for the expectation of Y . Designate a point s 0 ∈ S, and calculate that
E Y ≤ E kΦs 0 k2 = m ks 0 k2 ≤ m.

The identity holds because Φ has independent, standardized entries. Fact 11.2 ensures that
¶
µ
¶
µ
−ζ2 /2
−ζ2
P {Y ≤ E Y − ζ} ≤ exp
≤ exp
.
32B 2 E Y + 32B 4 m
128B 4 m



Rewrite this formula to complete the proof of (11.1).

11.2. Proposition 11.1: The Upper Tail of the RSV. Next, we establish that the restricted singular value of
a bounded random matrix is unlikely to be much larger than its mean. The proof depends on another tail
inequality for self-bounded random variables. This result also follows from Massart’s modified log-Sobolev
inequality [Mas00]; the argument is similar to the proofs of [Mau12, Thms. 18, 19]
Fact 11.3 (Self-Bounded Random Variable: Upper Tail). Let (X 1 , . . . , X p ) be an independent sequence of
real random variables. For a function f : Rp → R, define
Y :=
supi Y :=

f (X 1 , . . . , X i −1 , X i , X i +1 , . . . , X p ),
sup

α∈supp(X i )

and

f (X 1 , . . . , X i −1 , α, X i +1 , . . . , X p ) for i = 1, . . . , p.

Suppose that supi Y − Y ≤ L uniformly for a fixed value L and that
Xp ¡
¢2
∆− := i =1 supi Y − Y ≤ aY + b where a, b ≥ 0.

UNIVERSALITY OF RANDOMIZED DIMENSION REDUCTION

43

Then, for ζ ≥ 0,

¶
−ζ2 /2
.
(a E Y + b) + (a + L)ζ
The function supp(·) returns the support of a random variable.
P {Y ≥ E Y + ζ} ≤ exp

µ

Proof of Proposition 11.1, Eqn. (11.2). We proceed as in the proof of (11.1). It just remains to verify the
uniform bound on supi j Y − Y . Starting from (11.3), we calculate that
¯Xn
¯
supi j Y − Y ≤ 4B 2 t 2j + 4B |t j | ¯ `=1 ϕi l t ` ¯
¡Xn
¢1/2
≤ 4B 2 + 4B
ϕ2
`=1 i `
p
≤ 4B 2 + 4B 2 n
p
≤ 8B 2 n.
This calculation relies on the fact that kt k ≤ 1 and the entries of Φ have magnitude bounded by B . Apply
Fact 11.3 to complete the argument.

12. T HEOREM 9.1: P ROBABILITY B OUNDS FOR D ISSECTIONS
In this section, we establish some results that compare the expectation of a minimum of random
variables indexed by a set with the expectations of the minima indexed by subsets. These facts are easy
consequences of concentration phenomena.
12.1. Dissection of the Excess Width. First, we show that the excess width of a set can be related to the
excess width of a collection of subsets.
Proposition 12.1 (Theorem 9.1: Dissection of Excess Width). Consider a closed subset T of the unit ball
Bn that has been decomposed into a finite number of closed subsets T J :
[
T = J ∈J T J .
For each m ≥ 0, it holds that
q
³
¢´
¡p
¢
¡p
≥ min E min m kt k + g · t − C log(#J ).
E min m kt k + g · t
t ∈T

+

J ∈J

t ∈T J

In other words,
q
¡
¢
¡
¢
min Em (T J ) + ≤ Em (T ) + + C log(#J ).
J ∈J

Proof. Since T =

S

J ∈J

T J , we can stratify the minimum over T :
¡p
¢
¡p
¢
min m kt k + g · t = min min m kt k + g · t .
J ∈J t ∈T J

t ∈T

We will obtain a lower tail bound for the minimum over T by combining lower tail bounds for each
minimum over T J . Then we integrate the tail probability to obtain the required expectation bound.
Each subset T J is contained in Bn , so the map
¡p
¢
g 7→ min m kt k + g · t
t ∈T J

is 1-Lipschitz. The Gaussian concentration inequality, Fact A.2, provides a tail bound. For each J ∈ J and
for each λ ≥ 0,
½
¾
¡p
¢
¡p
¢
2
P min m kt k + g · t ≤ E min m kt k + g · t − λ ≤ e−λ /2 .
t ∈T J

t ∈T J

Apply the union bound over J ∈ J to see that, for all ζ ≥ 0,
½
¾
¢
¡p
¢ q
¡p
P min m kt k + g · t ≤ min E min m kt k + g · t − 2 log(#J ) − ζ
t ∈T

J ∈J

t ∈T J

44

S. OYMAK AND J. A. TROPP

≤ (#J )e−(

p

2 log(#J )+ζ)2 /2

≤ e−ζ

2

/2

.

Using the latter estimate, we quickly compute the excess width of T . Abbreviate
¡p
¢
¢ q
¡p
Y := min m kt k + g · t and α := min E min m kt k + g · t − 2 log(#J ).
J ∈J

t ∈T

t ∈T J

If α ≤ 0, the stated result is trivial, so we may assume that α > 0. The integration by parts representation of
the expectation yields
Z α
Z α
Z α
Z α
p
2
(E Y )+ ≥
P {Y > ζ} dζ =
P {Y > α − ζ} dζ = α −
P {Y ≤ α − ζ} dζ ≥ α −
e−ζ /2 dζ > α − π/2.
0

0

0

0

Reintroduce the values of Y and α, and combine constants to complete the argument.



12.2. Dissection of the Restricted Singular Value. Next, we show that the minimum singular value of a
random matrix, restricted to a set, is controlled by the minimum singular value, restricted to subsets.
Proposition 12.2 (Theorem 9.1: Dissection of RSV). Consider a closed subset T of the unit ball Bn , and
assume that it has been decomposed into a finite number of closed subsets T J :
[
T = J ∈J T J .
Let Φ be an m × n random matrix that satisfies Model 2.1 with uniform bound B . Then
q
min E σ2min (Φ; T J ) ≤ E σ2min (Φ; T ) + CB 2 m log(#J ).
J ∈J

Proof. The argument is similar with the proof of Proposition 12.1. Since T =

S

J ∈J

TJ ,

σ2min (Φ; T ) = min kΦt k2 = min min kΦt k2 = min σ2min (Φ; T J ).
J ∈J t ∈T J

t ∈T

J ∈J

The lower tail bound (11.1) for restricted singular values implies that, for all λ ≥ 0,
©
ª
2
4
P σ2min (Φ; T J ) ≤ E σ2min (Φ; T J ) − λ ≤ e−λ /(CB m) .

Next, we take a union bound. For all ζ ≥ 0,
½
¾
q
2
2
4
P σmin (Φ; T ) ≤ min E σmin (Φ; T J ) − CB m log(#J ) − ζ
J ∈J

p 4
2
4
2
4
≤ (#J )e−( CB m log(#J )+ζ) /(CB m) ≤ e−ζ /(CB m) .

Define a random variable Y and a constant α:
Y := σ2min (Φ; T ) and α := min E σ2min (Φ; T J ) −
J ∈J

q
CB 4 m log(#J ).

If α ≤ 0, the stated result is trivial, so we may assume that α > 0. Calculating as in Proposition 12.1,
EY ≥

α

Z
0

P {Y > ζ} dζ =

α

Z
0

P {Y > α − ζ} dζ
Z
= α−

Simplify this bound to complete the proof.

α
0

P {Y ≤ α − ζ} dζ ≥ α −

Z
0

α

e−ζ

2

/(CB 4 m)

p
dζ ≥ α − CB 2 m.



UNIVERSALITY OF RANDOMIZED DIMENSION REDUCTION

45

13. T HEOREM 9.1: R EPLACING M OST E NTRIES OF THE R ANDOM M ATRIX
In this section, we show that it is possible to replace most of the entries of a random matrix Φ with
standard normal random variables without changing the restricted singular value σmin (Φ; T J ) very much.
Proposition 13.1 (Theorem 9.1: Partial Replacement). Let Φ be an m × n random matrix that satisfies
Model 2.1 with magnitude bound B . Let J be a subset of {1, . . . , n} with cardinality k, and let T J be a closed
subset of Bn for which
t ∈ T J implies |t j | ≤ k −1/2 for each index j ∈ J c .
(13.1)
Define an m × n random matrix Ψ where
ΨJ = ΦJ
Assuming that k ≥ m

2/3

and Ψ J c = Γ J c .

, we have
¯
¯
¯
¯
¯E min kΦt k2 − E min kΨt k2 ¯
¯
¯
t ∈T J

t ∈T J

≤

(13.2)

CB 2 m 1/3 n log(mn)
k 1/2

.

(13.3)

Equivalently,
¯ 2
¯
¯E σ (Φ; T J ) − E σ2 (Ψ; T J )¯
min
min

≤

CB 2 m 1/3 n log(mn)
k 1/2

.

As usual, Γ is an m × n standard normal matrix.
The hypothesis (13.1) is an essential ingredient in the proof of Proposition 13.1. Indeed, we can only
exchange the elements of the random matrix Φ in the columns indexed by J c because we depend on the
uniform bound k −1/2 to control the replacement errors.
13.1. Proof of Proposition 13.1. The proof of Proposition 13.1 involves several steps, so it is helpful to
give an overview before we begin in earnest. Throughout this discussion, the index set J is fixed.
Let ε ∈ (0, 1) be a discretization parameter. The first step in the argument is to replace the index set T J
by a finite subset T Jε with cardinality log(#T Jε ) ≤ n log(3/ε). We obtain the bounds
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
2
2¯
2
2¯
(13.4)
¯E min kΦt k − E minε kΦt k ¯ ≤ 2mnε and ¯E min kΨt k − E minε kΨt k ¯ ≤ 2mnε.
¯ t ∈T J
¯
¯ t ∈T J
¯
t ∈T J
t ∈T J
See Lemma 13.2 for details, which are quite standard.
Next, we introduce a smoothing parameter β > 0, and we define the soft-min function:
X
2
1
F : Rm×n → R where F (A) := − log t ∈T ε e−βkAt k .
J
β

(13.5)

It is advantageous to work with the soft-min because it is differentiable. Lemma 13.3 demonstrates that
we pay only a small cost for passing to the soft-min:
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
¯
2
−1
ε
2
(13.6)
¯E minε kΦt k − E F (Φ)¯ ≤ β log(#T J ) and ¯E minε kΨt k − E F (Ψ)¯ ≤ β−1 log(#T Jε ).
¯ t ∈T J
¯
¯ t ∈T J
¯
This argument is also standard.
Finally, we compare the expectation of the soft-min, evaluated at each of the random matrices:
|E F (Φ) − E F (Ψ)| ≤

C(βB 4 + β2 B 6 )mn

.
(13.7)
k 3/2
Lemma 13.4 encapsulates the this argument, which is based on the Lindeberg principle (Fact 13.6, below).
The idea is to replace one entry of Φ J c at a time with the corresponding entry of Ψ J c , which is a Gaussian
random variable. We lose very little with each exchange because the function F is smooth and the vectors
in T Jε are bounded on the coordinates in J c .

46

S. OYMAK AND J. A. TROPP

Combine the relations (13.4), (13.6), and (13.7) to obtain an estimate for the total error:
¯
¯
4
2 6
¯
¯
¯E min kΦt k2 − E min kΨt k2 ¯ ≤ Cmnε + Cβ−1 n log(1/ε) + C(βB + β B )mn .
¯ t ∈T
¯
t ∈T
k 3/2
J

J

We used the fact that log #(T Jε ) ≤ n log(3/ε) in the smoothing term.

It remains to identify appropriate values for the parameters. Select ε = (mn)−1 so the discretization
error is negligible. We choose the smoothing parameter so that β3 = k 3/2 /(B 6 m). In summary,
¯
¯
2 2/3
2 1/3
¯
¯
¯E min kΦt k2 − E min kΨt k2 ¯ ≤ C + CB m n + CB m n log(mn) .
¯ t ∈T
¯
t ∈T J
k
k 1/2
J

Since B ≥ 1 and m 2/3 ≤ k ≤ n, the third term dominates. This is the bound stated in (13.3).
13.2. Proposition 13.1: Discretizing the Index Set. The first step in the proof of Proposition 13.1 is to
replace the set T J with a finite subset T Jε without changing the restricted singular values of Φ and Ψ
substantially.
Lemma 13.2 (Proposition 13.1: Discretization). Adopt the notation and hypotheses of Proposition 13.1.
Fix a parameter ε ∈ (0, 1]. We can construct a subset T Jε of T J with cardinality log(#T Jε ) ≤ n log(3/ε) that has
the property
¯
¯
¯
¯
¯
2
2¯
(13.8)
¯E min kΦt k − E minε kΦt k ¯ ≤ 2mnε.
¯
¯ t ∈T J
t ∈T J
Furthermore, the bound (13.8) holds if we replace Φ by Ψ.
Proof. We choose the discretization T Jε to be an ε-covering of T J with minimal cardinality. That is,
T Jε ⊂ T J

and

max minε kt ε − t k ≤ ε.
t ∈T J t ε ∈T J

Since Vol(T J ) ≤ Vol(Bn ), we can use a classic volumetric argument to ensure that the covering satisfies
#T Jε ≤ (3/ε)n . For example, see [Ver12, Lem. 5.2].
When we replace the set T J with the covering T Jε , we incur a discretization error. We establish the error
bound for Φ; the argument for Ψ is identical. Since T Jε ⊂ T J , it is immediate that
E min kΦt k2 ≤ E minε kΦt k2 .
t ∈T J

t ∈T J

We claim that
¡
¢
E minε kΦt k2 ≤ E min kΦt k2 + 2ε E kΦk2 .
t ∈T J

Since Φ has standardized entries,

t ∈T J

(13.9)

E kΦk2 ≤ E kΦk2F = mn,

where k·kF denotes the Frobenius norm. Combine the last three displays to verify (13.8).
It is quite easy to establish the claim (13.9). For all s, t ∈ T J , we have
¡
¢ ¡
¢
kΦsk2 − kΦt k2 = kΦsk + kΦt k · kΦsk − kΦt k
¡
¢
≤ kΦk ksk + kt k · kΦ(s − t )k
≤ 2 kΦk2 ks − t k .
We have used standard norm inequalities and the fact that T J is a subset of the unit ball. Now, let
t ? ∈ arg mint ∈T J kΦt k2 , and let t ε be a point in T Jε for which kt ε − t ? k ≤ ε. Then
¡
¢
min kΦt k2 = kΦt ? k2 = kΦt ε k2 − kΦt ε k2 − kΦt ? k2
t ∈T

≥ minε kΦt k2 − 2 kΦk2 kt ε − t ? k
t ∈T J

≥ minε kΦt k2 − 2ε kΦk2 .
t ∈T J

UNIVERSALITY OF RANDOMIZED DIMENSION REDUCTION

47



Taking expectations, we arrive at (13.9).

13.3. Proposition 13.1: Smoothing the Minimum. The second step in the proof of Proposition 13.1 is to
pass from the restricted minimum singular value over the discrete set T Jε to a smooth function. We rely on
an exponential smoothing technique that is common in the mathematical literature on statistical physics.
Lemma 13.3 (Proposition 13.1: Smoothing the Minimum). Adopt the notation and hypotheses of Proposition 13.1, and let T Jε be the set introduced in Lemma 13.2. Fix a parameter β > 0, and define the soft-min
function F via (13.5) Then
¯
¯
¯
¯ 1
¯
¯
(13.10)
¯E minε kΦt k2 − E F (Φ)¯ ≤ log(#T Jε ).
¯ t ∈T J
¯ β
The bound (13.10) also holds if we replace Φ by Ψ.
Proof. This result follows from trivial bounds on the sum in the definition (13.5) of the soft-min function
F . The summands are nonnegative, so the sum exceeds its maximum term. Thus,
X
2
2
log t ∈T ε e−βkAt k ≥ log maxε e−βkAt k = −β minε kAt k2 .
J

t ∈T J

t ∈T J

Similarly, the sum does not exceed the number of summands times the maximum term, so
³
´
X
2
2
log t ∈T ε e−βkAt k ≤ log (#T Jε ) maxε e−βkAt k = log(#T Jε ) − β minε kAt k2 .
J

t ∈T J

t ∈T J

Combine the last two displays and multiply through by the negative number −1/β to reach
X
2
1
1
minε kAt k2 − log(#T Jε ) ≤ − log t ∈T ε e−βkAt k ≤ minε kAt k2 .
J
t ∈T J
t ∈T J
β
β
Replace A by the random matrix Φ and take the expectation to reach (13.10). Similarly, we can take A = Ψ
to obtain the result for Ψ.

13.4. Proposition 13.1: Exchanging the Entries of the Random Matrix. The last step in the proof of
Proposition 13.1 is the hardest. We must demonstrate that the expectation E F (Φ) of the soft-min function
does not change very much when we replace the submatrix Φ J c with the submatrix Ψ J c .
Lemma 13.4 (Proposition 13.1: Exchanging Entries). Adopt the notation and hypotheses of Proposition 13.1; let T Jε be the set described in Lemma 13.2; and let F be the soft-min function (13.5) with parameter
β > 0. Then
C(βB 4 + β2 B 6 )mn
|E F (Φ) − E F (Ψ)| ≤
.
(13.11)
k 3/2
The random matrix Ψ is defined in (13.2).
Proof. We establish the lemma by replacing the rows of the random matrix Φ by the rows of the random
matrix Ψ one at a time. For each i = 1, 2, . . . , m + 1, let Ξ(i ) be the random matrix whose first i − 1 rows are
drawn from Ψ and whose remaining rows are drawn from Φ. By construction, Ξ(1) = Φ and Ξ(m + 1) = Ψ.
It follows that
Xm ¯ ¡
¢
¡
¢¯
|E F (Φ) − E F (Ψ)| ≤ i =1 ¯E F Ξ(i ) − E F Ξ(i + 1) ¯ .
We will demonstrate that
4
2 6
¯ ¡
¢
¡
¢¯
¯E F Ξ(i ) − E F Ξ(i + 1) ¯ ≤ C(βB + β B )n for i = 1, . . . , m.
(13.12)
k 3/2
Combining the last two displays, we arrive at the bound (13.11).
Fix an index i . By construction, the random matrices Ξ(i ) and Ξ(i + 1) are identical, except in the i th
row. To perform the estimate (13.12), it will be convenient to suppress the dependence of the function F
on the remaining rows. To that end, define the functions
X
2
1
f i : Rn → R via f i (a) := − log t ∈T ε e−β(a·t ) +qi (t )
J
β

48

S. OYMAK AND J. A. TROPP

where
q i : Rn → R via q i (t ) := −β

hX
j <i

(ψ j · t )2 +

X
j >i

i
(ϕ j · t )2 .

We have written ϕ j and ψ j for the j th rows of Φ and Ψ. With these definitions,
¡
¢
¡ ¢
¡
¢
¡ ¢
F Ξ(i ) = f i ϕi and F Ξ(i + 1) = f i ψi .
Therefore, the inequality (13.12) is equivalent with
¯
¡ ¢
¡ ¢¯¯ C(βB 4 + β2 B 6 )n
¯
¯E f i ϕi − E f i ψi ¯ ≤
k 3/2

for i = 1, . . . , m.

(13.13)

Since the matrix Φ is drawn from Model 2.1, the random vector ϕi contains independent, standardized
entries whose magnitudes are bounded by B . Meanwhile, the form (13.2) of the matrix Ψ shows that the
random vector ψi coincides with ϕi on the components indexed by J , while the entries of ψi indexed
by J c are independent standard normal variables. Sublemma 13.5, below, contains the proof of the
inequality (13.13).

13.4.1. Lemma 13.4: Comparison Principle for One Row. To complete the argument in Lemma 13.4, we
need to control how much a certain function changes when we replace some of the entries of its argument
with standard normal variables. The following result contains the required calculation.
Sublemma 13.5 (Lemma 13.4: Comparison for One Row). Adopt the notation and hypotheses of Proposition 13.1, and let T Jε be the set defined in Lemma 13.3. Introduce the function
f : Rn → R given by

f (a) := −

X
2
1
log t ∈T ε e−β(a·t ) +q(t ) ,
J
β

where q : T Jε → R is an arbitrary function. Suppose that ϕ ∈ Rn is a random vector with independent,
standardized entries that are bounded in magnitude by B . Suppose that ψ ∈ Rn is a random vector with
ψJ = ϕJ

and ψ J c = γ J c ,

n

where γ ∈ R is a standard normal vector. Then
4
2 6
¯
¯
¯E f (ϕ) − E f (ψ)¯ ≤ C(βB + β B )n .
k 3/2

(13.14)

The proof of Sublemma 13.5 is based on a modern interpretation [MOO10, Cha06, KM11] of the Lindeberg exchange principle [Lin22, Tro59, Rot73]. It is similar in spirit with examples from the paper [KM11].
We apply the following version of the Lindeberg principle, which is adapted from these works.
Fact 13.6 (Lindeberg Exchange Principle). Let r : R → R be a function with three continuous derivatives.
Let ϕ and ψ be standardized random variables, not necessarily independent, with three finite moments.
Then
·
¸
¯
¯
¯
¯
¯
¯
¯E r (ϕ) − E r (ψ)¯ ≤ 1 E |ϕ|3 max ¯r 000 (α)¯ + |ψ|3 max ¯r 000 (α)¯ .
|α|≤|ϕ|
|α|≤|ψ|
6
The proof of Fact 13.6 involves nothing more than a third-order Taylor expansion of r around the origin.
The first- and second-order terms cancel because the random variables ϕ and ψ have mean zero and
variance one. With this inequality at hand, we may proceed with the proof of the sublemma.
Proof of Sublemma 13.5. Without loss of generality, assume that the index set J = {1, . . . , k}. Indeed, the
entries of the random matrix Φ are independent, standardized, and uniformly bounded so it does not
matter which set J of columns we distinguish. This choice allows more intuitive indexing.
For each fixed index j ∈ {k + 1, . . . , n}, define the interpolating vector
ξ j : R → Rn

where ξ j (α) := (ϕ1 , . . . , ϕ j −1 , α, ψ j +1 , . . . , ψn ).

Introduce the function
¡
¢
r j : R → R where r j (α) := f ξ j (α) .

UNIVERSALITY OF RANDOMIZED DIMENSION REDUCTION

49

Observe that
¯
¯ ¯X
¯
¯
¡
¢
¡
¢¯¯ Xn
¯E f (ϕ) − E f (ψ)¯ = ¯¯ n
E
f
ξ
(ϕ
)
−
E
f
ξ
(ψ
)
¯ ≤ j =k+1 ¯E r j (ϕ j ) − E r j (ψ j )¯ .
j
j
j
j
j =k+1
The first identity holds because the sum telescopes. Fact 13.6 shows that
·
¯
¯
¯
¯¸
¯
¯
¯E r j (ϕ j ) − E r j (ψ j )¯ ≤ 1 E |ϕ j |3 max ¯¯r 000 (α)¯¯ + |ψ j |3 max ¯¯r 000 (α)¯¯ .
|α|≤|ϕ j | j
|α|≤|ψ j | j
6
We claim that, for each index j ∈ {k + 1, . . . , n},
·
¯
¯¸
¯ 000 ¯
3
E |ϕ j | max ¯r j (α)¯ ≤ C(βB 4 + β2 B 6 )k −3/2 ,
|α|≤|ϕ j |
·
¯
¯¸
¯ 000 ¯
3
E |ψ j | max ¯r j (α)¯ ≤ C(βB 4 + β2 B 6 )k −3/2 .

and
(13.15)

|α|≤|ψ j |

Once we establish the bound (13.15), we can combine the last three displays to reach
¯
¯
¯E f (ϕ) − E f (ψ)¯ ≤ C(βB 4 + β2 B 6 )k −3/2 (n − k).
The main result (13.14) follows.
To establish (13.15), fix an index j ∈ {k + 1, . . . , n}. The forthcoming Sublemma 13.7 will demonstrate
that
Ã
!
¯
¯
¯ 0
¯3 ³
¯
¯
¯
¯3 ´
¯ 000 ¯
¯
¯
β Ev ¯ξ j (α) · v ¯ + β2 Ev ¯ξ j (α) · v ¯
(13.16)
¯r j (α)¯ ≤ C maxε ξ (α) · t
t ∈T J

∈ T Jε

In this expression, v
immaterial. Note that

is a random vector that is independent from ξ j ; the precise distribution of v is
¯
¯3
maxε ¯ξ0 (α) · t ¯ = maxε |t j |3 ≤ k −3/2 .
t ∈T J

(13.17)

t ∈T J

Indeed, the derivative ξ0j (α) = e j , where e j is the j th standard basis vector. The last inequality holds
because the conditions T Jε ⊂ T J and j ∈ J c allow us to invoke the assumption (13.1).
We arrive at the following bound on the quantity of interest from (13.15):
·
µ ·
¸
·
¸¶
¯
¯¸
¯
¯
¯
¯3
¯ 000 ¯
3
−3/2
3
2
3
¯
¯
¯
¯
E |ϕ j | max ¯r j (α)¯ ≤ Ck
β E |ϕ j | max ξ j (α) · v + β E |ϕ j | max ξ j (α) · v
. (13.18)
|α|≤|ϕ j |

|α|≤|ϕ j |

|α|≤|ϕ j |

¯
¯
We have merged the bounds (13.16) and (13.17) to control ¯r j (α)¯. Next, we invoked Jensen’s inequality
to draw the expectation over v out of the maximum over α. Last, we combined the expectations to
reach (13.18). It remains to bound the expectations on the right-hand side.
Let us begin with the term in (13.18) that is linear in β. In view of the identity ξ j (α) = αe j + ξ j (0),
·
¸
·
¸
¯
¯
¯
¯¢
¡
E |ϕ j |3 max ¯ξ j (α) · v ¯ ≤ E |ϕ j |3 max |αv j | + ¯ξ j (0) · v ¯
|α|≤|ϕ j |

|α|≤|ϕ j |

¯¢
£
¤ ¡
¢¡ ¯
= E |ϕ j |4 |v j | + E |ϕ j |3 E ¯ξ j (0) · v ¯

(13.19)

≤ B 4 k −1/2 + B 3 .
We used the assumption that ϕ j is independent from ξ j (0) to factor the expectation in the second term in
the second line. The bounds in the third line exploit the fact that |ϕ j | ≤ B and, via the hypothesis (13.1),
the fact that v ∈ T J . We also relied on the estimate
¯X
¯
X
¯
¯
¯
¯
E ¯ξ j (0) · v ¯ = E ¯ i < j ϕi v i + i > j ψi v i ¯ ≤ kv k ≤ 1
Indeed, Jensen’s inequality allows us to replace the expectation with the second moment, which simplifies
to kv k because {ϕ1 , . . . , ϕ j −1 , ψ j +1 , . . . , ψn } is an independent family of standardized random variables.
Since v ∈ T J , the norm kv k does not exceed one.

50

S. OYMAK AND J. A. TROPP

Continuing to the term in (13.18) that is quadratic in β2 , we pursue the same approach to see that
·
¸
·
¸
³
¯
¯
¯3
¯3 ´
3
3 ¯
3
¯
¯
¯
E |ϕ j | max ξ j (α) · v
≤ C E |ϕ j | max |αv j | + ξ j (0) · v
|α|≤|ϕ j |
|α|≤|ϕ j |
(13.20)
¡ 6 −3/2
¢
6
≤C B k
+B .
This bound relies on the Khintchine-type inequality
³ ¯
¯3 ´1/3
E ¯ξ j (0) · v ¯
≤ CB kv k ≤ CB.
For example, see [Ver12, Cor. 5.12]. We remark that this estimate could be improved if we had additional
information about the distribution of the entries of Φ.
Substituting the bounds (13.19) and (13.20) into (13.18), we obtain
·
¯
¯¸
£ ¡
¢
¡
¢¤
¯ 000 ¯
3
E |ϕ j | max ¯r j (α)¯ ≤ Ck −3/2 β B 4 k −1/2 + B 3 + β2 B 6 k −3/2 + B 6
|α|≤|ϕ j |

≤ C(βB 4 + β2 B 6 )k −3/2 .
This establishes the first branch of the claim (13.15). The second branch follows from a similar argument,
where we use explicit values for the moments of a standard normal variable instead of the uniform upper
bound B .

13.4.2. Sublemma 13.5: Derivative Calculations. The final obstacle in the proof of Proposition 13.1 is to
bound the derivatives that are required in Sublemma 13.5. This argument uses some standard methods
from statistical physics, and it is similar with the approach in the paper [KM11].
Sublemma 13.7 (Sublemma 13.5: Derivatives). Adopt the notation and hypotheses of Proposition 13.1 and
Sublemma 13.5. Let ξ : R → Rn be a linear function, so its derivative ξ0 ∈ Rn is a constant vector. Define the
function
X
¡
¢
2
1
r (α) := f ξ(α) = − log t ∈T ε e−β(ξ(α)·t ) +q(t )
J
β
where q : T Jε → R is arbitrary. The third derivative of this function satisfies
Ã
!
¯ 000 ¯
¯
¯ ¡
¢
¯r (α)¯ ≤ 48 max ¯ξ0 · t ¯3 β Ev |ξ(α) · v | + β2 Ev |ξ(α) · v |3 .
t ∈T Jε

In this expression, v ∈ T Jε is a random vector that is independent from ξ(α).
Proof. Introduce a (parameterized) probability measure µα on the set T Jε :
µα (t ) :=

1 −β(ξ(α)·t )2 +q(t )
e
Zα

where Zα :=

X

t ∈T Jε

e−β(ξ(α)·t )

2

+q(t )

.

We treat the normalizing factor Zα as a function of α, and we write its derivatives as Zα0 , Zα00 , Zα000 . It is
convenient to use the statistical mechanics notation for expectation with respect to this measure. For any
function h : T Jε → R,
X
〈h(t )〉 := t ∈T ε h(t )µα (t ).
J

For brevity, we always suppress the dependence of 〈·〉 on the parameter α. We often suppress the dependence of ξ on α as well.
The function r is proportional to the logarithm of the normalizing factor Zα :
1
r (α) = − log Zα .
β
Thus, it is straightforward to express the third derivative of r in terms of the derivatives of Zα :
Ã
µ
¶00
µ
¶0
µ 0 ¶3 !
Zα0 Zα00
Z
1 Zα0
1 Zα00 (Zα0 )2
1 Zα000
000
r (α) = −
=−
−
=−
−3
+2 α
.
2
β Zα
β Zα
β
Z
Z
Z
Zα
Zα
α
α α

UNIVERSALITY OF RANDOMIZED DIMENSION REDUCTION

51

By direct calculation, the derivative Zα0 satisfies
Zα0

1 X
0
−β(ξ(α)·t )2 +q(t )
ε (−2β)(ξ · t )(ξ(α) · t )e
Zα Zα t ∈T J
­
®
= −2β (ξ0 · t )(ξ · t ) .
=

The second derivative is
Zα00

£
¤
1 X
0
2
2 0
2
2 −β(ξ(α)·t )2 +q(t )
e
ε (−2β)(ξ · t ) + (2β) (ξ · t ) (ξ(α) · t )
t
∈T
J
Zα Zα
­
®
­
®
= −2β (ξ0 · t )2 + 4β2 (ξ0 · t )2 (ξ · t )2 .

=

The third derivative is
Zα000
Zα

£
¤
1 X
2 0
3
3 0
3
3 −β(ξ(α)·t )2 +q(t )
e
ε 12β (ξ · t ) (ξ(α) · t ) − 8β (ξ · t ) (ξ(α) · t )
t
∈T
J
Zα
­
®
­
®
= 12β2 (ξ0 · t )3 (ξ · t ) − 8β3 (ξ0 · t )3 (ξ · t )3

=

We ascertain that
£
­
®
­
®­
®¤
r 000 (α) = β − 12 (ξ0 · t )3 (ξ · t ) + 12 (ξ0 · t )2 (ξ0 · t )(ξ · t )
®­
®3 ¤
£ ­
®
­
®
­
+ β2 8 (ξ0 · t )3 (ξ · t )3 − 24 (ξ0 · t )(ξ · t ) (ξ0 · t )2 (ξ · t )2 + 16 (ξ0 · t )(ξ · t ) .

(13.21)

This completes the calculation of the exact form of the third derivative of r .
Next, we simplify the formula (13.21) using basic probability inequalities for the expectation 〈·〉. First,
consider the terms that are linear in β. Observe that
E ³
¯­ 0 3
¯
¯
¯ ´
®¯ D¯
¯ (ξ · t ) (ξ · t ) ¯ ≤ ¯ξ0 · t ¯3 |ξ · t | ≤ max ¯ξ0 · t ¯3 〈|ξ · t |〉 .
ε
t ∈T J

Indeed, Jensen’s inequality allows us to draw the absolute value inside the average, and we can invoke
Hölder’s inequality to pull out the maximum of the first term. Similarly, since 〈1〉 = 1,
¯­ 0 2 ® ­ 0
¯
¯3 ´
®¯ ³
¯ (ξ · t )
(ξ · t )(ξ · t ) ¯ ≤ maxε ¯ξ0 · t ¯ 〈|ξ · t |〉
t ∈T J

Next, consider the terms that are quadratic in β. The simplest is
¯­ 0 3
¯
¯ ´­
®¯ ³
®
¯ (ξ · t ) (ξ · t )3 ¯ ≤ max ¯ξ0 · t ¯3 |ξ · t |3 .
ε
t ∈T J

Using Jensen’s inequality, we find that
¯­
³
¯
¯3 ´
¯
¯3 ´ ­
®3 ¯¯ ³
®
¯ 0
|ξ · t |3 .
¯ (ξ · t )(ξ · t ) ¯ ≤ maxε ¯ξ0 · t ¯ 〈|ξ · t |〉3 ≤ maxε ¯ξ0 · t ¯
t ∈T J

t ∈T J

Last, using Lyapunov’s inequality twice,
¯­ 0
¯
¯ ´
¯
¯ ´­
®­
®¯ ³
­
® ³
®
¯ (ξ · t )(ξ · t ) (ξ0 · t )2 (ξ · t )2 ¯ ≤ max ¯ξ0 · t ¯3 〈|ξ · t |〉 |ξ · t |2 ≤ max ¯ξ0 · t ¯3 |ξ · t |3 .
ε
ε
t ∈T J

t ∈T J

Introduce the last five displays into (13.21) to arrive at the bound
¯
¯ ´¡
¯ 000 ¯ ³
­
®¢
¯r (α)¯ ≤ max ¯ξ0 · t ¯3 24β 〈|ξ · t |〉 + 48β2 |ξ · t |3 .
ε
t ∈T J

(13.22)

Last, we want to replace the averages with respect to µα by averages with respect to a simpler probability
measure that does not depend on ξ(α). This argument relies on a correlation inequality. Define another
probability measure µ∗ on the set T Jε :
µ∗ (t ) :=

1 q(t )
e
Z∗

where Z∗ :=

X

t ∈T Jε

eq(t ) .

52

S. OYMAK AND J. A. TROPP

Write 〈·〉∗ for averages with respect to this new measure. First, consider the average
1 X
−β(ξ·t )2 +q(t )
ε |ξ · t | e
Zα t ∈T J
Z∗ 1 X
−β(ξ·t )2 q(t )
=
e
ε |ξ · t | e
Zα Z∗ t ∈T J
E
2
Z∗ D
|ξ · t | e−β(ξ·t )
.
=
∗
Zα

〈|ξ · t |〉 =

Let X := |ξ · t | be the random variable obtained by pushing forward the measure µ∗ from T Jε to the
nonnegative real line. Since x 7→ x is increasing and x 7→ exp(−βx 2 ) is decreasing, Chebyshev’s association
inequality [BLM13, Thm. 2.14] provides that
D
E
D
E
2
2
Zα
1 X
−β(ξ·t )2 +q(t )
|ξ · t | e−β(ξ·t )
= 〈|ξ · t |〉∗
.
≤ 〈|ξ · t |〉∗ e−β(ξ·t )
= 〈|ξ · t |〉∗
εe
∗
∗
Z∗ t ∈T J
Z∗
In summary,
〈|ξ · t |〉 ≤ 〈|ξ · t |〉∗ .

(13.23)

­
® ­
®
|ξ · t |3 ≤ |ξ · t |3 ∗ .

(13.24)

The same argument shows that

Introduce (13.23) and (13.24) into the bound (13.22) to reach the inequality
³
¯
¯3 ´ ¡
­
® ¢
r 000 (α) ≤ 48 maxε ¯ξ0 · t ¯ β 〈|ξ · t |〉∗ + β2 |ξ · t |3 ∗ .
t ∈T J

The statement of the result follows when we reinterpret the averages with respect to µ∗ as expectations
with respect to a random vector v ∈ T Jε with distribution Z∗−1 e−q(t ) .

14. T HEOREM 9.1: B OUNDING THE R ESTRICTED S INGULAR VALUE BY THE E XCESS W IDTH
In Section 13, we showed that the restricted singular value σmin (Φ; T J ) of the random matrix Φ does not
change very much if we replace Φ with a hybrid matrix Ψ, defined in (13.2), that contains many standard
normal random variables. Our next goal is to relate the restricted singular value σmin (Ψ; T J ) of the hybrid
matrix to the excess width of the set T J .
Proposition 14.1 (Theorem 9.1: Excess Width Bound). Let Φ be an m × n random matrix from Model 2.1
with magnitude bound B , and let Γ be an m ×n random matrix with independent, standard normal entries.
Let J be a subset of {1, . . . , n} with cardinality k, and let T J be a closed subset of Bn . Introduce the m × n
random matrix Ψ := Ψ(J ) from (13.2). Then
p ´2
°
°2 ³
E σ2min (Ψ; T J ) = E min °Φ J t J + Γ J c t J c ° ≥ Em (T J ) − CB 2 k .
(14.1)
t ∈T J

+

Furthermore, if T J is convex and k ≥ m 1/2 ,
p ´2
°
°2 ³
E σ2min (Ψ; T J ) = E min °Φ J t J + Γ J c t J c ° ≤ Em (T J ) + CB 2 k .
t ∈T J

+

(14.2)

To obtain this result, we will invoke the Gaussian Minimax Theorem [Gor85, Gor88] to reduce the
random matrix bounds to simpler bounds involving random vectors. This approach has been used
to study the ordinary singular values of a Gaussian matrix [DS01, Sec. 2.3]. It also plays a role in the
analysis of restricted singular values of Gaussian matrices [Sto13, OTH13, TOH15]. The application here
is complicated significantly by the presence of the non-Gaussian matrix Φ J .

UNIVERSALITY OF RANDOMIZED DIMENSION REDUCTION

53

14.1. Proof of Proposition 14.1. The proof of Proposition 14.1 involves several steps, so it is helpful once
again to summarize the calculations that are required.
First, let us explain the process by which we obtain the lower bound for a general closed subset T J of
the Euclidean unit ball Bm . We will argue that
µ
¶
°
°2
°
° 2
°
°
°
°
E min Φ J t J + Γ J c t J c ≥ E min Φ J t J + Γ J c t J c
(Jensen)
t ∈T J

t ∈T J

+

µ
¶2
°
¡°
¢
°
°
≥ E min Φ J t J + h kt J c k + g J c · t J c − 2
t ∈T J

(Lemma 14.5)

+

µ
¶
p 2
¢
¡p
2
c
c
≥ E min m kt k + g J · t J − CB k
t ∈T J

(Lemma 14.7)

+

µ
¶
p 2
¡p
¢
≥ E min m kt k + g · t − CB 2 k
t ∈T J

³
p ´2
= Em (T J ) − CB 2 k .

(Lemma 14.8)

+

(Definition 4.2)

+

In the first line, we pass from the expected square to the square of the expectation, which reduces the
technical complexity of the rest of the argument. Next, we replace the m × n Gaussian matrix Γ with an
expectation over two independent standard normal vectors h ∈ Rm and g ∈ Rn . Third, we remove the
remaining piece Φ J of the original random matrix to arrive at a formula involving only the random vector
g . Finally, we replace the missing coordinates in the random vector g to obtain a bound in terms of the
excess width Em (T J ). We arrive at the inequality (14.1).
The upper bound follows from a similar calculation. Assuming that T J is convex, we may calculate that
µ
¶2
°
°2
°
°
1/4
°
°
°
°
E min Φ J t J + Γ J c t J c ≤ E min Φ J t J + Γ J c t J c + CB m
(Lemma 14.2)
t ∈T J

t ∈T J

+

µ
¶2
°
¡°
¢
1/4
°
°
≤ E min Φ J t J + h kt J c k + g J c · t J c + CB m
t ∈T J

(Lemma 14.6)

+

¶
µ
p 2
¡p
¢
2
≤ E min m kt k + g J c · t J c + CB k
t ∈T J

(Lemma 14.7)

+

µ
¶
p 2
¡p
¢
2
≤ E min m kt k + g · t + CB k
t ∈T J

³
p ´2
= Em (T J ) + CB 2 k .

(Lemma 14.9)

+

+

(Definition 4.2)

The first step is a type of Poincaré inequality, which requires some specialized concentration results for
the restricted singular value of the hybrid matrix. The second step of this chain involves a convex duality
argument that is not present in the proof of the lower bound (14.1). We have used the assumption that
k ≥ m 1/2 to simplify the error term when we pass from the second line to the third. Altogether, this yields
the bound (14.2).
14.2. Proposition 14.1: Moment Comparison Inequality for the Hybrid RSV. We require a moment
comparison inequality to pass from the expected square of the restricted singular value of the hybrid
matrix to the expectation of the restricted singular value itself.
Lemma 14.2 (Proposition 14.1: Moment Comparison). Adopt the notation and hypotheses of Proposition 14.1. Then
µ
¶2
°
°2
°
°
1/4
°
°
°
°
E min Φ J t J + Γ J c t J c ≤ E min Φ J t J + Γ J c t J c + CB m
.
t ∈T J

t ∈T J

Proof. Define the random variable
°
°
X := min °Φ J t J + Γ J c t J c ° .
t ∈T J

54

S. OYMAK AND J. A. TROPP

We need a bound for E X 2 . We obtain this result by applying a moment comparison inequality for Φ,
conditional on Γ, and then we apply a moment comparison inequality for Γ.
Sublemma 14.3, applied conditionally, with the choice A = Γ, gives
h¡
£ £
¤¤
¢2 i
E X 2 = E E X 2 | Γ ≤ E E[X | Γ] + CB m 1/4 .
The function Γ 7→ E[X | Γ] + CB m 1/4 is 1-Lipschitz, so the Gaussian variance inequality, Fact A.1, implies
that
h¡
¢2 i ¡
¢2
E E[X | Γ] + CB m 1/4
≤ E X + CB m 1/4 + 1.



Combine the last two displays, and adjust the constant to complete the proof.

The proof of Lemma 14.2 requires a separate moment comparison result for a random variable that
depends only on the original matrix Φ J .
Sublemma 14.3 (Lemma 14.2: Moment Comparison for Original Matrix). Adopt the notation and hypotheses of Lemma 14.2. For a fixed m × n matrix A,
µ
¶2
°
°2
°
°
1/4
°
°
°
°
c
c
c
c
E min Φ J t J + A J t J
≤ E min Φ J t J + A J t J + CB m
.
(14.3)
t ∈T J

t ∈T J

Proof. Define the random variable
°
°
X := min °Φ J t J + A J c t J c ° .
t ∈T J

First, observe that
¡
¢
¡
¢
¡
¢
(E X 2 )1/2 − E X = (E X 2 )1/2 − E X + = E X − (E X 2 )1/2 − ≤ E X − (E X 2 )1/2 − .

(14.4)

The last inequality is Jensen’s. We can use concentration to bound this quantity. Mutatis mutandis, repeat
the proof of equation (11.1) from Proposition 11.1 to see that, for all ζ ≥ 0,
©
ª
2
P X 2 ≤ E X 2 − CB 2 ζ ≤ e−ζ /m .
Invoke the subadditivity of the square root and change variables:
©
ª
4
P X ≤ (E X 2 )1/2 − CB ζ ≤ e−ζ /m .
Jensen’s inequality and integration by parts deliver
Z ∞
Z
©
ª
¡
¢
2 1/2
2 1/2
E X − (E X )
P X − (E X ) ≤ −ζ dζ ≤
−=
0

∞
0

e−ζ

(14.5)

4

/(CB 4 m)

dζ ≤ CB m 1/4 .

The third inequality follows from (14.5). Introduce the last display into (14.4) to reach
(E X 2 )1/2 − E X ≤ CB m 1/4 .
Rearrange this relation to complete to proof of (14.3).



14.3. Proposition 14.1: The Role of the Gaussian Minimax Theorem. To prove Proposition 14.1, we
must replace the Gaussian matrix in the quantity of interest with a pair of Gaussian vectors. The key to
this argument is the following technical result.
Lemma 14.4 (Proposition 14.1: Application of Gaussian Minimax Theorem). Adopt the notation and
hypotheses of Proposition 14.1. Let A be a fixed m × n matrix, and let g ∈ Rn and h ∈ Rm be independent
standard normal random vectors. Then, for all ζ ∈ R,
½
¾
½
¾
°
°
°
¡°
¢
P min ° A J t J + Γ J c t J c ° ≤ ζ ≤ 2 P min ° A J t J + h kt J c k° + g J c · t J c ≤ ζ .
(14.6)
t ∈T J

t ∈T J

Furthermore, if T J is convex and ζ ≥ 0,
½
¾
½
¾
°
°
°
¡°
¢
°
°
°
°
P min A J t J + Γ J c t J c ≥ ζ ≤ 2 P min A J t J + h kt J c k + g J c · t J c ≥ ζ .
t ∈T J

If ζ ≤ 0, the left-hand side is trivially equal to one.

t ∈T J

(14.7)

UNIVERSALITY OF RANDOMIZED DIMENSION REDUCTION

55

This result depends on the Gaussian Minimax Theorem [Gor85]; see Fact A.3 for a statement. Lemma 14.4
is similar with early results of Gordon [Gor88, Cor. 1.2]. The detailed argument here is adapted from [TOH15,
Thm. 2.1]; see also Stojnic [Sto13].
Proof. The basic idea is to express the quantity of interest as the value of a saddle-point problem:
°
°
¡
¢
c tJc .
min ° A J t J + Γ J c t J c ° = min max
u
·
A
t
+
Γ
J
J
J
m
t ∈T J

t ∈T J u∈B

Then we apply the Gaussian Minimax Theorem to obtain probabilistic lower bounds. When T J is convex,
we can also invoke convex duality to interchange the minimum and maximum, which leads to complementary bounds. To proceed with this approach, however, it is convenient to work with a slightly different
minimax problem.
Define the deterministic function
λ(t , u) = u · (A J t J ) for t ∈ T J and u ∈ Bm .
Let γ be a standard normal random variable, independent from everything else. Introduce two centered
Gaussian processes:
X (t , u) := u · (Γ J c t J c ) + kuk kt J c k γ and Y (t , u) := (u · h) kt J c k + kuk (g · t J c )
indexed by t ∈ T J and u ∈ Bm . Let us verify that these processes satisfy the conditions required by the
Gaussian Minimax Theorem, Fact A.3. First, for all parameters t ∈ T J and u ∈ Bm ,
E X (t , u)2 = 2 kuk2 kt J c k2 = E Y (t , u)2 .

(14.8)

Second, for all parameters t , t 0 ∈ T J and u, u 0 ∈ Bm ,
¢
£
¤
£
¤ ¡
¢¡
E X (t , u)X (t 0 , u 0 ) − E Y (t , u)Y (t 0 , u 0 ) = kuk ku 0 k − u · u 0 kt J c k kt J0 c k − t J c · t J0 c .
By the Cauchy–Schwarz inequality,
£
¤
£
¤
E X (t , u)X (t , u 0 ) = E Y (t , u)Y (t , u 0 ) ;
£
¤
£
¤
E X (t , u)X (t 0 , u) = E Y (t , u)Y (t 0 , u) ;
£
¤
£
¤
E X (t , u)X (t 0 , u 0 ) ≥ E Y (t , u)Y (t 0 , u 0 ) .

(14.9)
(14.10)
(14.11)

The formulas (14.8), (14.9), and (14.11) verify the conditions of the Gaussian Minimax Theorem. Fact A.3
delivers the bound
¾
½
¾
½
¡
¢
¡
¢
P min max
λ(t , u) + X (t , u) > ζ ≥ P min max
λ(t , u) + Y (t , u) > ζ .
(14.12)
m
m
t ∈T J u∈B

t ∈T J u∈B

This estimate does involve a small technicality. We can only apply the Gaussian Minimax Theorem to a
finite subset of T J × Bm , so we must make an approximation argument to pass to the entire set. We omit
the details.
Now, let us determine the values of the saddle-point problems in (14.12). First,
¡
¢
¡
¢
min max
λ(t , u) + X (t , u) = min max
u · (A J t J + Γ J c t J c ) + kuk kt J c k γ
m
m
t ∈T J u∈B
t ∈T J u∈B
°
¡°
¢
(14.13)
= min ° A J t J + Γ J c t J c ° + kt J c k γ + .
t ∈T J

Similarly,
°
¡
¢
¡°
¢
min max
λ(t , u) + Y (t , u) ≥ min ° A J t J + h kt J c k° + g J c · t J c .
m
t ∈T J u∈B

t ∈T J

56

S. OYMAK AND J. A. TROPP

Next, we remove the term involving γ from the right-hand side of (14.13). To do so, we condition on
γ > 0 and γ ≤ 0 and calculate that
½
¾
½
¾
°
¡
¢
¡°
¢
° A J t J + Γ J c t J c ° + kt J c k γ > ζ
P min max
λ(t
,
u)
+
X
(t
,
u)
>
ζ
=
P
min
max
+
t ∈T J u∈Bm
t ∈T J u∈Bm
½
¾
¯
°
¡°
¢
1 1
¯
°
°
c
c
c
kt
k
≤ + P min A J t J + Γ J t J + J γ + > ζ ¯ γ ≤ 0
t ∈T J
2 2
½
¾
°¢
¡°
1 1
°
°
≤ + P min A J t J + Γ J c t J c + > ζ
t ∈T J
2 2
½
¾
°
°
1 1
°
°
= + P min A J t J + Γ J c t J c > ζ .
t ∈T J
2 2
On the other hand,
½
¾
½
¾
°
¡
¢
¡°
¢
°
°
P min max
λ(t , u) + Y (t , u) > ζ ≥ P min A J t J + h kt J c k + g J c · t J c > ζ .
m
t ∈T J u∈B

t ∈T J

Introduce the last two displays into (14.12) to reach
½
¾
½
¾
°
°
°
¡°
¢
1 1
°
°
°
°
+ P min A J t J + Γ J c t J c > ζ ≥ P min A J t J + h kt J c k + g J c · t J c > ζ .
t ∈T J
t ∈T J
2 2
Take the complements of both probabilities and rearrange to conclude that (14.6) is correct.
The second result (14.7) requires an additional duality argument. If we replace the function λ and the
random processes X and Y with their negations, all of the variance calculations above remain valid. In
particular, the relations (14.8), (14.10), and (14.11) permit us to apply Fact A.3 with the roles of T J and Bm
reversed. This step yields
½
¾
½
¾
¡
¢
¡
¢
P minm max − λ(t , u) − X (t , u) > −ζ ≥ P minm max − λ(t , u) − Y (t , u) > −ζ .
u∈B

t ∈T J

u∈B

t ∈T J

Let us examine the saddle-point problems. Since −λ − X is bilinear and the sets Bm and T J are compact
and convex, the Sion Minimax Theorem [Sio58] allows us to interchange the minimum and maximum.
Thus
¡
¢
¡
¢
minm max − λ(t , u) − X (t , u) = max minm − λ(t , u) − X (t , u)
t ∈T J u∈B
u∈B t ∈T J
¡
¢
= − min max
λ(t , u) + X (t , u)
m
t ∈T J u∈B
°
¡°
¢
= − min ° A J t J + Γ J c t J c ° + kt J c k γ + .
t ∈T J

Similarly,
°
¡
¢
¡°
¢
minm max − λ(t , u) − Y (t , u) = − min ° A J t J + h kt J c k° + g J c · t J c + .

u∈B

t ∈T J

t ∈T J

Combining the last three displays, we reach
½
¾
½
¾
°
°
¡°
¢
¡°
¢
°
°
°
°
P min A J t J + Γ J c t J c + kt J c k γ + < ζ ≥ P min A J t J + h kt J c k + g J c · t J c + < ζ .
t ∈T J

t ∈T J

Proceeding as before, conditioning on the sign of γ, we may remove the dependence on γ from the
left-hand side to obtain
½
¾
½
¾
°
°
°
¡°
¢
°
°
°
°
c
c
c
c
c
P min A J t J + Γ J t J ≥ ζ ≥ 2P min A J t J + h kt J k + g J · t J + ≥ ζ .
t ∈T J

t ∈T J

Clearly, this inequality is useful only for ζ ≥ 0 in which case the right hand side is equal to
½
¾
°
°
°
°
c
c
c
2P min A J t J + h kt J k + g J · t J ≥ ζ .
t ∈T J

We confirm that (14.7) is true.



UNIVERSALITY OF RANDOMIZED DIMENSION REDUCTION

57

14.4. Proposition 14.1: Reducing the Gaussian Matrix to Some Gaussian Vectors. Our next goal is to
convert the probability bounds from Lemma 14.4 into expectation bounds. Lemma 14.5 gives a lower
bound that is valid for every subset T J of the unit ball, and Lemma 14.6 gives an upper bound that is valid
when T J is also convex.
Lemma 14.5 (Proposition 14.1: Reducing the Gaussian Matrix—Lower Bound). Adopt the notation and
hypotheses of Proposition 14.1. Let A be a fixed m × n matrix, and let g ∈ Rn and h ∈ Rm be independent
standard normal vectors. Then
°
°
°
¡°
¢
E min ° A J t J + Γ J c t J c ° ≥ E min ° A J t J + h kt J c k° + g J c · t J c − 2.
(14.14)
t ∈T J

t ∈T J

In particular,
°
°
°
¡°
¢
E min °Φ J t J + Γ J c t J c ° ≥ E min °Φ J t J + h kt J c k° + g J c · t J c − 2.
t ∈T J

t ∈T J

Proof. We make the abbreviations
°
°
X := min ° A J t J + Γ J c t J c °
t ∈T J

°
¡°
¢
and Y := min ° A J t J + h kt J c k° + g J c · t J c .
t ∈T J

First, note that
E Y − E X ≤ (E Y − E X )+ = (E X − E Y )− ≤ E(X − E Y )− .

The last inequality is Jensen’s. To bound the right-hand side, we use integration by parts and formula (14.6)
from Lemma 14.4:
Z ∞
Z ∞
E(X − E Y )− =
P {X − E Y ≤ −ζ} dζ ≤
2 P {Y − E Y ≤ −ζ} dζ = 2 E(Y − E Y )− .
0

0

Finally, we make the estimates
E[(Y − E Y )− ] ≤ Var[Y ]1/2 ≤ 1.

The last inequality follows from the Gaussian variance inequality, Fact A.1. Indeed, the function (g , h) 7→
Y (g , h) is 1-Lipschitz because the set T J is contained in the unit ball. In summary,
E Y − E X ≤ E(X − E Y )− ≤ 2 E(Y − E Y )− ≤ 2.



We arrive the advertised bound (14.14).

Lemma 14.6 (Proposition 14.1: Reducing the Gaussian Matrix—Upper Bound). Adopt the notation and
hypotheses of Proposition 14.1. Let A be a fixed m × n matrix, and let g ∈ Rn and h ∈ Rm be independent
standard normal vectors. Then
°
°
°
¡°
¢
E min ° A J t J + Γ J c t J c ° ≤ E min ° A J t J + h kt J c k° + g J c · t J c + 2.
t ∈T J

t ∈T J

In particular,
°
°
°
¡°
¢
E min °Φ J t J + Γ J c t J c ° ≤ E min °Φ J t J + h kt J c k° + g J c · t J c + 2.
t ∈T J

t ∈T J

Proof. We follow the same pattern as in Lemma 14.5. Using the same notation, we calculate that
E X − E Y ≤ (E X − E Y )+ ≤ E(X − E Y )+ ≤ 2 E(Y − E Y )+ ≤ 2.

In this case, we invoke (14.7) from Lemma 14.4 to obtain the penultimate inequality.



58

S. OYMAK AND J. A. TROPP

14.5. Proposition 14.1: Removing the Remaining Part of the Original Random Matrix. The next step
in the proof of Proposition 14.1 is to remove the remaining section of the random matrix Φ from the
bounds in Lemmas 14.5 and 14.6.
Lemma 14.7 (Proposition 14.1: Removing the Original Matrix). Adopt the notation and hypotheses of
Proposition 14.1. Let X be an m × n random matrix with independent, standardized entries that satisfy
Assumption B.1. Then
¯
¯
p
¯
°
¢¯
¡°
¢
¡p
¯E min ° X J t J + h kt J c k° + g J c · t J c − E min m kt k + g J c · t J c ¯ ≤ CB 2 k.
¯
¯
t ∈T J

t ∈T J

In particular, this conclusion is valid when X = Φ.
£
¤
Proof. Abbreviate Ψ := X J h . Observe that
¸
·
tJ
X J t J + h kt J c k = Ψ
kt J c k

and

°·
¸°
° tJ °
°
°
° kt J c k ° = kt k .

Therefore, we have the deterministic bounds
°
°
σmin (Ψ) kt k ≤ ° X J t J + h kt J c k° ≤ σmax (Ψ) kt k .

(14.15)

The m × (k + 1) random matrix Ψ has independent, standardized entries that satisfy (B.1). For all ζ ≥ 0,
Fact B.1 shows that its extreme singular values satisfy the probability bounds
n
o
p
p
2
4
P σmax (Ψ) ≥ m + C0 B 2 k + ζ ≤ e−c0 ζ /B , and
o
n
(14.16)
p
p
2
4
P σmin (Ψ) ≤ m − C0 B 2 k − ζ ≤ e−c0 ζ /B .
p
These inequalities allow us to treat the singular values of Ψ as if they were equal to m.
We may now perform the following estimates:
°
¡°
¢
¡
¢
E min ° X J t J + h kt J c k° + g J c · t J c ≤ E min σmax (Ψ) kt k + g J c · t J c
t ∈T J
t ∈T J
¸
·
¢ ¡
¡p
p ¢
≤ E min m kt k + g J c · t J c + σmax (Ψ) − m + max kt k
t ∈T J
t ∈T J
¡p
¢
¡
p ¢
≤ E min m kt k + g J c · t J c + E σmax (Ψ) − m + .
t ∈T J

p
The first inequality is (14.15). Then we add and subtract
m from the maximum singular value. Last, we
p
2
recall that T J is a subset of the unit ball. Set α := C0 B k, and calculate that
Z ∞
¡
©
ª
p ¢
p
E σmax (Ψ) − m + =
P σmax (Ψ) − m ≥ ζ dζ
Z0 α
Z ∞
©
ª
p
(14.17)
≤
dζ +
P σmax (Ψ) − m ≥ α + ζ dζ
0
Z ∞ 0
2
4
≤ α+
e−c0 ζ /B dζ = α + CB 2 .
0

We split the integral at α, and we change variables in the second integral. For the first integral, we use the
trivial bound of one on the probability. Then we invoke the probability inequality (14.16).
Combining the last two displays and collecting constants, we arrive at
p
°
¡°
¢
¡p
¢
E min ° X J t J + h kt J c k° + g J c · t J c ≤ E min m kt k + g J c · t J c + CB 2 k.
t ∈T J

t ∈T J

An entirely similar argument delivers a matching lower bound. Together, these estimates complete the
proof.


UNIVERSALITY OF RANDOMIZED DIMENSION REDUCTION

59

14.6. Proposition 14.1: Replacing the Coordinates Missing from the Excess Width. The last step in the
proof of Proposition 14.1 is to examine the excess-width-like functional from Lemma 14.7 that involves the
term g J c · t J c . We must show that this term does not change very much if we reintroduce the coordinates
listed in J . Lemma 14.8 gives the easy proof of the lower bound. Lemma 14.9 contains the upper bound.
Lemma 14.8 (Proposition 14.1: Missing Coordinates—Lower Bound). Adopt the notation and hypotheses
of Proposition 14.1. Then
¢
¢
¡p
¡p
E min m kt k + g J c · t J c ≥ E min m kt k + g · t .
t ∈T J

t ∈T J

Proof. This result is an immediate consequence of Jensen’s inequality:
¡p
¢
¢
¡p
E min m kt k + g J c · t J c = E min m kt k + g J c · t J c + Eg J (g J · t J )
t ∈T J
t ∈T J
¡p
¢
≥ E min m kt k + g J c · t J c + g J · t J
t ∈T J
¢
¡p
= E min m kt k + g · t
t ∈T J

We rely on the fact that g J and g J c are independent standard normal vectors.



Lemma 14.9 (Proposition 14.1: Missing Coordinates—Upper Bound). Adopt the notation and hypotheses
of Proposition 14.1. Then
¡p
¢ p
¢
¡p
E min m kt k + g J c · t J c ≤ E min m kt k + g · t + k.
t ∈T J

t ∈T J

Proof. This calculation is also easy:
¡p
¢
¢
¡p
E min m kt k + g J c · t J c = E min m kt k + g · t − g J · t J
t ∈T J

t ∈T J

≤ E min

¡p
¢
m kt k + g · t + E kg J k

≤ E min

¡p
¢ p
m kt k + g · t + k.

t ∈T J

t ∈T J

In the last step, we have used the fact that #J = k.



15. P ROOF OF C OROLLARY 10.1 FROM T HEOREM 9.1 BY T RUNCATION
In this section, we show how to establish Corollary 10.1 as a consequence of Theorem 9.1. The proof
depends on a truncation argument.
15.1. Proof of Corollary 10.1. Fix parameters p > 4 and ν ≥ 1. Assume that Φ is an m × n matrix that
follows Model 2.4 with parameters p and ν. Let T be a compact subset of the unit ball Bn . We will prove
the lower bound for the minimum singular value of Φ restricted to T . When T is convex, an entirely
similar approach yields the corresponding upper bound.
Fix a truncation parameter R that satisfies R p/2−1 ≥ 2νp/2 . Decompose the random matrix Φ as
Φ = Φtrunc + Φtail
by applying the truncation described below in Lemma 15.1 separately to each entry of Φ. This procedure
ensures that Φtrunc contains independent, symmetric, standardized entries, each bounded by 2R. In other
words, Φtrunc follows Model 2.1 with B = 2R. The tail Φtail contains independent, centered entries, each
with variance bounded by Cνp R 2−p and whose pth moment is bounded by (2ν)p .
We can control the restricted singular values of Φ using the triangle inequality:
σmin (Φ; T ) = min kΦt k ≥ min kΦtrunc t k − kΦtail k = σmin (Φtrunc ; T ) − kΦtail k .
t ∈T

t ∈T

(15.1)

We bound the restricted singular value of the bounded matrix Φtrunc using Theorem 9.1. To bound kΦtail k,
we apply a simple norm estimate, Fact B.2, based on the matrix Rosenthal inequality [Tro15c, Thm. I].

60

S. OYMAK AND J. A. TROPP

Since Φtrunc follows Model 2.1 with B = 2R, Theorem 9.1(1) and (2) give the probability bound
o
n
¡
¢2
2
P σ2min (Φtrunc ; T ) ≤ Em (T ) + − CR 2 (m + n)0.92 − CR 2 ζ ≤ e−ζ /(m+n) .
Select ζ = (m + n)0.92 to make the tail probability negligible:
n
o
¡
¢2
0.84
P σ2min (Φtrunc ; T ) ≤ Em (T ) + − CR 2 (m + n)0.92 ≤ e−(m+n) .
Taking square roots inside the event, we reach
©
¡
¢
ª
0.84
P σmin (Φtrunc ; T ) ≤ Em (T ) + − CR(m + n)0.46 ≤ e−(m+n) .

(15.2)

This step depends on the subadditivity of the square root.
Meanwhile, the entries of Φtail are centered, have variances at most Cνp R 2−p , and have pth moments
bounded by (2ν)p . Therefore, we can apply the norm bound for heavy-tailed random matrices, Fact B.2,
to see that
½
¾
q
¡
¢
2/p
p
2−p
P kΦtail k ≥ C ν R
(m + n) log(m + n) + Cν(m + n) log(m + n) ζ ≤ ζ−p .
Define the positive quantity ε via the relation 4(1 + ε) := p. Select ζ = (m + n)ε/p to obtain
q
n
o
P kΦtail k ≥ Cνp/2 R 1−p/2 (m + n) log(m + n) + Cν(m + n)(2+ε)/p log(m + n) ≤ (m + n)−ε .

(15.3)

p
The key point here is that we can arrange for kΦtail k to have order o( m + n) with high probability.
Combine (15.1), (15.2), and (15.3) to reach
n
¡
¢
P σmin (Φ; T ) ≤ Em (T ) + − CR(m + n)0.46
q
o
− Cνp/2 R 1−p/2 (m + n) log(m + n) − Cν(m + n)(2+ε)/p log(m + n)
0.84

≤ e−(m+n)

+ (m + n)−ε .

Set the truncation parameter R = ν(m + n)0.02/(1+ε) to equate the exponents on m + n in the two terms
that depend on R. Then simplify using p = 4(1 + ε) to obtain
©
¡
¢
¡
¢
ª
P σmin (Ψ; T ) ≤ Em (T ) + − Cν (m + n)0.5−0.02(1+2ε)/(1+ε) + (m + n)0.5−(ε/4)/(1+ε) log(m + n)

≤ e−(m+n)

0.84

+ (m + n)−ε .

Note that both powers in the event are bounded away from 1/2, so we can absorb the logarithm by
increasing the power slightly. Furthermore, we can introduce a function κ(p) that is strictly positive for
p > 4 to reach the inequality
©
¡
¢
ª
0.84
P σmin (Ψ; T ) ≤ Em (T ) + − Cp ν(m + n)0.5−κ(p) ≤ e−(m+n) + (m + n)1−p/4 .
The constant Cp depends only on the parameter p. The exponential vanishes faster than any polynomial,
so we can combine the terms on the right-hand side to complete the proof of (10.1).
For the upper bound, we use Theorem 9.1(3) to control the expectation of the restricted singular value.
In this case, the error term in the expectation bound becomes R 4 (m + n)0.94 . This change presents no new
difficulties, and we arrive at the result (10.2) by a slight modification of the argument.
15.2. Corollary 10.1: Truncation of Individual Random Variables. In this section, we describe a truncation procedure for scalar random variables. The arguments here are entirely standard, but we include
details for completeness.

UNIVERSALITY OF RANDOMIZED DIMENSION REDUCTION

61

Lemma 15.1 (Corollary 10.1: Truncation). Let ϕ be a random variable that satisfies the properties listed in
Model 2.4. Let R be a parameter that satisfies R p/2−1 ≥ 2νp/2 . Then we have the decomposition
ϕ = ϕtrunc + ϕtail

(15.4)

where
E ϕtrunc = 0,

E ϕ2trunc = 1,

and
E ϕtail = 0,

E ϕ2tail ≤

6νp
,
R p−2

and
and

|ϕtrunc | ≤ 2R
E |ϕtail |p ≤ (2ν)p .

Proof. Define the random variable
£
¤
ϕ1{|ϕ| ≤ R}
where α2 := E ϕ2 1{|ϕ| ≤ R} .
α
Since ϕ is standardized and symmetric, ϕtrunc is also standardized and symmetric. To ensure that the
decomposition (15.4) holds, we must set

ϕtrunc :=

1−α
ϕ1{|ϕ| ≤ R}.
(15.5)
α
The random variable ϕtail is also centered because of the symmetry of ϕ.
To establish the other properties of ϕtrunc and ϕtail , we need to calculate some expectations. First, using
integration by parts and Markov’s inequality,
Z R
Z ∞
£ 2
¤
E ϕ 1{|ϕ| > R} =
2ζP {|ϕ| > R} dζ +
2ζP {|ϕ| > ζ} dζ
0
R
(15.6)
Z R
Z
∞
E |ϕ|p
E |ϕ|p
2νp
2ζ p dζ ≤ p−2 .
≤
2ζ p dζ +
R
ζ
R
0
R
ϕtail := ϕ1{|ϕ| > R} −

In the last step, we used the assumption that p ≥ 4. A similar calculation shows that
Z R
£
¤
α2 = E ϕ2 1{|ϕ| ≤ R} =
2ζP {|ϕ| > ζ} dζ
0
Z ∞
Z ∞
2ζP {|ϕ| > ζ} dζ
2ζP {|ϕ| > ζ} dζ −
=
R

0

£ ¤
≥ E ϕ2 −

2νp
νp
≥
1
−
.
(p − 2)R p−2
R p−2

The last relation holds because ϕ is standardized. It follows that
α ≥ 1−

νp/2
R p/2−1

1
≥ .
2

(15.7)

The last estimate holds because p ≥ 4 and of the assumption R p/2−1 ≥ 2νp/2 .
We are now prepared to verify the uniform bound on ϕtrunc :
¯
¯
¯ ϕ1{|ϕ| ≤ R} ¯ R
¯
¯ ≤ ≤ 2R.
|ϕtrunc | = ¯
¯ α
α
The last inequality follows from (15.7).
Next, we need to bound the variance of ϕtail . We have
µ
¶
µ p/2 p/2−1 ¶2
£
¤
£
¤
¤ 2νp
£ ¤ 6νp
1−α 2 £ 2
ν /R
E ϕ2tail = E ϕ2 1{|ϕ| > R} +
E ψ2 ≤ p−2 .
E ϕ 1{|ϕ| ≤ R} ≤ p−2 +
α
R
1/2
R
The first identity holds because the two indicators are orthogonal random variables. The second relation
uses the expectation calculation (15.6) and the estimate (15.7); we have dropped the indicator in the
second expectation. The last estimate holds because ϕ is standardized.

62

S. OYMAK AND J. A. TROPP

Last, we need to check the moment inequality for ϕtail . This estimate follows by applying the triangle
inequality to the definition (15.5):
¡
¢1/p ¡
¢1/p 1 − α ¡
¢1/p 1 ¡
¢1/p
E |ϕtail |p
≤ E |ϕ|p
+
E |ϕ|p
=
E |ϕ|p
≤ 2ν.
α
α
We have dropped the indicators after invoking the triangle inequality. Finally, we introduced the estimate (15.7).


UNIVERSALITY OF RANDOMIZED DIMENSION REDUCTION

63

Part IV. Universality of the Embedding Dimension: Proof of Theorem I(b)
This part of the paper develops a condition under which the random projection of a set fails with
high probability. This argument establishes the second part of the universality law for the embedding
dimension, Theorem I(b).
Section 16 contains the main technical result, a condition under which a bounded random matrix
maps a point in a set to the origin. Section 17 extends this argument to the heavy-tailed random matrix
model, Model 2.4. In Section 17.2, we use the latter result to derive Theorem I(b). The remaining parts of
the section lay out the supporting argument.
16. W HEN E MBEDDING FAILS FOR A B OUNDED R ANDOM M ATRIX
In this section, we introduce a functional whose value determines whether a linear transformation
maps a point in a set to the origin. Then we present the main technical result, which gives an estimate for
this functional evaluated on a random linear map from Model 2.1. The rest of the section outlines the
main steps in the proof of the result.
16.1. The RAP Functional: Dual Condition for Failure. To study when a linear map maps a point a set
to the origin, we use an approach based on polarity. Let us make the following definition.
Definition 16.1 (Range Avoids Polar (RAP)). Let K ⊂ Rm be a closed, convex cone. Let A be an m × n
matrix. Define the quantity
τmin (A; K ) := min min◦ ks − At k .
kt k=1 s∈K

Note that the range of the inner minimum involves the polar K ◦ of the cone. We refer to τmin as the RAP
functional.
To see why the RAP functional is important, consider a closed, spherically convex subset Ω of Sm−1 for
which cone(Ω) is not a subspace. The second conclusion of Proposition 3.8 states that
τmin (A; cone(Ω)) > 0 implies 0 ∈ A(Ω).
The third conclusion of Proposition 3.8 gives a similar result in the case of a subspace. Therefore, we can
obtain a sufficient condition that A maps a point in Ω to zero by providing a lower bound for the RAP
functional.
16.2. Theorem 16.2: Main Result for the Bounded Random Matrix Model. The main technical result in
this part of the paper is a theorem on the behavior of the RAP functional of a bounded random matrix.
Theorem 16.2 (RAP: Bounded Random Matrix Model). Place the following assumptions:
• Let m and n be natural numbers with m + n ≤ min{m, n}9/8 .
• Let K be a closed, convex cone in Rm , and define Ω := K ∩ Sm−1 .
• Draw an m × n random matrix Φ from Model 2.1 with bound B .
Then the squared RAP functional τ2min (Φ; K ) has the following properties.

p
(1) The squared RAP functional deviates below its mean on a scale of B 2 m + n:
©
ª
2
P τ2min (Φ; K ) ≤ E τ2min (Φ; K ) − CB 2 ζ ≤ e−ζ /m

(2) The expected square of the RAP functional is bounded below:
¡
¢2
En (Ω) −
2
E τmin (Φ; K ) ≥
− CB 3 (m + n)0.95 .
CB 2 log(m + n)
This result does use the symmetry assumption in Model 2.1.
The proof of Theorem 16.2 is long, even though we can borrow a lot from the proof of Theorem 9.1. This
section contains an overview of the calculations that are required with forward references to the detailed
arguments.

64

S. OYMAK AND J. A. TROPP

16.3. Proof of Theorem 16.2: Lower Tail Bound. Theorem 16.2(1) states that the quantity τ2min (Φ; K )
does not deviate substantially below its mean. The proof is similar to the proof of the bound (11.1) in
Proposition 11.1, which shows that the squared restricted singular value σ2min (Φ; K ) does not deviate
substantially below its mean. We omit the repetitive details.
16.4. Proof of Theorem 16.2: Truncation and Dissection. Let us proceed with the proof of Theorem 16.2(2).
Define the sets
S := K ◦ ∩ R Bm and T := Sn−1
p
where the radius R := Crad B 2 m + n for some universal constant Crad . Next, we construct a family of
closed, convex subsets of S and T . For each I ⊂ {1, . . . , m} and each J ⊂ {1, . . . , n}, define
©
ª
S I := s ∈ S : |s i | ≤ R(#I )−1/2 for all i ∈ I c ;
©
ª
T J := t ∈ T : |t j | ≤ (#J )−1/2 for all j ∈ J c .
Fix the cardinality parameter k ∈ {1, . . . , min{m, n}}. As in the proof of Theorem 9.1, we have the decompositions
[
[
S = #I =k S I and T = #J =k T J .
Furthermore,
¶
e(m + n) k
#{S I : #I = k} × #{T J : #J = k} ≤
.
(16.1)
k
We maintain the heuristic that the cardinality k is much smaller than either ambient dimension m or n.
µ

16.5. Proof of Theorem 16.2: Lower Bound for RAP Functional. To bound the quantity τmin (Φ; K ), we
must combine estimates from several technical results. We give an outline of the calculation here, with
the details postponed to a series of propositions.
First, we must account for the error we incur when we truncate the cone K ◦ to the wedge S. Proposition 18.1 demonstrates that
E τ2min (Φ; K ) = E min min◦ ks − Φt k2 ≥ E min min ks − Φt k2 − CB 4 .
kt k=1 s∈K

t ∈T s∈S

(16.2)

This inequality is based on an estimate for the norm of the point s ∈ K ◦ where the inner minimum is
achieved, as well as a probability bound for the norm of the random matrix Φ.
Next, we pass from the minimum over the full sets S and T to minima over their subsets S I and T J :
q
E min min ks − Φt k2 ≥ min E min min ks − Φt k2 − CB 2 km log((m + n)/k).
(16.3)
t ∈T s∈S

#I =#J =k

t ∈T J s∈S I

The proof of this inequality hews to the argument in Proposition 12.2. We just need to invoke the concentration inequality from Theorem 16.2(1) in lieu of the concentration inequality from Proposition 11.1, and
we take into account the bound (16.1) on the number of subsets in the decomposition. Further details are
omitted.
We are now prepared to perform the exchange argument to pass from the matrix Φ to a matrix Ψ that
contains many standard normal entries. Fix subsets I ⊂ {1, . . . , m} and J ⊂ {1, . . . , n}, each with cardinality
k. Introduce the random matrix
·
¸
ΦI J ΦI J c
Ψ := Ψ(I , J ) :=
ΦI c J ΓI c J c
where Γ is an m × n standard normal matrix. Proposition 19.1 gives the bound
E min min ks − Φt k2 ≥ E min min ks − Ψ(I , J )t k2 −
s∈S I t ∈T J

t ∈T J s∈S I

CB 3 (m + n)11/6 log(mn)
k

(16.4)
CB 3 (m + n)11/6 log(mn)
≥ E min min◦ ks − Ψ(I , J )t k −
kt k=1 s∈K
k
The proof is similar with the proof of Proposition 13.1. We discretize both sets; we smooth the minima
using the soft-min function; and then we apply the Lindeberg principle. The main distinction is that we
2

UNIVERSALITY OF RANDOMIZED DIMENSION REDUCTION

65

can replace even less of the matrix Φ than before. The second line in (16.4) is an immediate consequence
of the facts S I ⊂ S ⊂ K ◦ and T J ⊂ T = Sn−1 .
To continue, we must identify a geometric functional that is hiding within the expression (16.4). Write
Ω := K ∩ Sm−1 . Proposition 20.1 demonstrates that
Ã ¡
!2
¢
q
E
(Ω)
n
−
(16.5)
E min min◦ ks − Ψ(I , J )t k2 ≥
− CB 2 k log m .
p
kt k=1 s∈K
CB log m
+
As in Proposition 14.1, the main tool is the Gaussian Minimax Theorem, Fact A.3, which allows us to break
down the standard normal matrix Γ into simpler quantities. The proof requires some convex duality
arguments, as well as some delicate considerations that did not arise before.
Last, we linearize the function (·)2+ in (16.5):
Ã ¡
!2
¡
¢2
¢
q
p
En (Ω) −
En (Ω) −
2
− CB
k log m ≥
− CB km.
(16.6)
p
2
CB log m
CB log m
+
We have employed the observation that
¡
¢
p
En (Ω) − ≤ E max g · s ≤ E kg k ≤ m.
s∈Ω

m

Here, g ∈ R is a standard normal vector.
Now, sequence the estimates (16.2), (16.3), (16.4), (16.5), and (16.6) to arrive at
¡
¢2
µ
¶
11/6
En (Ω) −
log(mn) q
2
3 (m + n)
E τmin (Φ; K ) ≥
−
CB
+
km
log((m
+
n)/k)
.
CB 2 log m
k
We select k = b(m + n)8/9 c, which results in the bound
¡
¢2
En (Ω) −
2
− CB 3 (m + n)17/18 log(m + n).
E τmin (Φ; K ) ≥
CB 2 log(m + n)
Note that k ≤ min{m, n}, as required, because we have assumed that m + n ≤ min{m, n}9/8 . We obtain the
result quoted in Theorem 16.2(2).
17. W HEN E MBEDDING FAILS FOR A H EAVY-TAILED R ANDOM M ATRIX
In this section, we extend Theorem 16.2 to the heavy-tailed matrix model, Model 2.4. In Section 10.3, we
show how to derive the second half of the universality result for the embedding dimension, Theorem I(a),
as a consequence.
17.1. Corollary 17.1: Main Result for the p-Moment Random Matrix Model. The following corollary
extends Theorem 16.2 to include random matrices drawn from Model 2.4.
Corollary 17.1 (RAP: p-Moment Random Matrix Model). Fix parameters p > 4 and ν ≥ 1. Place the
following assumptions:
• Let m and n be natural numbers with m + n ≤ min{m, n}9/8 .
• Let K be a closed, convex cone in Rm , and define Ω := K ∩ Sm−1 .
• Draw an m × n random matrix Φ that satisfies Model 2.4 with given p and ν.
Then the RAP functional satisfies the probability bound
(
)
¡
¢
En (Ω) −
P τmin (Φ; K ) ≤
− Cp ν3/2 (m + n)1/2−κ(p) ≤ Cp (m + n)1−p/4 .
Cp ν(m + n)(1−cp )κ(p)
The function κ(p) is strictly positive for p > 4. The strictly positive constants cp and Cp depend only on p.
The proof of Corollary 17.1 follows from Theorem 16.2 and the same kind of truncation argument that
appears in Section 15. We omit further details.

66

S. OYMAK AND J. A. TROPP

17.2. Proof of Theorem I(b) from Corollary 17.1. Theorem I(b) is an easy consequence of Corollary 17.1.
Let us restate the assumptions of the theorem:
• E is a compact subset of RD that does not contain the origin.
• The statistical dimension of E satisfies δ(E ) ≥ %D.
• The d × D random linear map Π follows Model 2.4 with parameters p > 4 and ν ≥ 1.
We must now consider the regime where the embedding dimension d ≤ (1 − ε) δ(E ). We need to demonstrate that
P {0 ∈ Π(E )} = P {E ∩ null(Π) 6= ;} ≥ 1 − Cp D 1−p/4 .
(17.1)
As in Section 10.3, the probability is a decreasing function of the embedding dimension, so we may as
well consider the case where d = b(1 − ε) δ(E )c. It is easy to see that d ≤ D ≤ %−1 d because δ(E ) ≤ d . In
particular, d + D ≤ min{d , D}9/8 .
Introduce the spherical retraction Ω := θ(E ). If cone(Ω) is a subspace, we replace Ω by a subset Ω0 with
the property that cone(Ω0 ) is a subspace of one dimension fewer than cone(Ω). Then we proceed with
the argument.
Proposition 3.8 and relation (3.2) show that
τmin (Π∗ ; cone(Ω)) > 0 implies 0 ∈ Π(Ω) implies 0 ∈ Π(E ).
Therefore, to verify (17.1), it is enough to produce a high-probability lower bound on the RAP functional
τmin (Π∗ ; cone(Ω)). With the choices Φ = Π∗ and K = cone(Ω), Corollary 17.1 yields
(
)
¡
¢
Ed (Ω) −
∗
3/2
1/2−κ(p)
P τmin (Π ; cone(Ω)) ≥
− Cp ν (d + D)
≥ 1 − Cp D 1−p/4 .
Cp ν(d + D)(1−cp )κ(p)
We need to check that the lower bound on the RAP functional is positive. That is,
¡
¢
Ed (Ω) − > Cp ν5/2 (d + D)1/2−cp κ(p) .

(17.2)

Once again, this point follows from two relatively short calculations.
Since Ω is a subset of the unit sphere, we quickly compute the excess width using (4.3):
p
p
p
p
p
¡
¢
¡
¢p
Ed (Ω) − ≥ δ(Ω) − 1 − d = δ(E ) − 1 − d ≥ 1 − 1 − ε δ(E ) − 1.

(17.3)

The justifications are the same as in Section 10.3.
We can easily bound the dimensional term in (17.2):
(d + D)1/2−cp κ(p) ≤ CD 1/2−cp κ(p) ≤ C%−1/2 D −cp κ(p)

p
p
δ(E ) ≤ C%−1/2 D −cp κ(p) δ(E ) − 1

The first inequality holds because d ≤ D, and the last two relations both rely on the assumption 1 ¿ D ≤
%−1 δ(E ). Since cp κ(p) is positive, we can find a number N := N (p, ν, %, ε) for which D ≥ N implies that
¡p
¢p
Cp ν5/2 (d + D)1/2−cp κ(p) < 1 + ε − 1 δ(E ) − 1.
Combine the last result with (17.3) to see that the claim (17.2) holds true.
17.3. Proof of Proposition 6.1: Application of RAP functional to decoding with structured errors. This
section establishes the success condition in Proposition 6.1. More precisely, we show that
s/n < ψ−1
`1 (1 − m/n) − o(1) implies Ω ∩ range(Φ) = ; with probability 1 − o(1).
The set Ω is derived from the descent cone of the `1 norm, and the calculation (6.3) shows that
δ(Ω◦ ) = n(1 − ψ`1 (s/n) − o(1)).
To begin, we assume that there are parameters %, ε > 0 for which
• The statistical dimension δ(Ω◦ ) ≥ %n.
• The message length m ≤ (1 − ε) δ(Ω◦ ).

(17.4)

UNIVERSALITY OF RANDOMIZED DIMENSION REDUCTION

67

As in Section 17.2, these conditions imply that
Ω◦ ∩ null(Φ∗ ) 6= ; with probability at least 1 − o(1).
Indeed, this statement corresponds to (17.1) under the change of variables d = m and D = n and E = Ω◦
and Π = Φ∗ . By polarity, the conclusion of (17.4) holds.
It remains to show that the parameter choice in (17.4) implies the two assumptions we have made. As
in the proof of Proposition 6.1, the condition s ≤ (1 − ξ)n ensures that δ(Ω◦ ) ≥ %n for some % > 0. Similarly,
the condition m ≤ (1 − ε)δ(Ω◦ ) holds when
m ≤ (1 − ε) · n(1 − ψ`1 (s/n) − o(1)).
Equivalently,
s/n ≤ ψ−1
`1 (1 − m/((1 − ε)n) − o(1)).
Since we can choose ε to be an arbitrarily small constant as m → ∞, it suffices that
s/n ≤ ψ−1
`1 (1 − m/n − o(1)).
This observation completes the argument.
18. T HEOREM 16.2: T RUNCATION OF THE C ONE
In this section, we argue that functional τmin (Φ; K ) does not change very much if we truncate the cone
K . Replacing the unbounded set with a compact set allows us to develop discretization arguments.
Proposition 18.1 (RAP: Truncation
p of Cone). Adopt the notation and hypotheses of Theorem 16.2. Let
S := K ◦ ∩ R Bm , where R := Crad B 2 m + n. Then
E min min◦ ks − Φt k2 ≥ E min min ks − Φt k2 − CB 4 .
kt k=1 s∈K

kt k=1 s∈S

Proof. Since 0 ∈ K ◦ , it is easy to see that
min◦ ks − Φt k ≤ kΦt k ≤ kΦk
s∈K

when kt k = 1.

Meanwhile, the triangle inequality gives the bound
ks − Φt k ≥ ksk − kΦt k ≥ ksk − kΦk

when kt k = 1.

It follows that
s ? ∈ arg min ks − Φt k
s∈K ◦

implies

ks ? k ≤ 2 kΦk

when kt k = 1.

(18.1)

Since the norm of the random matrix Φ concentrates, the bound (18.1) shows that the norm of the
minimizer s ? is unlikely to be large.
For any positive parameter R, the observation (18.1) allows us to calculate that
E τ2min (Φ; K ) = E min min◦ ks − Φt k2
kt k=1 s∈K
·
¸
2
≥ E min min◦ ks − Φt k 1{kΦk ≤ R/2}
kt k=1 s∈K
¸
·
2
ks
k
= E min min
−
Φt
1
{kΦk
≤
R/2}
kt k=1 s∈K ◦ ∩RBm
·
2
ks
k
= E min min
−
Φt
−
E
max max
◦
m
◦
kt k=1 s∈K ∩RB

kt k=1 s∈K ∩RB

(18.2)
¸
2
ks
k
−
Φt
1
{kΦk
>
R/2}
.
m

To reach the last line, we write the indicator function in terms of its the complement.

68

S. OYMAK AND J. A. TROPP

To bound the second term on the right-hand side of (18.2), crude estimates suffice.
¸
·
£
¤
2
ks − Φt k 1{kΦk > R/2} ≤ E (R + kΦk)2 1{kΦk > R/2}
E max max
◦
m
kt k=1 s∈K ∩RB
¤
£
≤ 9 E kΦk2 1{kΦk > R/2}
¢1/2
¡
¢1/2 ¡
.
≤ 9 E kΦk4
P {kΦk > R/2}
The last inequality is Cauchy–Schwarz. Since Φ satisfies the condition (B.1), Fact B.1 implies that
p
©
ª
2
P kΦk > C0 B 2 m + n + C0 B 2 ζ ≤ e−ζ .
In particular, using integration by parts,
p
¡
¢1/4
E kΦk4
≤ CB 2 m + n.
Furthermore, there is a constant Crad for which
p
ª
©
P kΦk > 12 Crad B 2 m + n ≤ (m + n)−2 .
p
If we set R := Crad B 2 m + n, then
·
¸
2
ks − Φt k 1{kΦk > R/2} ≤ CB 4 .
E max max
◦
m

(18.3)

kt k=1 s∈K ∩RB



Introduce the estimate (18.3) into (18.2) to complete the argument.
19. T HEOREM 16.2: R EPLACING M OST E NTRIES OF THE R ANDOM M ATRIX

In this section, we show that we can replace most of the entries of a random matrix Φ with standard
normal variables without changing the value of the functional E τ2min (Φ; K ) substantially
Proposition 19.1 (RAP: Partial Replacement). Let Φ be an m
p× n random matrix that satisfies Model 2.1
with magnitude bound B . Fix the parameter R := Crad B 2 m + n. Let I be a subset of {1, . . . , m} with
cardinality k, and let S I be a closed subset of R Bm for which
s ∈ SI

implies

for each index i ∈ I c .

|s i | ≤ Rk −1/2

Let J be a subset of {1, . . . , n} with cardinality k, and let T J be a closed subset of Bn for which
t ∈ TJ

implies

|t j | ≤ k −1/2

for each index j ∈ J c .

Suppose that Ψ is an m × n matrix with block form
Ψ := Ψ(I , J ) :=
Then

ΦI J
ΦI c J

·

¸
ΦI J c
.
ΓI c J c

(19.1)

¯
¯
3
11/6
¯
¯
log(mn)
¯E min min ks − Φt k2 − E min min ks − Ψt k2 ¯ ≤ CB (m + n)
.
¯
¯ t ∈T s∈S
t ∈T J s∈S I
k
J
I

As usual, Γ is an m × n standard normal matrix.
19.1. Proof of Proposition 19.1. Fix the sets I and J . As in the proof of Proposition 13.1, the error has
three components:
¯
¯
¯
¯
¯E min min ks − Φt k2 − E min min ks − Ψt k2 ¯ ≤ Cmnε
(Lemma 19.2)
¯
¯
t ∈T J s∈S I

t ∈T J s∈S I

+
+

Cβ−1 (m + n) log(1/ε)
µ
¶
βR β2 R 3
CB 3 mn 2 + 3 .
k
k

(Lemma 19.3)
(Lemma 19.4)

UNIVERSALITY OF RANDOMIZED DIMENSION REDUCTION

69

The first error comes from discretizing the sets S and T at a level ε ∈ (0, 1]. The second error appears when
we replace the minima with a soft-min function with parameter β > 0. The last error emerges from the
Lindeberg exchange argument.
To complete the proof, we set ε = (mn)−1 to make the discretization error negligible. Select the
smoothing parameter so that β3 = k 3 (m + n)/(B 3 R 3 mn). We arrive at
¯
¯
¯
¯
¯E min min ks − Φt k2 − E min min ks − Ψt k2 ¯
¯
¯
t ∈T J s∈S I

t ∈T J s∈S I

≤

CB 2 (m + n)1/3 (mn)2/3 CB R(m + n)2/3 (mn)1/3 log(mn)
+
.
k2
k

p
p
Since 2 mn ≤ m + n and R = Crad B 2 m + n, the second term dominates. We reach the stated result.

19.2. Proposition 19.1: Discretizing the Index Sets. The first step in the proof of Proposition 19.1 is to
replace the index sets by finite subsets.
Lemma 19.2 (Proposition 19.1: Discretization). Adopt the notation and hypotheses of Proposition 19.1.
Fix a parameter ε ∈ (0, 1]. Then S I contains a finite subset S εI and T J contains a finite subset T Jε whose
cardinalities satisfy
log(#S εI ) + log(#T Jε ) ≤ (m + n) log(3/ε).
Furthermore, these subsets have the property that
¯
¯
¯
¯
¯
¯
¯E min min ks − Φt k2 − E minε minε ks − Φt k2 ¯ ≤ Cmnε.
¯ t ∈T J s∈S I
¯
t ∈T J s∈S I

(19.2)

The bound (19.2) also holds if we replace Φ by Ψ.
Proof. We choose S εI to be an (Rε)-covering of S I , and T Jε to be an ε-covering of T J . Since S I is a subset
of R Bm and T J is a subset of Bn , we can be sure that the coverings have cardinality #S εI ≤ (3/ε)m and
#T Jε ≤ (3/ε)n . See [Ver12, Lem. 5.2]. The rest of the proof is essentially the same as that of Lemma 13.2, so
we omit the details.

19.3. Proposition 19.1: Smoothing the Minimum. The next step in the proof of Proposition 19.1 is to
pass from the minimum to the soft-min function.
Lemma 19.3 (Proposition 19.1: Smoothing). Adopt the notation and hypotheses of Proposition 19.1, and
let S εI and T Jε be the sets introduced in Lemma 19.2. Fix a parameter β > 0, and introduce the function
F : Rm×n → R where F (A) := −
Then

X
X
2
1
log s∈S ε t ∈T ε e−βks−At k .
I
J
β

¯
¯
¯
¯ 1¡
¢
¯
¯
log(#S εI ) + log(#T Jε ) .
¯E minε minε ks − Φt k2 − E F (Φ)¯ ≤
¯ t ∈T J s∈S I
¯ β

(19.3)

The estimate (19.3) also holds if we replace Φ by Ψ.
Proof. The proof is almost identical with that of Lemma 13.3.



19.4. Proposition 19.1: Exchanging the Entries of the Random Matrix. The main challenge in the proof
of Proposition 19.1 is to exchange most of the entries of the random matrix Φ for the entries of Ψ.
Lemma 19.4 (Proposition 19.1: Exchange). Adopt the notation and hypotheses of Proposition 19.1, and let
F be the function defined in Lemma 19.3. Then
µ
¶
βR β2 R 3
|E F (Φ) − E F (Ψ)| ≤ CB 3 mn 2 + 3 .
k
k

70

S. OYMAK AND J. A. TROPP

The proof is similar with Lemma 13.4. This time, we replace only the rows of Φ listed in I c . We incur
the same error for each of these m − k rows, so it suffices to control the error in exchanging a single row.
The following sublemma achieves this goal.
Sublemma 19.5 (Lemma 19.4: Comparison for One Row). Adopt the notation and hypotheses of Proposition 19.1, and let S εI and T Jε be the sets defined in Lemma 19.3. For i ∈ I c , introduce the function
f : Rn → R given by

f (a) := −

X
X
2
1
log s∈S ε t ∈T ε e−β(si −a·t ) +q(s,t ) ,
I
J
β

where q : S εI × T Jε → R is an arbitrary function. Suppose that ϕ ∈ Rn is a random vector with independent,
standardized entries that are bounded in magnitude by B . Suppose that ψ ∈ Rn is a random vector with
ψJ = ϕJ

and ψ J c = γ J c ,

where γ ∈ Rn is a standard normal vector. Then
µ
2 3¶
¯
¯
¯E f (ϕ) − E f (ψ)¯ ≤ CB 3 n βR + β R .
k2
k3

The proof of this result is much the same as the proof of Sublemma 13.5. There are only two points that
require care. First, we use a slightly different result to compute the derivatives.
Sublemma 19.6 (Lemma 19.4: Derivatives). Adopt the notation and hypotheses of Proposition 19.1 and
Sublemma 19.5. Let ξ : R → Rn be a linear function, so its derivative ξ0 ∈ Rn is a constant vector. For i ∈ I c ,
define the function
X
X
¡
¢
2
1
r (α) := f ξ(α) = − log s∈S ε t ∈T ε e−β(si −ξ(α)·t ) +q(s,t )
J
I
β
where q : S εI × T Jε → R is arbitrary. The third derivative of this function satisfies
Ã
!
¯ 000 ¯
¯ 0 ¯3 ¡
¢
¯r (α)¯ ≤ 48 max ¯ξ · t ¯ β Ev |s i − ξ(α) · v | + β2 Ev |s i − ξ(α) · v |3 ,
t ∈T Jε

where v ∈ T Jε is a random vector that does not depend on ξ(α).
¯
¯
Second, when making further bounds on ¯r 000 (α)¯, we need to exploit our control on the magnitude of s
on the coordinates in I c . Note that
|s i − ξ(α) · v | ≤ |s i | + |ξ(α) · v | ≤ Rk −1/2 + |ξ(α) · v |
The second inequality holds because |s i | ≤ Rk −1/2 for each i ∈ I c . Similarly,
|s i − ξ(α) · v |3 ≤ C |s i |3 + C |ξ(α) · v |3 ≤ CRk −3/2 + C |ξ(α) · v |3 .
Repeating the arguments from Sublemma 13.5, we obtain bounds of the form
·
¯
¯¸ βB 3 R Cβ2 B 3 R 3 CβB 4 + Cβ2 B 6
¯ 000 ¯
3
+
+
.
E |ϕ j | max ¯r j (α)¯ ≤
|α|≤|ϕ j |
k2
k3
k 3/2
p
The first two terms dominate the third because our choice R = Crad B 2 m + n implies that R ≥ Bk 1/2 . We
arrive at the statement of Sublemma 19.5.
20. T HEOREM 16.2: B OUNDING THE RAP F UNCTIONAL BY THE E XCESS W IDTH
The most difficult part of proving Theorem 16.2 is to identify the excess width En (Ω) after we replace
the original matrix Φ by the hybrid matrix Ψ defined in (19.1). The following result does the job.

UNIVERSALITY OF RANDOMIZED DIMENSION REDUCTION

71

Proposition 20.1 (Theorem 16.2: Excess Width Bound). Adopt the notation and hypotheses of Proposition 19.1. Let Ω := K ∩ Sm−1 . Then
Ã ¡
!2
¢
q
En (Ω) −
2
2
E min min◦ ks − Ψ(I , J )t k ≥
− CB
k log m .
p
kt k=1 s∈K
CB log m
+
The random matrix Ψ is defined in (19.1).
The proof of Proposition 20.1 occupies the rest of this section. At the highest level, the proof is similar
with the argument underlying Proposition 14.1. We write the quantity of interest as a minimax, and then
we apply the Gaussian Minimax Theorem to replace the Gaussian matrix with a pair of Gaussian vectors.
Afterward, we analyze the resulting expression to identify the Gaussian width; the new challenges appear
in this step.
20.1. Proof of Proposition 20.1. Here is an overview of the calculations that we will perform; the detailed
justifications appear in the upcoming subsections. Let us abbreviate U := K ∩ Bm . We have the chain of
inequalities
E min min◦ ks − Ψt k
kt k=1 s∈K

≥ E min max u · Ψt
kt k=1 u∈U
· ¸ ·
¸· ¸
uI
ΦI J ΦI J c
tJ
= E min max
·
ΦI c J ΓI c J c t J c
kt k=1 u∈U u I c
µ ·
¸
¶
ΦI J ΦI J c
≥ E min max u ·
t + (u I c · g I c ) kt J c k + ku I c k (h J c · t J c ) − 2
ΦI c J
0
kt k=1 u∈U
¡
p ¢
q
W (U ) − n +
≥
− CB 2 k log m
p
CB log m

(Lemma 20.2)

(Lemma 20.3)
(Lemma 20.4).

Lemma 20.2 is a standard convex duality argument, and the next line follows when we write out the
quantity of interest more explicitly. To reach the fourth line, we apply the Gaussian Minimax Theorem in
the usual way to replace the random matrix Γ with two standard normal vectors g ∈ Rm and h ∈ Rn . In a
rough sense, the remaining part of the random matrix Φ is negligible. The term (u I c · g I c ) generates the
p
Gaussian width W (U ), defined in (3.7), while the term (h J c · t J c ) contributes a dimensional factor − n.
Apply the increasing convex function (·)2+ to the inequality in the last display, and invoke Jensen’s
inequality to draw out the expectation. Notice that

W (U ) = E max m u · g ≥ E maxm−1 u · g = W (Ω).
u∈K ∩B

u∈K ∩S

p ¢
Finally, En (Ω) − = W (Ω) − n + because of (4.2). This point completes the proof.
¡

¢

¡

20.2. Proposition 20.1: Duality for the RAP Functional. The first step in the argument is to apply the
minimax inequality to pass to a saddle-point formulation that is amenable to analysis with the Gaussian
Minimax Theorem.
Lemma 20.2 (Proposition 20.1: Duality). Adopt the notation and hypotheses of Proposition 20.1. For any
point t ∈ Rn ,
min◦ ks − Ψt k ≥ max u · Ψt
s∈K

u∈U

where U := K ∩ Bm .
Proof. Write the norm as maximum:
min◦ ks − Ψt k = min◦ max
u · (Ψt − s).
m
s∈K

s∈K u∈B

72

S. OYMAK AND J. A. TROPP

The minimax inequality allows us to interchange the maximum and minimum:
³
´
min◦ ks − Ψt k ≥ max
min
u
·
(Ψt
−
s)
=
max
u
·
Ψt
−
max
u
·
s
◦
◦
m
m
s∈K

u∈B s∈K

u∈B

s∈K

◦ ◦

The value of maxs∈K ◦ u · s equals zero when u ∈ (K ) = K ; otherwise, it takes the value +∞. This step uses
the assumption that K is closed and convex. We conclude that
min◦ ks − Ψt k ≥ max m u · Ψt .
s∈K

u∈K ∩B

This is the stated result.



20.3. Proposition 20.1: Reducing the Gaussian Matrix to Some Gaussian Vectors. By an argument similar with the proof of Lemma 14.5, we can replace the Gaussian block of Ψ with two Gaussian vectors.
Lemma 20.3 (Proposition 20.1: Reducing the Gaussian Matrix). Adopt the notation and hypotheses of
Proposition 20.1. Then
·
¸
µ ·
¸
¶
ΦI J ΦI J c
ΦI J ΦI J c
E min max u ·
t ≥ E min max u ·
t + (u I c · g I c ) kt J c k + ku I c k (h J c · t J c ) − 2,
ΦI c J ΓI c J c
ΦI c J
0
kt k=1 u∈U
kt k=1 u∈U
where g ∈ Rm and h ∈ Rn be independent standard normal vectors.
Proof. There are no new ideas in this bound, so we refer the reader to Lemmas 14.4 and 14.5 for the
pattern of argument.

20.4. Proposition 20.1: Finding the Gaussian Width. To prove Proposition 20.1, most of the difficulty
arises when we seek a good lower bound for the minimax problem that appears in Lemma 20.3. We have
the following result.
Lemma 20.4 (Proposition 20.1: Finding the Gaussian Width). Adopt the notation and hypotheses of
Proposition 20.1. Define the set U := K ∩ Bm . Then
p
µ ·
¸
¶
q
W (U ) − n
ΦI J ΦI J c
E min max u ·
t + (u I c · g I c ) kt J c k + ku I c k (h J c · t J c ) ≥
− CB 2 k log m.
p
ΦI c J
0
kt k=1 u∈U
CB log m
Proof. The proof of this bound is lengthy, so we break the argument into several steps. The overall result
follows when we sequence the inequalities in Sublemmas 20.5, 20.6, 20.7, and 20.8 and consolidate the
error terms.

20.4.1. Lemma 20.4: Simplifying the Minimax I. The first step in the proof of Lemma 20.4 is to simplify
the minimax so we can identify the key terms.
Sublemma 20.5 (Lemma 20.4: Simplifying the Minimax I). Adopt the notation and hypotheses of Lemma 20.4.
Then
µ ·
¸
¶
ΦI J ΦI J c
E min max u ·
t + (u I c · g I c ) kt J c k + ku I c k (h J c · t J c )
ΦI c J
0
kt k=1 u∈U
µ
·
¸
¶
p
£
¤ tj
p
≥ E min max u · Φ J g
− n kt J c k − CB 2 k.
kt J c k
kt k=1 u∈U
+
Proof. Let us introduce notation for the quantity of interest:
µ ·
¸
¶
ΦI J ΦI J c
Q 1 := E min max u ·
t + (u I c · g I c ) kt J c k + ku I c k (h J c · t J c ) .
ΦI c J
0
kt k=1 u∈U
+

(20.1)

We can introduce the positive-part operator because the fact that 0 ∈ U ensures that the minimax is
nonnegative.

UNIVERSALITY OF RANDOMIZED DIMENSION REDUCTION

73

The first step in the argument is to reintroduce the missing piece of the random vector g . Adding and
subtracting the quantity (u I · g I ) kt J c k inside the positive-part operator in (20.1), we obtain the bound
¸
¶
µ ·
ΦI J ΦI J c
t + (u · g ) kt J c k + ku I c k (h J c · t J c ) − E max u I · g I
Q 1 ≥ E min max u ·
ΦI c J
0
kt k=1 u∈U
u∈U
+
(20.2)
µ ·
¸
¶
p
ΦI J ΦI J c
≥ E min max u ·
t + (u · g ) kt J c k + ku I c k (h J c · t J c ) − k.
ΦI c J
0
kt k=1 u∈U
+
The second inequality holds because #I = k and U is a subset of the unit ball. This step is similar with the
proof of Lemma 14.8.
Next, we combine the terms in (20.2) involving ΦI J c and the row vector h J c . Since kuk ≤ 1,
·
¸ ·
¸
uI
ΦI J c
u I · ΦI J c t J c + ku I c k (h J c · t J c ) =
·
tJc
ku I c k
hJc
°·
¸°
° ΦI J c °
°
≥ −°
(20.3)
° h J c ° kt J c k
µ°·
¶
¸°
° ΦI J c ° p
p
°
°
− n .
≥ − n kt J c k − °
hJc °
+
The (k + 1) × (n − k) random matrix on the right-hand side has independent, standardized entries that
satisfy the subgaussian estimate (B.1) with bound B . Repeating the calculations in (14.17), we see that
¶
µ°·
¸°
p
° ΦI J c ° p
°
°
E °
− n ≤ CB 2 k.
(20.4)
hJc °
+
Apply the estimate (20.3) inside the minimax in (20.2) and then use (20.4) to arrive at the lower bound
µ ·
¸
¶
µ°·
¶
¸°
° ΦI J c ° p
p
ΦI J
°
°
t + (u · g ) kt J c k − n kt J c k − E °
Q 1 ≥ E min max u ·
− n
ΦI c J J
hJc °
kt k=1 u∈U
+
+
µ
·
¸
¶
p
£
¤ tJ
p
− n kt J c k − CB 2 k.
≥ E min max u · Φ J g
kt J c k
kt k=1 u∈U
+



In the second line, we have simply consolidated terms.

20.4.2. Lemma 20.4: Simplifying the Minimax II. The next step in the proof of Lemma 20.4 is to reduce
the minimax problem in Sublemma 20.5 to a scalar optimization problem.
Sublemma 20.6 (Lemma 20.4: Simplifying the Minimax II). Adopt the notation and hypotheses of Lemma 20.4.
Then
µ
·
¸
¶
£
¤ tj
p
c
E min max u · Φ J g
− n kt J k
kt J c k
kt k=1 u∈U
n+ ¡
£
¤
p ¢
p o p
≥ E min max 0, max u · g − n α, min max u · Φ J g s − nα − k.
α∈[0,1]

u∈U

ksk=1 u∈U

Proof. Introduce the notation
µ
£
Q 2 := max u · Φ J
u∈U

g

¤

¶
¸
p
tJ
− n kt J c k .
kt J c k
+

·

(20.5)

We will develop two lower bounds on the maximum by coupling u to the random matrix in different ways.
Afterward, we combine these results into a single bound.
In the first place, we can choose the row vector u so that it depends only on the remaining Gaussian
vector:
u(g ) ∈ arg max u · g .
u∈U

74

S. OYMAK AND J. A. TROPP

Since kt k = 1, we obtain the bound
¸
µ
·
¶
£
¤ tJ
¡
p
p ¢
− n kt J c k ≥ u(g ) · g − n kt J c k + u(g ) · Φ J t J
max u · Φ J g
c
kt J k
u∈U
°
°
¡
p ¢
≥ max u · g − n kt J c k − °u(g )Φ J ° .

(20.6)

u∈U

The second term on the right-hand side of (20.6) satisfies
°
° ³ °
°2 ´1/2 p
E °u(g )Φ J ° ≤ E °u(g )Φ J °
≤ k.

(20.7)

Indeed, u(g ) is a random vector with ku(g )k ≤ 1 that is stochastically independent from Φ J , and the m × k
random matrix Φ J has independent, standardized entries.
The second bound is even simpler. Since kt k = 1,
µ
·
¸
¶
£
¤
£
¤ tJ
p
p
(20.8)
max u · Φ J g
− n kt J c k ≥ min max u · Φ J g s − n kt J c k .
c
kt
k
ksk=1 u∈U
u∈U
J
In this expression, the variable s ∈ Rk+1 .
Introducing (20.6) and (20.8) into (20.5), we arrive at
n ¡
o
°
°
£
¤
p ¢
p
Q 2 ≥ E min max 0, max u · g − n kt J c k − °u(g )Φ J ° , min max u · Φ J g s − n kt J c k
kt k=1
ksk=1 u∈U
u∈U
n ¡
£
¤
p ¢
p o p
≥ E min max 0, max u · g − n α, min max u · Φ J g s − nα − k.
α∈[0,1]

u∈U

(20.9)

ksk=1 u∈U

The zero branch in the maximum accounts for the positive-part operator in (20.5). The second line follows
from (20.7). We have also introduced a new parameter α to stand in for kt J c k.

20.4.3. Lemma 20.4: Probabilistic Bounds. The last major step in Lemma 20.4 is to develop probabilistic
bounds for the terms that arise in Sublemma 20.6.
Sublemma 20.7 (Lemma 20.4: Probabilistic Bounds). Adopt the notation and hypotheses of Lemma 20.4.
Then
n ¡
£
¤
p ¢
p o
E min max 0, max u · g − n α, min max u · Φ J g s − nα
ksk=1 u∈U
u∈U
α∈[0,1]
(
)
q
p
W (U ) − 2 p
1
≥ min max (W (U ) − n − 2)α, p
− nα − CB 2 k log m.
2 α∈[0,1]
2B log m
Proof. Introduce the notation
n ¡
£
p ¢
Q 3 := E min max 0, max u · g − n α, min max u · Φ J
α∈[0,1]

u∈U

ksk=1 u∈U

¤
p o
g s − nα .

p
We assume that W (U ) ≥ 2 + n, which is permitted because the final result would otherwise become
vacuous.
The next stage in the argument is to introduce probabilistic bounds for the branches of the maximum
and use these to control the expectation. It is convenient to abbreviate
£
¤
p
X := max u · g − n and Y := min max u · Φ J g s.
u∈U

ksk=1 u∈U

p
Note that E X = W (U )− n. Since g →
7 X (g ) is 1-Lipschitz, the Gaussian concentration inequality, Fact A.2,
implies that
©
ª
p
P X ≥ W (U ) − n − 2 ≥ 3/4.
On the other hand, Sublemma 20.10 will demonstrate that
(
)
q
W (U )
P Y ≥
− CB k log m ≥ 3/4.
p
CB log m

UNIVERSALITY OF RANDOMIZED DIMENSION REDUCTION

Therefore, taking complements and a union bound,
(
p
P X > W (U ) − n − 2 and Y >

W (U )
CB

p

log m

75

)
q
− CB k log m ≥ 1/2.

(20.10)

For each nonnegative random variable Z and each number L > 0, it holds that E Z ≥ L P {Z > L}. Using the
estimate (20.9) and the probability bound (20.10), we find that
(
Ã
!
)
q
p
p
p
1
W (U )
− CB k log m − nα − k
Q 3 ≥ min max 0, (W (U ) − n − 2)α,
p
2 α∈[0,1]
CB log m
)
(
q
p
W (U ) − 2 p
1
≥ min max (W (U ) − n − 2)α,
− nα − CB 2 k log m.
p
2 α∈[0,1]
CB log m
Once again, we have used shift-invariance of the maximum to combine the error terms. For convenience,
we have also dropped the zero branch of the maximum and introduced the number two into the numerator
in the second branch.

20.4.4. Lemma 20.4: Solving the Scalar Minimax Problem. The final step in the proof of Lemma 20.4 is to
solve the scalar minimax problem that emerges in Sublemma 20.7.
Sublemma 20.8 (Lemma 20.4: Solving the Minimax Problem). Adopt the notation and hypotheses of
Lemma 20.4. Then
(
)
p
p
W (U ) − 2 p
W (U ) − n − 2
− nα ≥
.
min max (W (U ) − n − 2)α,
p
p
α∈[0,1]
CB log m
CB log m
Proof. The first branch of the maximum is increasing in α while the second branch is decreasing in α, so
the minimum occurs when the two branches are equal, provided that this situation occurs when α ∈ [0, 1].
Setting the branches equal, we identify the point α? where the saddle value is achieved.
α? :=

b
a +c

p
W (U ) − 2
where a := W (U ) − n − 2 and b :=
p
CB log m

and c :=

p
n.

We quickly verify that α? ∈ [0, 1], so the minimax takes the value
p
p
W (U ) − n − 2 W (U ) − 2 W (U ) − n − 2
ab
=
×
=
.
p
p
a +c
W (U ) − 2
2B log m
CB log m



This is the required estimate.

20.4.5. Sublemma 20.7: Probabilistic Lower Bound for Bilinear Minimax. In this section, we explain how
to obtain a lower bound for the minimax problem in (20.8) in terms of the Gaussian width of the set U .
Sublemma 20.9 (Sublemma 20.7: Probability Bound for Bilinear Minimax). Assume that k < m, and let X
be an m × k random matrix that satisfies Model 2.1 with bound B . Let g ∈ Rm be standard normal. Let U be
a subset of the unit ball in Rm . Then
(
)
q
£
¤
W (U )
P min max u · X g s >
− CB k log m ≥ 3/4.
p
ksk=1 u∈U
CB log m
Proof. Fix ε = m −1 . Let N be an ε-net for the unit sphere in Rk+1 . The cardinality of the net satisfies
log(N ) ≤ (k + 1) log(3m) by the standard volumetric argument [Ver12, Lem. 5.2]
We can estimate the quantity of interest below by discretizing the parameter s. Since N and U are
subsets of the unit ball, we have the bound
°£
£
¤
£
¤
¤°
min max u · X g s ≥ min max u · X g s − ° X g ° ε
(20.11)
ksk=1 u∈U

s∈N u∈U

We will establish a probabilistic lower bound for the right-hand side of (20.11).

76

S. OYMAK AND J. A. TROPP

First, we develop a probability bound for the second term on the right-hand side of (20.11). A simple
spectral norm estimate suffices. The m × k random matrix X has standardized entries and g ∈ Rm is
standard normal, so
p
°£
°£
¤°
¤°
E ° X g ° ≤ E ° X g °F ≤ (k + 1)m.
As usual, k·kF denotes the Frobenius norm. Markov’s inequality now implies that
o
n°£
p
¤°
P ° X g ° ≥ 6 (k + 1)m ≥ 5/6.
It follows that
©°£
P ° X

¤°
ª
g ° ε ≥ 6 ≥ 5/6.

(20.12)

We have used the facts that ε = m −1 and k < m.
Let us turn to the second quantity on the right-hand side of (20.11). We develop a strong probability
bound for each fixed point s ∈ N , and we extend it to the entire net using the union bound. For technical
reasons, it is easier to treat the random matrix£ X and the
g separately.
¤ random vector
k
Fix a point s ∈ N , and decompose it as s = s 1 s k+1 where s 1 ∈ R . Construct a random vector u ∈ U
that satisfies
u(X ) ∈ arg max u · X s 1 .
u∈U

We may calculate that
£

max u · X
u∈U

¤

£

g s ≥ u(X ) · X

g

¤

·

s1

¸

s k+1

= u(X ) · X s 1 + (u(X ) · g )s k+1
¯
¯
≥ max u · X s 1 − ¯u(X ) · g ¯ .

(20.13)

u∈S

The last estimate relies on the fact that |s k+1 | ≤ 1 because ksk = 1.
The second term on the right-hand side of (20.13) is easy to handle using the Gaussian concentration
inequality, Fact A.2:
¯
©¯
ª
2
P ¯u(X ) · g ¯ ≥ ζ ≤ 2e−ζ /2
(20.14)
Indeed, g 7→ u(X ) · g is a 1-Lipschitz function with mean zero because the random vector u(X ) is stochastically independent from g and has norm bounded by one.
We can interpret the first term on the right-hand side of (20.13) as an “empirical width.” It takes
some work to compare this quantity with the Gaussian width. Sublemma 20.10 contains a bound for the
expectation, and Sublemma 20.11 contains a tail bound. Together, they deliver the probability inequality
(
)
2
2
W (U )
P max u · X s 1 ≤
− ζ ≤ e−ζ /(8B ) for each s ∈ N .
(20.15)
p
u∈U
CB log m
In other words, the empirical width of U is comparable with the Gaussian width, modulo a logarithmic
factor.
Introduce the two probability bounds (20.14) and (20.15) into the deterministic estimate (20.13). We
arrive at
(
)
£
¤
2
2
W (U )
P max u · X g s ≤
− 2ζ ≤ 3e−ζ /(8B ) for each s ∈ N .
p
u∈U
CB log m
Finally, we take a union bound over s ∈ N to
pobtain an estimate that is uniform over the net. Recall that
log(#N ) ≤ (k + 1) log(3m) and select ζ = 4B (k + 1) log(3m) to reach
(
)
q
W (U )
P min max u · X s 1 ≤
− CB (k + 1) log(3m)
p
s∈N u∈U
CB log m
≤ 3(#N )e−ζ
The numerical estimate holds because 1 ≤ k < m.

2

/(8B 2 )

≤ 3e−(k+1) log(3m) = 3(3m)−(k+1) ≤ 1/18. (20.16)

UNIVERSALITY OF RANDOMIZED DIMENSION REDUCTION

77

The two probability bounds (20.12) and (20.16) hold simultaneously with probability at least 3/4.
Therefore, we can substitute these results into (20.11) and adjust constants to obtain the stated bound. 
20.4.6. Sublemma 20.7: Lower Estimate for the Empirical Width. The next sublemma demonstrates that
the Gaussian width of a set is not more than a logarithmic factor larger than the empirical width of the set
as computed with bounded random variables. This is the only step in the argument for bounded random
matrices that requires the symmetry assumption.
Sublemma 20.10 (Sublemma 20.7: Empirical Width Bound). Adopt the notation and hypotheses of Sublemma 20.9, and let s be a fixed unit-norm vector. Then
E max u · X s ≥
u∈U

W (U )
CB

.
p
log m

Proof of Sublemma 20.10. Define the random vector v := (V1 , . . . ,Vn ) := X s. Our goal is to compare the
empirical width of the set U computed using the vector v with the Gaussian width of the set.
First, we develop a lower bound on the first moment of the entries of v . Fix an index i . Since the entries
of X are independent and symmetric
¯X
¯
¯X
¯
¯ k
¯
¯ k
¯
E |Vi | = E ¯ j =1 X i j s j ¯ = E ¯ j =1 η j X i j s j ¯
where {η j } is an independent family of Rademacher random variables, independent from X . The Khintchine inequality [LO94] allows us to compare the first moment with the second moment:
µ ¯
¯2 ¶1/2
´1/2
1
1 ³Xk
¯
¯Xk
2
2
|
|
|s
|X
.
E |Vi | ≥ p E X Eη ¯ j =1 η j X i j s j ¯
=p E
j
i
j
j =1
2
2

Since s has unit norm, we can regard the sum as a weighted average, and we can invoke Jensen’s inequality
to draw the average out of the square root:
¢
1 Xk ¡
E |Vi | ≥ p
E |X i j | |s j |2 .
j =1
2

Last, note that 1 = E |X i j |2 ≤ B E |X i j | because the entries of X are standardized and bounded by B . Thus,
1 Xk 1
1
|s |2 = p .
E |Vi | ≥ p
j =1 B j
2
B 2
Let us bound the width-like functional below. Since v has independent, symmetric coordinates,
Xn
Xn
E max u · X s = E max u · v = E max i =1 Vi u i = E max i =1 η i |Vi | u i
u∈U

u∈U

u∈U

u∈U

where, again, {η i } is an independent family of Rademacher random variables, independent from u. Using
a corollary of the contraction principle [LT11, Lem. 4.5],
E max u · X s ≥ mini (E |Vi |) Eη max
u∈U

u∈U

Xn
i =1

ηi ui ≥

Xn
1
p E max i =1 η i u i .
B 2 u∈U

Applying the contraction principle again [LT11, Eqn. (4.9)], we can randomize the sum with independent
Gaussian variables:
Xn
1
E max u · X s ≥
E max i =1 g i u i
p
u∈U
2B log n u∈U
Here, g := (g 1 , . . . , g n ) is a standard normal vector. Identify the Gaussian width to complete the proof. 

78

S. OYMAK AND J. A. TROPP

20.4.7. Sublemma 20.7: Lower Tail of the Empirical Width. Last, we present a concentration inequality for
the empirical width.
Sublemma 20.11 (Sublemma 20.7: Lower Tail of Empirical Width). Adopt the notation and hypotheses of
Sublemma 20.9. Let s be a fixed unit-norm vector. Then
½
¾
2
2
P max u · X s ≤ E max u · X s − ζ ≤ e−ζ /8B .
u∈U

u∈U

The most direct proof of this result relies on a version of Talagrand’s inequality [BLM13, Thm. 8.6]
obtained from the transportation cost method.
Fact 20.12 (Talagrand’s Inequality). Let X be a metric space. Suppose that f : X p → R fulfills the one-sided
Lipschitz bound
Xp
f (a) − f (z) ≤ i =1 c i (a)1ai 6=zi for all a, z ∈ X p ,
where c i : Rp → R are auxiliary functions that satisfy
Xp 2
c (a) ≤ v for all a ∈ X p .
i =1 i

Let (X 1 , . . . , X p ) be an independent sequence of random variables taking values in X , and define
Y := f (X 1 , . . . , X p ).
Then, for all ζ ≥ 0,
P {Y − E Y ≥ ζ} ≤ e−ζ
P {Y − E Y ≤ −ζ} ≤ e

2

/(2v)

−ζ2 /(2v)

,

and

.

Proof of Sublemma 20.11. Let X be the interval [−B, B ] equipped with the Euclidean distance. For a
matrix A ∈ X m×k , introduce the function
f (A) := max u · As.
u∈U

Select a point t ∈ arg maxu∈U u · As. Then
f (A) − f (Z ) ≤ t · As − t · Z s
Xm Xk
= i =1 j =1 t i s j (a i j − z i j )
Xm Xk
¯
¯
≤ i =1 j =1 2B ¯t i s j ¯ 1ai j 6=zi j .
We¯used¯ the fact that the entries of A and Z are bounded in magnitude by B . With the choice c i j (A) =
2B ¯t i s j ¯, we see that
Xm Xk
X ¯
¯2
c 2 (A) ≤ 4B 2 i , j ¯t i s j ¯ ≤ 4B 2
i =1
j =1 i j
because t , s both belong to the Euclidean unit ball. Invoke Fact 20.12 to complete the argument.



UNIVERSALITY OF RANDOMIZED DIMENSION REDUCTION

79

Part V. Back Matter
Two appendices contain statements of some results that we use throughout the paper. Appendix A
presents some facts about Gaussian analysis, while Appendix B describes some spectral bounds for
random matrices with independent entries. We conclude with acknowledgments and a list of works cited.
A PPENDIX A. T OOLS FROM G AUSSIAN A NALYSIS
We make extensive use of methods from Gaussian analysis to provide precise information about the
behavior of functions of Gaussian random variables. These results come up in many places in the paper,
so we have collected them here.
A.1. Concentration for Gaussian Lipschitz Functions. We begin with two concentration results that
apply to a Lipschitz function of independent Gaussian variables. Recall that a function f : Rn → R has
Lipschitz constant L when
¯
¯
¯ f (a) − f (b)¯ ≤ L ka − bk for all a, b ∈ Rn .
We also say, more briefly, that f is L-Lipschitz. The first result [Bog98, Thm. 1.6.4] gives a bound on the
variance of a Lipschitz function. The second result [Bog98, Thm. 1.7.6] provides a normal concentration
inequality for Lipschitz functions.
Fact A.1 (Gaussian Variance Inequality). Suppose that f : Rn → R has Lipschitz constant L. Let γ ∈ Rn be a
standard normal random vector. Then
Var[ f (γ)] ≤ L.
Equivalently,
¡
¢2
E f (γ)2 ≤ E f (γ) + L.

Fact A.2 (Gaussian Concentration Inequality). Suppose that f : Rn → R has Lipschitz constant L. Let γ ∈ Rn
be a standard normal random vector. Then, for all ζ ≥ 0,
©
ª
2
P f (γ) ≥ E f (γ) + ζ ≤ e−ζ /2 , and
©
ª
2
P f (γ) ≤ E f (γ) − ζ ≤ e−ζ /2 .
A.2. The Gaussian Minimax Theorem. To compute the expectations of certain functions of Gaussian
random variables, we depend on a comparison principle due to Gordon [Gor85, Thm. 1.1].
Let S be an abstract set. A family {Z s : s ∈ S} of real random variables is called a centered Gaussian
process when each element Z s has mean zero and each finite subcollection {Z s1 , . . . , Z sn } has a jointly
Gaussian distribution.
Fact A.3 (Gaussian Minimax Theorem). Let T and U be finite sets. Consider two centered Gaussian processes
{X t u } and {Y t u }, indexed over T ×U . For all choices of indices, suppose that
 2
2

E X t u = E Y t u
E X t u X t u0 ≤ E Yt u Yt u0


E X t u X t 0 u 0 ≥ E Y t u Y t 0 u 0 when t 6= t 0 .
Then, for all real numbers λt u and ζ,
¾
½
¾
½
¡
¢
¡
¢
P min max λt u + X t u ≥ ζ ≥ P min max λt u + Y t u ≥ ζ .
t ∈T u∈U

t ∈T u∈U

Fact A.3 extends to infinite index sets T,U by approximation.

80

S. OYMAK AND J. A. TROPP

A PPENDIX B. S PECTRAL B OUNDS FOR R ANDOM M ATRICES
Our argument also depends heavily on some non-asymptotic bounds for the spectrum of a random
matrix with independent entries. These results only give rough estimates, but they are adequate for our
purposes.
The first result gives tail bounds for the extreme singular values of a rectangular matrix with independent, subgaussian entries.
Fact B.1 (Subgaussian Matrix: Tail Bounds). Let X be an d 1 × d 2 random matrix with independent, standardized entries that are uniformly subgaussian:
¢1/p
1 ¡
≤ B.
sup p E |X i j |p
p
p≥1

(B.1)

Then the largest singular value σmax (X ) and the d 2 -th largest singular value σmin (X ) satisfy the bounds
n
o
p
p
2
P σmax (X ) > d 1 + CB 2 d 2 + CB 2 ζ ≤ e−ζ
n
o
p
p
2
P σmin (X ) < d 1 − CB 2 d 2 − CB 2 ζ ≤ e−ζ .
This result follows from [Ver12, Thm. 5.39] when we track the role of the subgaussian constant through
the proof.
The second result gives a tail bound for the norm of a matrix with independent entries that may only
have two moments; it is based on the matrix Rosenthal inequality [Tro15c, Thm. 1.1] and a standard
concentration inequality [BLM13, Thm. 15.5].
Fact B.2 (Heavy-Tailed Matrix: Norm Bound). Fix a parameter p ∈ [2, log(d 1 + d 2 )]. Let X be a d 1 × d 2
random matrix with independent entries that have the following properties.
• The entries are centered: E X i j = 0.
• The variances of the entries are uniformly bounded: Var(X i j ) ≤ α.
• The entries have uniformly bounded pth moments: E |X i j |p ≤ νp .
Then
q
n
¢ o
¡
P kX k ≥ C α(d 1 + d 2 ) log(d 1 + d 2 ) + Cν(d 1 + d 2 )2/p log(d 1 + d 2 ) ζ ≤ ζ−p .

Proof Sketch. Write the random matrix as a sum of independent random matrices:
Xd1 Xd2
X = i =1
X E ,
j =1 i j i j
where Ei j is the d 1 × d 2 matrix with a one in the (i , j ) position and zeros elsewhere. A straightforward
application of the matrix Rosenthal inequality [Tro15c, Thm. I] yields
q
¡
¢1/p
E kX k ≤ C α(d 1 + d 2 ) log(d 1 + d 2 ) + C E maxi j |X i j |p
log(d 1 + d 2 )
q
≤ C α(d 1 + d 2 ) log(d 1 + d 2 ) + Cν(d 1 d 2 )1/p log(d 1 + d 2 )
q
≤ C α(d 1 + d 2 ) log(d 1 + d 2 ) + Cν(d 1 + d 2 )2/p log(d 1 + d 2 ).
The second line follows when we replace the maximum by a sum and exploit the uniform moment
estimate. The third line is just the inequality between the geometric and arithmetic means.
A standard concentration inequality for moments [BLM13, Thm. 15.5] gives
£
p ¡
p ¤1/p
p/2 ¢1/p
E(kX k − E kX k)+
≤ C p E V+
In this expression, the variance parameter
X
£¡
¢2
¤
V+ := i j E kX k − kX (i j ) k + | X .

UNIVERSALITY OF RANDOMIZED DIMENSION REDUCTION

81

The (i , j ) entry of X (i j ) is an independent copy of the corresponding entry of X ; the remaining entries of
the two matrices are the same. Applying the usual method [BLM13, Ex. 3.14], we see that
£¡
¢2 ¤
V+ ≤ C maxi j E X i j − X i0 j | X .
Applying the same considerations as in the last paragraph, we obtain
¡
p/2 ¢1/p
≤ Cν(d 1 + d 2 )2/p .
E V+
Combine these results and apply Markov’s inequality to obtain the tail bound
©
ª
p
P kX k ≥ E kX k + Cν p(d 1 + d 2 )2/p ζ ≤ ζ−p .
Introduce the estimate for the expected norm to complete the argument.



A CKNOWLEDGMENTS
The authors would like to thank David Donoho, Surya Ganguli, Babak Hassibi, Michael McCoy, Andreas
Maurer, Andrea Montanari, Ivan Nourdin, Giovanni Peccati, Adrian Röllin, Jared Tanner, Christos Thrampoulidis, and Madeleine Udell for helpful conversations. We also thank the anonymous reviewers and the
editors for their careful reading and suggestions. SO was generously supported by the Simons Institute for
the Theory of Computing and NSF award CCF-1217058. JAT gratefully acknowledges support from ONR
award N00014-11-1002 and the Gordon & Betty Moore Foundation.
R EFERENCES
[ALMT14] D. Amelunxen, M. Lotz, M. B. McCoy, and J. A. Tropp. Living on the edge: phase transitions in convex programs with
random data. Inf. Inference, 3(3):224–294, 2014.
[BDN15] J. Bourgain, S. Dirksen, and J. Nelson. Toward a unified theory of sparse dimensionality reduction in Euclidean space.
Geom. Funct. Anal., 25(4):1009–1088, 2015.
[BGVV14] S. Brazitikos, A. Giannopoulos, P. Valettas, and B.-H. Vritsiou. Geometry of isotropic convex bodies, volume 196 of
Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 2014.
[BLM13] S. Boucheron, G. Lugosi, and P. Massart. Concentration inequalities. Oxford University Press, Oxford, 2013. A
nonasymptotic theory of independence, With a foreword by Michel Ledoux.
[BLM15] M. Bayati, M. Lelarge, and A. Montanari. Universality in polytope phase transitions and message passing algorithms.
Ann. Appl. Probab., 25(2):753–822, 2015.
[BM12]
M. Bayati and A. Montanari. The LASSO risk for Gaussian matrices. IEEE Trans. Inform. Theory, 58(4):1997–2017,
2012.
[Bog98]
V. I. Bogachev. Gaussian measures, volume 62 of Mathematical Surveys and Monographs. American Mathematical
Society, Providence, RI, 1998.
[BS10]
Z. Bai and J. W. Silverstein. Spectral analysis of large dimensional random matrices. Springer Series in Statistics.
Springer, New York, second edition, 2010.
[BY93]
Z. D. Bai and Y. Q. Yin. Limit of the smallest eigenvalue of a large-dimensional sample covariance matrix. Ann.
Probab., 21(3):1275–1294, 1993.
[CDS98]
S. S. Chen, D. L. Donoho, and M. A. Saunders. Atomic decomposition by basis pursuit. SIAM J. Sci. Comput., 20(1):33–
61, 1998.
[Cha06]
S. Chatterjee. A generalization of the Lindeberg principle. Ann. Probab., 34(6):2061–2076, 2006.
[CRPW12] V. Chandrasekaran, B. Recht, P. A. Parrilo, and A. S. Willsky. The convex geometry of linear inverse problems. Found.
Comput. Math., 12(6):805–849, 2012.
[CRT06]
E. J. Candès, J. Romberg, and T. Tao. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inform. Theory, 52(2):489–509, 2006.
[CRTV05] E. Candès, M. Rudelson, T. Tao, and R. Vershynin. Error correction via linear programming. In Foundations of
Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on, pages 668–681, Oct 2005.
[CSPW11] V. Chandrasekaran, S. Sanghavi, P. A. Parrilo, and A. S. Willsky. Rank-sparsity incoherence for matrix decomposition.
SIAM J. Optim., 21(2):572–596, 2011.
[CW13]
K. L. Clarkson and D. P. Woodruff. Low rank approximation and regression in input sparsity time. In STOC’13—
Proceedings of the 2013 ACM Symposium on Theory of Computing, pages 81–90. ACM, New York, 2013.
[DDW+ 07] M. A. Davenport, M. F. Duarte, M. B. Wakin, J. N. Laska, D. Takhar, K. F. Kelly, and R. G. Baraniuk. The smashed filter
for compressive classification and target recognition. In Proc. SPIE, volume 6498, pages 64980H–64980H–12, 2007.

82

[DGM13]
[DH01]
[DJM13]
[Don06a]
[Don06b]
[Don06c]
[DS01]
[DT06]
[DT09a]

[DT09b]
[DT10]
[EK12]
[Faz02]
[FM14]
[FR13]
[GG15]
[GNP14]
[Gor85]
[Gor88]
[Gru07]
[HMT11]
[JM14]
[Kle55]
[KM11]
[KN14]
[KY14]
[Lin22]
[LO94]
[LT11]
[Mah11]
[Mas00]
[Mau12]

S. OYMAK AND J. A. TROPP

D. L. Donoho, M. Gavish, and A. Montanari. The phase transition of matrix recovery from Gaussian measurements
matches the minimax MSE of matrix denoising. Proc. Natl. Acad. Sci. USA, 110(21):8405–8410, 2013.
D. L. Donoho and X. Huo. Uncertainty principles and ideal atomic decomposition. IEEE Trans. Inform. Theory,
47(7):2845–2862, 2001.
D. L. Donoho, I. Johnstone, and A. Montanari. Accurate prediction of phase transitions in compressed sensing via a
connection to minimax denoising. IEEE Trans. Inform. Theory, 59(6):3396–3433, 2013.
D. L. Donoho. Compressed sensing. IEEE Trans. Inform. Theory, 52(4):1289–1306, 2006.
D. L. Donoho. For most large underdetermined systems of linear equations the minimal l 1 -norm solution is also the
sparsest solution. Comm. Pure Appl. Math., 59(6):797–829, 2006.
D. L. Donoho. High-dimensional centrally symmetric polytopes with neighborliness proportional to dimension.
Discrete Comput. Geom., 35(4):617–652, 2006.
K. R. Davidson and S. J. Szarek. Local operator theory, random matrices and Banach spaces. In Handbook of the
geometry of Banach spaces, Vol. I, pages 317–366. North-Holland, Amsterdam, 2001.
D. Donoho and J. Tanner. Thresholds for the recovery of sparse solutions via l1 minimization. In Information Sciences
and Systems, 2006 40th Annual Conference on, pages 202–206, March 2006.
D. Donoho and J. Tanner. Observed universality of phase transitions in high-dimensional geometry, with implications
for modern data analysis and signal processing. Philos. Trans. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., 367(1906):4273–
4293, 2009. With electronic supplementary materials available online.
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.
D. L. Donoho and J. Tanner. Counting the faces of randomly-projected hypercubes and orthants, with applications.
Discrete Comput. Geom., 43(3):522–541, 2010.
Y. C. Eldar and G. Kutyniok, editors. Compressed sensing. Cambridge University Press, Cambridge, 2012. Theory and
applications.
M. Fazel. Matrix rank minimization with applications. PhD thesis, Stanford, 2002.
R. Foygel and L. Mackey. Corrupted sensing: novel guarantees for separating structured signals. IEEE Trans. Inform.
Theory, 60(2):1223–1247, 2014.
S. Foucart and H. Rauhut. A mathematical introduction to compressive sensing. Applied and Numerical Harmonic
Analysis. Birkhäuser/Springer, New York, 2013.
P. Gao and S. Ganguli. On simplicity and complexity in the brave new world of large-scale neuroscience. Curr. Opinion
Neurobiology, 32:148–155, 2015.
L. Goldstein, I. Nourdin, and G. Peccati. Gaussian phase transitions and conic intrinsic volumes: Steining the Steiner
formula. Available at http://arXiv.org/abs/1411.6265, Nov. 2014.
Y. Gordon. Some inequalities for Gaussian processes and applications. Israel J. Math., 50(4):265–289, 1985.
Y. Gordon. On Milman’s inequality and random subspaces which escape through a mesh in Rn . In Geometric aspects
of functional analysis (1986/87), volume 1317 of Lecture Notes in Math., pages 84–106. Springer, Berlin, 1988.
P. M. Gruber. Convex and discrete geometry, volume 336 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer, Berlin, 2007.
N. Halko, P. G. Martinsson, and J. A. Tropp. Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions. SIAM Rev., 53(2):217–288, 2011.
A. Javanmard and A. Montanari. Hypothesis testing in high-dimensional regression under the Gaussian random
design model: asymptotic theory. IEEE Trans. Inform. Theory, 60(10):6522–6554, 2014.
V. L. Klee, Jr. Separation properties of convex cones. Proc. Amer. Math. Soc., 6:313–318, 1955.
S. B. Korada and A. Montanari. Applications of the Lindeberg principle in communications and statistical learning.
IEEE Trans. Inform. Theory, 57(4):2440–2450, 2011.
D. M. Kane and J. Nelson. Sparser Johnson-Lindenstrauss transforms. J. ACM, 61(1):Art. 4, 23, 2014.
A. Knowles and J. Yin. Anisotropic local laws for random matrices. Available at http://arXiv.org/abs/1410.3516,
Nov. 2014.
J. W. Lindeberg. Eine neue Herleitung des Exponentialgesetzes in der Wahrscheinlichkeitsrechnung. Math. Z.,
15(1):211–225, 1922.
R. Latała and K. Oleszkiewicz. On the best constant in the Khinchin-Kahane inequality. Studia Math., 109(1):101–104,
1994.
M. Ledoux and M. Talagrand. Probability in Banach spaces. Classics in Mathematics. Springer-Verlag, Berlin, 2011.
Isoperimetry and processes, Reprint of the 1991 edition.
M. W. Mahoney. Randomized algorithms for matrices and data. Foundations and Trends® in Machine Learning,
3(2):123–224, 2011.
P. Massart. About the constants in Talagrand’s concentration inequalities for empirical processes. Ann. Probab.,
28(2):863–884, 2000.
A. Maurer. Thermodynamics and concentration. Bernoulli, 18(2):434–454, 2012.

UNIVERSALITY OF RANDOMIZED DIMENSION REDUCTION

[Men10]
[Men14]
[MOO10]
[MPTJ07]
[MT13]
[MT14a]
[MT14b]
[NN13]

[OH10]
[OH13]
[OTH13]

[PW15]
[Rot73]
[RV08]
[San52]
[San76]
[Sar06]
[Sch50]
[Sio58]
[Sto09]
[Sto13]
[SW08]
[TAH15]
[Tao12]
[TH15]

[Tib96]
[Tik15]
[TOH15]

[Tro59]
[Tro06]

83

S. Mendelson. Empirical processes with a bounded ψ1 diameter. Geom. Funct. Anal., 20(4):988–1027, 2010.
S. Mendelson. A remark on the diameter of random sections of convex bodies. In B. Klartag and E. Milman, editors,
Geometric Aspects of Functional Analysis, volume 2116 of LNM, pages 395–404. Springer, 2014.
E. Mossel, R. O’Donnell, and K. Oleszkiewicz. Noise stability of functions with low influences: invariance and
optimality. Ann. of Math. (2), 171(1):295–341, 2010.
S. Mendelson, A. Pajor, and N. Tomczak-Jaegermann. Reconstruction and subgaussian operators in asymptotic
geometric analysis. Geom. Funct. Anal., 17(4):1248–1282, 2007.
M. B. McCoy and J. A. Tropp. The achievable performance of convex demixing. Available at http://arXiv.org/
abs/arXiv:1309.7478, Sep. 2013.
M. B. McCoy and J. A. Tropp. From Steiner formulas for cones to concentration of intrinsic volumes. Discrete Comput.
Geom., 51(4):926–963, 2014.
M. B. McCoy and J. A. Tropp. Sharp recovery bounds for convex demixing, with applications. Found. Comput. Math.,
14(3):503–567, 2014.
J. Nelson and H. L. Nguyen. OSNAP: faster numerical linear algebra algorithms via sparser subspace embeddings. In
2013 IEEE 54th Annual Symposium on Foundations of Computer Science—FOCS 2013, pages 117–126. IEEE Computer
Soc., Los Alamitos, CA, 2013.
S. Oymak and B. Hassibi. New null space results and recovery thresholds for matrix rank minimization. Available at
http://arXiv.org/abs/1011.6326, Nov. 2010.
S. Oymak and B. Hassibi. Asymptotically exact denoising in relation to compressed sensing. Available at http:
//arXiv.org/abs/1305.2714, May 2013.
S. Oymak, C. Thrampoulidis, and B. Hassibi. The squared-error of generalized lasso: A precise analysis. In Communication, Control, and Computing (Allerton), 2013 51st Annual Allerton Conference on, pages 1002–1009, Oct 2013.
Available at http://arXiv.org/abs/1311.0830.
M. Pilanci and M. Wainwright. Randomized sketches of convex programs with sharp guarantees. Information Theory,
IEEE Transactions on, 61(9):5096–5115, Sept 2015.
V. I. Rotar’. Certain limit theorems for polynomials of degree two. Teor. Verojatnost. i Primenen., 18:527–534, 1973.
M. Rudelson and R. Vershynin. On sparse reconstruction from Fourier and Gaussian measurements. Comm. Pure
Appl. Math., 61(8):1025–1045, 2008.
L. A. Santaló. Integral geometry in spaces of constant curvature. Repub. Argentina. Publ. Comision Nac. Energia
Atomica. Ser. Mat., 1(1):68, 1952.
L. A. Santaló. Integral geometry and geometric probability. Addison-Wesley Publishing Co., Reading, Mass.-LondonAmsterdam, 1976. With a foreword by Mark Kac, Encyclopedia of Mathematics and its Applications, Vol. 1.
T. Sarlos. Improved approximation algorithms for large matrices via random projections. In Foundations of Computer
Science, 2006. FOCS ’06. 47th Annual IEEE Symposium on, pages 143–152, Oct 2006.
L. Schläfli. Gesammelte mathematische Abhandlungen. Band I. Verlag Birkhäuser, Basel, 1950.
M. Sion. On general minimax theorems. Pacific J. Math., 8:171–176, 1958.
M. Stojnic. Various thresholds for `1 -optimization in compressed sensing. Available at http://arXiv.org/abs/
0907.3666, July 2009.
M. Stojnic. Regularly random duality. Available at http://arXiv.org/abs/1303.7295, Mar. 2013.
R. Schneider and W. Weil. Stochastic and integral geometry. Probability and its Applications (New York). SpringerVerlag, Berlin, 2008.
C. Thrampoulidis, E. Abbasi, and B. Hassibi. High-dimensional error anlaysis of regularized m-estimators. Forthcoming, Nov. 2015.
T. Tao. Topics in random matrix theory, volume 132 of Graduate Studies in Mathematics. American Mathematical
Society, Providence, RI, 2012.
C. Thrampoulidis and B. Hassibi. Isotropically random orthogonal matrices: Performance of lasso and minimum
conic singular values. In Information Theory (ISIT), 2015 IEEE International Symposium on, pages 556–560, June
2015. Available at http://arXiv.org/abs/1503.07236.
R. Tibshirani. Regression shrinkage and selection via the lasso. J. Roy. Statist. Soc. Ser. B, 58(1):267–288, 1996.
K. Tikhomirov. The limit of the smallest singular value of random matrices with i.i.d. entries. Adv. Math., 284:1–20,
2015.
C. Thrampoulidis, S. Oymak, and B. Hassibi. The Gaussian min–max theorem in the presence of convexity. In
Proceedings of The 28th Conference on Learning Theory (COLT), Jul. 2015. Available at http://arXiv.org/abs/
1408.4837.
H. F. Trotter. An elementary proof of the central limit theorem. Arch. Math., 10:226–234, 1959.
J. A. Tropp. Just relax: convex programming methods for identifying sparse signals in noise. IEEE Trans. Inform.
Theory, 52(3):1030–1051, 2006.

84

[Tro15a]

[Tro15b]
[Tro15c]
[TV15]
[Ver12]
[Ver15]
[Wen62]
[Woo14]
[Yin86]

S. OYMAK AND J. A. TROPP

J. A. Tropp. Code for reproducing figures from Oymak & Tropp, Universality Laws for Randomized Dimension
Reduction, with Applications, 2015.ropp, Universality Laws for Randomized Dimension Reduction, with Applications,
2015. Available at http://users.cms.caltech.edu/~jtropp, Nov. 2015.
J. A. Tropp. Convex recovery of a structured signal from independent random measurements. In G. Pfander, editor,
Sampling Theory: A Rennaissance. Birkhäuser Verlag, 2015. Available at http://arXiv.org/abs/1405.1102.
J. A. Tropp. The expected norm of a sum of independent random matrices: An elementary approach. In HighDimensional Probability VII, Cargèse, June 2015. To appear. Available at http://arXiv.org/abs/1506.04711.
T. Tao and V. Vu. Random matrices: universality of local spectral statistics of non-Hermitian matrices. Ann. Probab.,
43(2):782–874, 2015.
R. Vershynin. Introduction to the non-asymptotic analysis of random matrices. In Compressed sensing, pages 210–268.
Cambridge Univ. Press, Cambridge, 2012.
R. Vershynin. Estimation in high dimensions: A geometric perspective. In G. Pfander, editor, Sampling Theory: A
Rennaissance. Birkhäuser Verlag, 2015.
J. G. Wendel. A problem in geometric probability. Math. Scand., 11:109–111, 1962.
D. P. Woodruff. Sketching as a tool for numerical linear algebra. Foundations and Trends® in Theoretical Computer
Science, 10(1–2):1–157, 2014.
Y. Q. Yin. Limiting spectral distribution for a class of random matrices. J. Multivariate Anal., 20(1):50–68, 1986.

