Adaptive measurements require logarithmic rounds to learn vectors on spheres
A Borsuk-Ulam theorem for adaptive continuous measurements
Computational Complexity
Summary
This paper studies the minimum number of adaptive continuous measurements needed to distinguish points on a sphere in multi-dimensional space. The authors prove that if you have fewer than about the logarithm (base 2) of the dimension of the space, you cannot tell apart two opposite points on the sphere using such measurements. This shows that to accurately learn points inside a ball, you must make at least that many adaptive measurements. The proof uses a famous topological result called the Borsuk-Ulam theorem and extends its ideas to adaptive settings.
What this means in practice
- •For sensor network designers: Plan the minimal number of adaptive sensing steps needed to guarantee certain accuracy in measuring signals modeled by points in high-dimensional balls.
- •For signal processing engineers: Determine fundamental limits in multistage adaptive measurement schemes for reconstructing continuous signals with bounded error.
A theory result. No direct application yet.
Authors
Mario Ullrich
Abstract
We prove a Borsuk-Ulam theorem for adaptive measurements: if $2^n\le m$, then any $n$ adaptively chosen continuous functionals take identical values at two antipodal points of any sphere in $\mathbb{R}^m$. Consequently, at least $\lceil\log_2(m+1)\rceil$ adaptive continuous measurements are needed to learn the vectors of a ball in $\mathbb{R}^m$ with an error smaller than its radius, which matches the recently obtained upper bound up to one measurement. The bound extends to Bernstein widths in Banach spaces. The main idea of the proof was found by Claude Fable 5, an AI model developed by Anthropic, and we document the development in a last section.