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:

Continue reading →