A resolution of the Gaussian hyperplane tessellation conjecture on the sphere

2025/08/07 by Sjoerd Dirksen, Dirksen, Sjoerd, Nigel Q․ D. Strachan +1
#FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2508.05194

Abstract

We investigate how many hyperplanes with independent standard Gaussian directions one needs to produce a δ-uniform tessellation of a subset S of the Euclidean sphere, meaning that for any pair of points in S the fraction of hyperplanes separating them corresponds to their geodesic distance up to an additive error δ. It was conjectured that δ^-2w_*(S)² Gaussian random hyperplanes are necessary and sufficient for this purpose, where w_*(S) is the Gaussian complexity of S. We falsify this conjecture by constructing a set S where δ^-3w_*(S)² Gaussian hyperplanes are necessary and sufficient.

Citations

• Sharp estimates on random hyperplane tessellations
• Fast binary embeddings with Gaussian circulant matrices: improved bounds
• Near-Optimal Sample Complexity Bounds for Circulant Binary Embedding
• Near-Optimal Bounds for Binary Embeddings of Arbitrary Sets
• Binary Embedding: Fundamental Limits and Fast Algorithm
• Dvoretzky type theorems for subgaussian coordinate projections
• Circulant Binary Embedding
• Robust 1-bit compressed sensing and sparse logistic regression: A convex\n programming approach
• Dimension reduction by random hyperplane tessellations
• One-bit compressed sensing by linear programming
• Robust 1-Bit Compressive Sensing via Binary Stable Embeddings of Sparse Vectors
• Near-optimal estimates for the ℓ^p-Lipschitz constants of deep random ReLU neural networks

Related

• Sharp estimates on random hyperplane tessellations
• Dimension reduction by random hyperplane tessellations
• On the Number of Faces and Radii of Cells Induced by Gaussian Spherical Tessellations
• Restriction of 3D arithmetic Laplace eigenfunctions to a plane
• Non-Gaussian Hyperplane Tessellations and Robust One-Bit Compressed Sensing