Spherical Discrepancy Minimization and Algorithmic Lower Bounds for\n Covering the Sphere

2019/07/11 by Chris Jones, Jones, Chris, Matt McPartlon +1 · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Numerical Analysis Techniques #Computational Complexity (cs.CC) #Digital Image Processing Techniques #FOS: Computer and information sciences #Mathematical Approximation and Integration

paper · pdf · doi:10.48550/arxiv.1907.05515

openalex publication_date 2019/07/11 · openalex created_date 2022/07/28 · openalex updated_date 2026/07/28

Abstract

Inspired by the boolean discrepancy problem, we study the following\noptimization problem which we term \Spherical Discrepancy: given m\nunit vectors v₁, \…, v_m, find another unit vector x that minimizes\n\max_i \⟨ x, v_i\⟩. We show that \Spherical Discrepancy is\nAPX-hard and develop a multiplicative weights-based algorithm that achieves\noptimal worst-case error bounds up to lower order terms. We use our algorithm\nto give the first non-trivial lower bounds for the problem of covering a\nhypersphere by hyperspherical caps of uniform volume at least\n2^-o(\√(n)). We accomplish this by proving a related covering bound in\nGaussian space and showing that in this \large cap regime the bound\ntransfers to spherical space. Up to a log factor, our lower bounds match known\nupper bounds in the large cap regime.\n

Cited by

• On the computation of the cosine measure in high dimensions

Related

• On the Optimality of Random Partial Sphere Coverings in High Dimensions
• On the lower bounds for the spherical cap discrepancy
• Spherical coverage verification
• The Sphere Covering Inequality and Its Applications
• Some spherical coverings on S2 and their algebraic numbers