Minimum number of continuous adaptive measurements for vector recovery
For $m \ge 2$, consider deterministic algorithms that recover $x \in \mathbb{R}^m$ from exact real measurements taken in sequence, $$y_j = \lambda_{j, y_1, \dots, y_{j-1}}(x),$$ where for every fixed history the functional $\lambda_{j, y_1, \dots, y_{j-1}} : \mathbb{R}^m \to \mathbb{R}$ is continuous, while its dependence on the preceding values is arbitrary (no continuity in the history is imposed), followed by an arbitrary reconstruction $\Phi : \mathbb{R}^n \to \mathbb{R}^m$. Let $N(m)$ be the smallest integer $n$ such that for every $\varepsilon > 0$ some such algorithm using at most $n$ measurements satisfies $$\sup_{x \in \mathbb{R}^m} \|x - \Phi(y_1, \dots, y_n)\|_2 \le \varepsilon.$$ With linear measurements, adaptive or not, or with non-adaptive continuous measurements, $m$ measurements are needed. By the Borsuk–Ulam theorem one continuous measurement does not suffice, so $N(m) \ge 2$, and Krieg, Novak and Ullrich proved $N(m) \le \lceil \log_2 m \rceil + 1$, improving their earlier bound of $\lceil \log_2 (m+1) \rceil + 1$ Lipschitz-continuous measurements.
Problem. Determine $N(m)$, or its sharp asymptotic growth as $m \to \infty$. In particular, is $N(m)$ unbounded, or can an absolute constant number of such measurements achieve arbitrary precision in every dimension?
Source: Krieg and Ullrich (2026), §10.3, after Theorem 10.6, who do not know whether that bound is optimal or whether a constant number of measurements suffices, and Krieg, Novak and Ullrich (2026), §3; stated in this form by AIM — Open Applied Problems.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- CA
- Keywords
- adaptive algorithms, AIM Open Applied Problems, continuous measurements, information-based complexity
References
@article{krieg2026acta,
author = {Krieg, David and Ullrich, Mario},
title = {Approximation of functions: optimal sampling and complexity},
journal = {Acta Numer.},
volume = {35},
year = {2026},
pages = {273--457},
doi = {10.1017/S0962492925100287},
eprint = {2602.02066},
archivePrefix = {arXiv},
}
@misc{krieg2026continuous,
author = {Krieg, David and Novak, Erich and Ullrich, Mario},
title = {How many continuous measurements are needed to learn a vector?},
year = {2026},
eprint = {2412.06468},
archivePrefix = {arXiv},
note = {Version 2, 22 September 2026},
}
@misc{aim-continuous-adaptive-measurement-complexity,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Minimum number of continuous adaptive measurements for vector recovery}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/1b7c7fd251c1643bb41f0e3cef38704bcef410fd/problems/553-continuous-adaptive-measurement-complexity.md},
note = {Entry 553 at commit 1b7c7fd, 2026-10-13},
}
Resolution claims
The bounds are $\lfloor\log_2m\rfloor+1\le N(m)\le\lceil\log_2m\rceil+1$. This gives the sharp leading asymptotic and exact values at powers of two. It does not determine every $N(m)$, including $N(3)$.
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-16 | Needs verification → Solution claimed | — | Recorded here: AIM @ a153f46, siavash-sadeghi-553/aim553_report.pdf. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00671, "Minimum number of continuous adaptive measurements for vector recovery", clopen.solutions.