In many applications (such as compressed sensing), we use a random projection to capture a subset of . Sometimes, you can show that a random projection performs well by appealing to the Johnson–Lindenstrauss lemma, which says that the pairwise distances of a finite collection of points are nearly preserved (for example, JL implies RIP). In other cases, we might call a projection “good” if its null space avoids a certain subset of (think the null space property), but how might we show that a random projection is good? By appealing to * Gordon’s escape through a mesh theorem*, which says that a random subspace avoids a subset (“escapes a mesh”) provided the subset is small in some sense. The purpose of this blog entry is to prove this theorem and provide some intuition.

Throughout, we take to be a -dimensional vector with iid entries, and we denote , which satisfies . Given a closed subset , then its * Gaussian width* is defined as

.

As we will see, Gaussian width is an important measure of the size of a set. Intuitively, the Gaussian width of is more or less the expected width of when measured in a random direction (it’s actually half of the * mean width*, as defined here), and it plays a crucial role in several results, including the following:

**Gordon’s Comparison Theorem (Corollary 1.2 in Gordon’s paper).** Take a closed subset of the unit sphere in , and draw a matrix with iid entries. Then

,

and

.

Note that for any fixed , has the same distribution as , and so Gordon’s comparison theorem says you can expect and to be no more than away from . This sort of guarantee is much weaker than the kind you’d get by taking a union bound over an epsilon net and appealing to concentration of measure. Still, this result is very useful because it’s often strong enough, and for some sets, the Gaussian width is easier to control than the size of the requisite epsilon net. For example, this paper uses linear programming duality to estimate the Guassian width of the set of vectors which are avoided in the null space property, and Proposition 3.6 in this paper similarly bounds the Gaussian width of sets in terms of an expected distance from a dual cone.

To prove Gordon’s escape through a mesh theorem, we will make use of Gordon’s comparison theorem as well as the following deviation inequality:

**Proposition 1 (Corollary 2.3 in these notes).** If is -Lipschitz, i.e., for every , then

.

The meat of the argument is in the proof of the following proposition, which says that a random subspace escapes an -thickened mesh provided the original mesh is contained in the sphere and has a sufficiently small Gaussian width. The original (and more general) version of this result is Theorem 3.3 in Gordon’s paper, but I think the generality makes the proof needlessly difficult to parse.

**Proposition 2.** Take a closed subset of the unit sphere in , and let denote the closed ball centered at the origin of radius . If , then an -dimensional subspace drawn uniformly from the Grassmannian satisfies

.

* Proof:* We will take to be the null space of a matrix with iid entries; indeed, this random subspace is uniformly distributed on the Grassmannian. To estimate the desired probability

,

we first note that

,

where the last step follows from a union bound (to see this, consider the contrapositive). Note that the second term above is precisely . We will use Proposition 1 to bound the first term:

Given matrices and , note that

,

and similarly . Putting these together then gives

,

i.e., the mapping is -Lipschitz with respect to the Frobenius norm. As such, by Proposition 1, a matrix with iid entries satisfies

for any . Next, monotonocity of expectation gives that

,

where is the first identity basis element. As such, we have

.

Overall, we have , and rearranging gives a lower bound:

As such, it remains to find a lower bound on . [At this point, you might be inclined to hunt for an epsilon net of and do a union bound, but this is not what we do here. (!)] Taking to be and independent of , then a union bound gives

,

where the last step follows from the Chernoff bound. Furthermore (and this is the most interesting part of the proof), Lemma 3.1 in Gordon’s paper gives the following lower bound on the left-hand side above:

,

where and are independent. Note that and have the same distribution for each , as do and , but it is not at all obvious how the above probabilities should be related (due to the dependence on ). It turns out that the second mixed moments of for and can be bounded in terms of the corresponding moments of , which in turn leads to the probability estimate given above (thanks to Theorem B in Gordon’s paper). [This actually bears some resemblance to the proof of Gordan’s comparison theorem, which similarly bounds second mixed moments and appeals to Theorem A.]

At this point, we have

so it remains to find a lower bound on . To this end, a union bound gives

Since is -Lipschitz in the -norm, Proposition 1 can be used to bound the first term above. Also, the second term can be reexpressed by noting that has the same distribution as . Indeed,

.

To bound the second term above, we first claim that is -Lipschitz. To see this, given , suppose without loss of generality that , and that is maximized at . Then

.

Thus, Proposition 1 gives

,

provided . To satisfy this positivity condition, first note that the Gordon comparison theorem (with taken to be the closed ball centered at the origin of radius ) gives . As such,

,

and since the first term of is strictly positive by assumption, it suffices to pick such that

.

Overall, we have

Combining (1), (2) and (3) then gives

.

We now pick so as to balance and combine the terms on the right-hand side. Specifically, we take such that , which by the definition of , explicitly means

.

Then , completing the result.

Now we essentially take the limit as to get the main theorem:

**Gordon’s Escape Through a Mesh Theorem (Corollary 3.4 in Gordon’s paper).** Take a closed subset of the unit sphere in . If , then an -dimensional subspace drawn uniformly from the Grassmannian satisfies

.

* Proof:* First note that for every , the closest has norm since it’s an orthogonal projection of . As such, is equivalent to having for every and , which in turn implies that when

.

Indeed, the minimum is achieved (and thus ) since is compact. As such, we have

,

where the last step follows from the fact that implies for every . Since by assumption, then we also have whenever

.

At this point, we appeal to Proposition 2 to bound for such and take the limit to get the claimed bound.

## 4 thoughts on “Gordon’s escape through a mesh theorem”