Sharp Estimates on Random Hyperplane Tessellations
Sjoerd Dirksen, Shahar Mendelson, Alexander Stollenwerk · SIAM Journal on Mathematics of Data Science · 2022
Abstract. We study the problem of generating a hyperplane tessellation of an arbitrary set [Formula: see text] in [Formula: see text], ensuring that the Euclidean distance between any two points corresponds to the fraction of hyperplanes separating them up to a prespecified error [Formula: see text]. We focus on random Gaussian tessellations with uniformly distributed shifts and derive sharp bounds on the number of hyperplanes [Formula: see text] that are required. This result has natural applications in data dimension reduction—it yields a binary version of the Johnson–Lindenstrauss embedding—and signal processing under coarse quantization. Surprisingly, our lower estimates falsify the conjecture that [Formula: see text], where [Formula: see text] is the Gaussian width of [Formula: see text], is optimal. This conjecture is the natural analogue of a conjecture by Plan and Vershynin on random tessellations of subsets of the Euclidean sphere. As it turns out, the true optimal rate is larger by an order of magnitude in the accuracy parameter [Formula: see text] and depends in an intricate way on the geometry of the set. In particular, we give an explicit example where [Formula: see text] is required. To the best of our knowledge, the fact that the optimal error decay rate depends on the geometry of the set [Formula: see text] is a new phenomenon in the general context of random embeddings.