# Optimal Reconstruction from Linear Queries

arXiv: https://arxiv.org/abs/2605.19625 · HTML: https://mlsanity.com/paper/2605.19625/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 15 references that are in the map.
- First posted on arXiv 19 May 2026.

## Builds on (most cited first, 4 of 4)

- [Preserving Statistical Validity in Adaptive Data Analysis](https://mlsanity.com/paper/1411.2664/) (2014)
- [Algorithmic Stability for Adaptive Data Analysis](https://mlsanity.com/paper/1511.02513/) (2015)
- [Generalization in Adaptive Data Analysis and Holdout Reuse](https://mlsanity.com/paper/1506.02629/) (2015)
- [Reconstruction and Secrecy under Approximate Distance Queries](https://mlsanity.com/paper/2511.06461/) (2025)

## Abstract (arXiv)

We study the problem of reconstructing an unknown point in ℝd from approximate linear queries. This setting arises naturally in applications ranging from low-dimensional remote sensing and signal recovery to high-dimensional data analysis and privacy-sensitive inference. Our main goal is to characterize the optimal reconstruction error as a function of the number of queries T, the ambient dimension d, and the noise parameter δ. We first analyze the limit T → ∞ and show that the optimal reconstruction error converges to the explicit value √2d/(d+1) δ, which plays a role analogous to the Bayes optimal error in supervised learning. When the dimension is fixed, we show that the excess error above this limit decays doubly exponentially fast as T → ∞, a rate that is significantly faster than those typically encountered in learning curves. When the dimension grows, we show that a number of queries on the order of exp(d) is necessary and sufficient to achieve vanishing excess error. Finally, we introduce and analyze an improper variant of the reconstruction problem. From a technical perspective, our main contribution is a generalization of Jung's theorem (1901). The classical theorem bounds the maximum possible radius of a set of diameter 1 and characterizes extremal bodies. Our generalization provides a robust variant that characterizes near-extremal bodies and is proved via geometric and dynamical arguments exploiting symmetry and Lie group actions.