The problem of uniform tessellation of the unit sphere (or its subsets) by hyperplanes, or equivalently, almost isometric embeddings of subsets of the sphere into the Hamming cube, has been raised in the work of Plan and Vershynin. It asks for the smallest number of hyperplanes, such that the induced Hamming distance (i.e. the proportion of hyperplanes that separate the two given points) uniformly approximates the geodesic distance. The setup of this question naturally relates it to the so-called one-bit compressed sensing. In the joint work with Michael Lacey we adopt two new points of view on this problem. First, we look at it through the prism of empirical processes and find that the bounds may be controlled in terms of the supremum of the "hemisphere process" (rather than the more standard Gaussian width).
In particular, we establish one-bit analogs of classical results (e.g., the Johnson--Lindenstrauss lemma), which may be roughly summarized as: theoretically, one-bit sensing is just as good as the standard compressed sensing. Furthermore, we observe that the question of uniform tessellation may be rephrased as a problem about geometric discrepancy, thus introducing tools and ideas from this field. This allows us to show that, in the asymptotic case, ``jittered sampling" performs better than a random choice of hyperplanes. Speaker(s): Dmitriy Bilyk (University of Minnesota)