Optimal Reconstruction from Linear Queries

2026

Read Optimal Reconstruction from Linear Queries (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-19625.txt.

Introduction

Filmus, Moran and Nesterova study rebuilding an unknown point from approximate linear queries, a setting spanning remote sensing and privacy-sensitive inference. Their goal is the optimal reconstruction error from query count, dimension and noise. In the infinite-query limit the error converges to an exact value like the Bayes optimal error in supervised learning. With fixed dimension the excess error decays doubly exponentially, while with growing dimension exponentially many queries prove necessary and enough. The key core generalizes Jung's 1901 theorem to a robust variant for near-extremal bodies.

Catalog record

YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE125896
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.19625

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Optimal Reconstruction from Linear Queries Abstract We study the problem of reconstructing an unknown point in ℝ d \mathbb{R}^{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 T , the ambient dimension d d , and the noise parameter δ \delta . We first analyze the limit T → ∞ T\to\infty and show that the optimal reconstruction error converges to the explicit value 2 ​ d / ( d + 1 ) ​ δ \sqrt{2d/(d+1)}\,\delta , 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 → ∞ T\to\infty , 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 ) \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. \coltauthor \Name Yuval Filmus \Email [email protected] \addr Technion – Israel Institute of Technology and \Name Shay Moran \Email [email protected] \addr Technion – Israel Institute of Technology \addr Google Research and \Name Elizaveta Nesterova \Email [email protected] \addr Technion – Israel Institute of Technology 1 Introduction In this work we study the following question: How accurately can an unknown point x^{*}\in\mathbb{R}^{d} be reconstructed using linear measurements? We formalize this question via a linear reconstruction game . In this game, an adversary holds a secret point x^{*}\in\mathbb{R}^{d} , and at each round: 1. The reconstructor submits a linear query in the form of a unit vector v\in\mathbb{R}^{d} , \|v\|_{2}=1 . 1 1 1 Equivalently, we can allow arbitrary vectors v , and require the error to be at most \delta\|v\|_{2} . Without this normalization, the reconstructor can cheat by scaling v by a large amount, effectively reducing the error. 2. The adversary replies with an adversarially chosen value r satisfying |r-\langle v,x^{*}\rangle|\leq\delta, where \delta>0 is a fixed additive noise parameter, and \langle v,x\rangle is the standard inner product. The reconstructor can choose its queries adaptively, based on the answers to previous queries. After a given number of rounds T , it outputs an estimate \hat{x} , aiming to minimize the \ell_{2} -distance \|\hat{x}-x^{*}\|_{2} . The linear reconstruction game captures phenomena that arise naturally in both low- and high-dimensional settings. In low-dimensional geometric problems, it models adaptive sensing and signal acquisition, where measurement directions are chosen sequentially in order to localize an unknown signal or object in space. Related formulations also arise in data analysis and privacy — often, but not exclusively, in high dimensions — where linear queries are used to probe a dataset, and noise is added to limit reconstruction of sensitive information. A discrete variant of this problem, in which both the hidden point and the queries are restricted to the Boolean cube \{0,1\}^{n} , was introduced by 7 , and played a foundational role in the development of differential privacy. Subsequent work in private and adaptive data analysis, as well as in the statistical query model, has studied this setting extensively, primarily from the perspective of preventing reconstruction ( 4 ; 9 ; 8 ; 16 ) . Related questions also appear in the adaptive sensing literature ( 3 ; 12 ) , though most of that work assumes stochastic noise, whereas we consider adversarial noise. We study the optimal minimax reconstruction error against an arbitrary adversary: Main Question What is the optimal reconstruction error that can be guaranteed against an arbitrary (worst-case) adversary, as a function of the error parameter \delta , the number of rounds T , and the dimension d ? From a learning-theoretic perspective, this question can be viewed as a natural instance of interactive learning, in which a learner adaptively queries an oracle and seeks to reconstruct an unknown target from noisy feedback. Here, the secret point x^{*} plays the role of the concept to be learned. 2 Main results In this section, we outline the key definitions and results. More detailed definitions and statements are deferred to Section 4 . The optimal reconstruction error is the smallest worst-case loss achievable by a reconstructor, i.e., the smallest worst-case loss that the “best” reconstructor can achieve. We denote the optimal reconstruction error for noise level \delta>0 , dimension d , and T interaction rounds by \mathrm{OPT}_{d}(T,\delta) . Our first main theorem identifies the reconstruction error achievable (in the limit) given an unlimited number of rounds. Main Theorem \thetheorem (Asymptotic optimal error) \mathrm{OPT}_{d}(\infty,\delta):=\lim_{T\to\infty}\mathrm{OPT}_{d}(T,\delta)=\sqrt{\frac{2d}{d+1}}\delta. From a learning-theoretic viewpoint, the limiting value \mathrm{OPT}_{d}(\infty,\delta) is analogous to the Bayes-optimal error: it is the best performance achievable under the interaction and noise constraints of the model. This motivates studying the excess reconstruction error , \mathsf{ExcessErr}_{d}(T,\delta)\;:=\;\mathrm{OPT}_{d}(T,\delta)-\mathrm{OPT}_{d}(\infty,\delta). Our second main theorem, which is also our main technical contribution, shows that \mathsf{ExcessErr}_{d}(T,\delta) decays at a doubly exponential rate in T when d\geq 2 (when d=1 , there is only one unit vector v=1 up to sign, and so one round suffices). Main Theorem \thetheorem (Doubly-exponential decay of excess error) For every dimension d\geq 2 there exists T^{\prime}_{d} such that for every T\geq T^{\prime}_{d} : \mathsf{ExcessErr}_{d}(T,\delta)=2^{-2^{\Theta_{d}(T)}}\delta. The linear dependence on \delta in Main Theorems 2 and 2 is not accidental: in fact, the reconstruction game is invariant under rescaling \delta . We elaborate on this further in the Technical Overview and prove it in Section 4 . The proof of Main Theorem 2 relies on a reconstruction algorithm with a natural two-phase structure. In the first phase, which can be viewed as a preprocessing step, the reconstructor queries a sufficiently dense (but oblivious) set of directions in order to obtain a coarse geometric localization of the hidden point. In the second phase, the reconstructor exploits this localization to adaptively refine its estimate, leading to the doubly-exponential decay of the excess error. This rapid refinement crucially relies on our robust Jung theorem: a robust variant of Jung’s theorem, which identifies a small set of particularly informative directions whose queries sharply reduce the remaining uncertainty. We elaborate on this robust variant of Jung’s theorem and explain how it is leveraged algorithmically in the proof overview in the next section. The cost of the first, preprocessing phase grows rapidly with the dimension d , as it requires querying a dense net of directions on the unit sphere. This naturally raises the question of whether such a dependence on the dimension is inherent. Our final main theorem answers this question in the affirmative and identifies T=\exp(d) as a threshold for achieving vanishing excess error, in the following sense: Main Theorem \thetheorem (Dimension-dependent query budgets) Let T:\mathbb{N}\to\mathbb{N} be a query

Read the complete text