pith. sign in

arxiv: 2605.19625 · v1 · pith:IKG4W2ROnew · submitted 2026-05-19 · 💻 cs.LG

Optimal Reconstruction from Linear Queries

Yuval Filmus , Shay Moran , Elizaveta Nesterova This is my paper

Pith reviewed 2026-05-20 07:59 UTC · model grok-4.3

classification 💻 cs.LG
keywords reconstruction from linear queriesoptimal error boundsJung's theorem generalizationhigh-dimensional geometrynoise toleranceasymptotic analysisdoubly exponential convergence
0
0 comments X

The pith

The minimal error for reconstructing a point in R^d from noisy linear queries converges to sqrt(2d/(d+1)) delta as the query count goes to infinity.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper determines the best achievable accuracy when recovering an unknown vector in d-dimensional space using many noisy linear measurements. It proves that this accuracy approaches sqrt(2d/(d+1)) times the noise bound delta in the limit of unlimited queries, mirroring the role of Bayes error in standard learning. For a fixed dimension the difference from this limit vanishes doubly exponentially fast with added queries, but when the dimension increases the number of queries must grow exponentially with d to get close to the limit. The proof rests on a new geometric result that extends Jung's classical theorem on the smallest enclosing ball for sets of fixed diameter.

Core claim

In the limit as the number of linear queries T tends to infinity, the optimal reconstruction error is sqrt(2d/(d+1)) delta. This value is tight and is established through a robust generalization of Jung's theorem that characterizes bodies achieving nearly the maximal possible radius for a given diameter.

What carries the argument

A robust generalization of Jung's theorem that characterizes near-extremal bodies of given diameter using geometric and dynamical arguments based on symmetry and Lie group actions.

If this is right

  • The excess reconstruction error above the limiting value decays doubly exponentially with the number of queries when d is fixed.
  • Order of exp(d) queries are necessary and sufficient to drive the excess error to zero when the dimension d grows.
  • The same limiting error bound holds for the improper reconstruction setting where the output is not required to be in R^d.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • This limiting error could benchmark algorithm performance in practical noisy reconstruction tasks.
  • The geometric characterization might apply to related problems in robust estimation or query complexity.
  • Double-exponential convergence suggests that moderate numbers of queries suffice for near-optimal results in low dimensions.

Load-bearing premise

Each linear query is corrupted by noise bounded in absolute value by delta, and the reconstruction procedure may return a value outside the original d-dimensional space.

What would settle it

For small fixed dimensions such as d equals 1 or 2, compute or simulate the minimal reconstruction error for very large T and check whether it approaches exactly the predicted value sqrt(2d/(d+1)) delta.

Figures

Figures reproduced from arXiv: 2605.19625 by Elizaveta Nesterova, Shay Moran, Yuval Filmus.

Figure 1
Figure 1. Figure 1: A secret point x ∗ and an output xˆT such that ∥xˆT − x ∗∥ ≥ rad(ΦT ) [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 3
Figure 3. Figure 3: Reuleaux triangle of diameter 1 and Chebyshev radius Jung2 = q 1 3 . The vertices of the highlighted triangle constitute the unique witness. where Jungd = OPTd(∞, 1/2) = q d 2(d+1) is Jung’s constant (see Theorem 4). The doubly exponential rate in Main Theorem 2 is unusual. Moran and Nesterova (2025) proved a doubly exponential lower bound in a related setting (distance queries), which we repurpose for our… view at source ↗
Figure 4
Figure 4. Figure 4: For any prediction rule Gˆ there exists a secret point x ∗ ∈ ΦT and a direction v such that [PITH_FULL_IMAGE:figures/full_fig_p025_4.png] view at source ↗
read the original abstract

We study the problem of reconstructing an unknown point in $\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$, the ambient dimension $d$, and the noise parameter $\delta$. We first analyze the limit $T \to \infty$ and show that the optimal reconstruction error converges to the explicit value $\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 \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)$ 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript studies reconstruction of an unknown point in R^d from T noisy linear queries with per-query noise bounded by δ. It claims that the optimal reconstruction error converges to the explicit value sqrt(2d/(d+1)) δ as T → ∞. For fixed d the excess error above this limit decays doubly exponentially in T; when d grows, Θ(exp(d)) queries are necessary and sufficient for the excess error to vanish. An improper reconstruction variant is analyzed. The central technical contribution is a robust generalization of Jung's theorem (1901) proved via geometric and dynamical arguments that exploit symmetry and Lie group actions.

Significance. If the claims hold, the work supplies a sharp, closed-form information-theoretic limit for bounded-noise linear reconstruction that is directly analogous to the Bayes-optimal error. The doubly exponential convergence rate for fixed d is a notable departure from typical learning-curve exponents. The robust Jung theorem generalization, obtained through symmetry and Lie-group techniques, may have independent value in convex geometry and robust optimization. Credit is due for the parameter-free limiting expression and the joint treatment of fixed-d and growing-d regimes.

minor comments (3)
  1. [Abstract] Abstract: the statement that the limiting error 'plays a role analogous to the Bayes optimal error' is evocative; a one-sentence elaboration of the analogy (e.g., both are explicit minimax quantities independent of the estimator) would improve immediate clarity.
  2. [Introduction / technical contribution paragraph] The paragraph describing the technical contribution mentions 'geometric and dynamical arguments exploiting symmetry and Lie group actions' but provides no high-level outline; adding a single sentence sketching the symmetry reduction would aid readers without lengthening the paper.
  3. [Problem formulation] The noise model is stated as 'bounded by δ in each linear query'; confirm that this bound is uniform across all directions and independent of the query vector norm, as this is used in the slab-intersection argument for the limiting radius.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of the manuscript, the recognition of its significance, and the recommendation for minor revision. We appreciate the acknowledgment of the sharp limiting reconstruction error, the doubly exponential convergence for fixed dimension, and the technical contribution via the robust generalization of Jung's theorem.

Circularity Check

0 steps flagged

No significant circularity; limit follows from classical Jung theorem on slab intersections

full rationale

The T→∞ limiting error sqrt(2d/(d+1)) δ is obtained by applying the classical Jung theorem (1901) to the uncertainty set formed by intersecting slabs of width 2δ in all directions. This set has diameter ≤2δ and is contained in a ball of the stated radius, with the regular simplex achieving equality. The paper's own robust generalization of Jung is used only for finite-T and growing-d regimes; the infinite-query claim requires no additional assumptions, fitted parameters, or self-citations. The derivation is geometrically self-contained and externally verifiable via the 1901 theorem, satisfying the criteria for an independent result.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The analysis rests on standard Euclidean geometry and bounded noise assumptions typical for query models; no free parameters are fitted to data and no new entities are postulated.

axioms (2)
  • domain assumption Linear queries are of the form a·x + noise with |noise| <= delta
    Invoked when defining the reconstruction problem and the limiting error (abstract opening paragraph).
  • domain assumption The reconstruction procedure may be improper (output not required to be in R^d)
    Stated explicitly when introducing the improper variant.

pith-pipeline@v0.9.0 · 5785 in / 1349 out tokens · 41158 ms · 2026-05-20T07:59:17.334664+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

49 extracted references · 49 canonical work pages

  1. [1]

    , title =

    Blumenthal, Leonard M. , title =. 1970 , note =

    work page 1970

  2. [2]

    Asian Journal of Mathematics & Statistics , volume =

    Li, Shengqiao , title =. Asian Journal of Mathematics & Statistics , volume =. 2011 , issn =

    work page 2011

  3. [3]

    The Thirty-ninth Annual Conference on Neural Information Processing Systems , year =

    Reconstruction and Secrecy under Approximate Distance Queries , author=. The Thirty-ninth Annual Conference on Neural Information Processing Systems , year =

    work page

  4. [4]

    Revealing information while preserving privacy , booktitle =

    Irit Dinur and Kobbi Nissim , editor =. Revealing information while preserving privacy , booktitle =. 2003 , url =. doi:10.1145/773153.773173 , timestamp =

    work page doi:10.1145/773153.773173 2003

  5. [5]

    ArXiv , year=

    Statistical Queries and Statistical Algorithms: Foundations and Applications , author=. ArXiv , year=

    work page

  6. [6]

    On the Fundamental Limits of Adaptive Sensing , journal =

    Arias-Castro, Ery and Cand. On the Fundamental Limits of Adaptive Sensing , journal =. 2013 , doi =

    work page 2013

  7. [7]

    , title =

    Haupt, Jarvis and Castro, Rui and Nowak, Robert D. , title =. IEEE Digital Signal Processing Workshop and IEEE Signal Processing Education Workshop (DSP/SPE) , year =

    work page

  8. [8]

    Preserving Statistical Validity in Adaptive Data Analysis , booktitle =

    Cynthia Dwork and Vitaly Feldman and Moritz Hardt and Toniann Pitassi and Omer Reingold and Aaron Leon Roth , editor =. Preserving Statistical Validity in Adaptive Data Analysis , booktitle =. 2015 , url =. doi:10.1145/2746539.2746580 , biburl =

    work page doi:10.1145/2746539.2746580 2015

  9. [9]

    Generalization in Adaptive Data Analysis and Holdout Reuse , booktitle =

    Cynthia Dwork and Vitaly Feldman and Moritz Hardt and Toniann Pitassi and Omer Reingold and Aaron Roth , editor =. Generalization in Adaptive Data Analysis and Holdout Reuse , booktitle =. 2015 , url =

    work page 2015

  10. [10]

    Rothblum , title =

    Moritz Hardt and Guy N. Rothblum , title =. 51th Annual. 2010 , url =. doi:10.1109/FOCS.2010.85 , biburl =

    work page doi:10.1109/focs.2010.85 2010

  11. [11]

    Ullman , title =

    Moritz Hardt and Jonathan R. Ullman , title =. 55th. 2014 , url =. doi:10.1109/FOCS.2014.55 , biburl =

    work page doi:10.1109/focs.2014.55 2014

  12. [12]

    doi: 10.1145/2897518.2897566

    Raef Bassily and Kobbi Nissim and Adam D. Smith and Thomas Steinke and Uri Stemmer and Jonathan R. Ullman , editor =. Algorithmic stability for adaptive data analysis , booktitle =. 2016 , url =. doi:10.1145/2897518.2897566 , biburl =

    work page doi:10.1145/2897518.2897566 2016

  13. [13]

    Cynthia Dwork and Aaron Roth , title =. Found. Trends Theor. Comput. Sci. , volume =. 2014 , url =. doi:10.1561/0400000042 , biburl =

    work page doi:10.1561/0400000042 2014

  14. [14]

    Kearns , title =

    Michael J. Kearns , title =. J. 1998 , url =. doi:10.1145/293347.293351 , biburl =

    work page doi:10.1145/293347.293351 1998

  15. [15]

    Nadler , title =

    Alejandro Illanes and Sam B. Nadler , title =

    work page

  16. [16]

    2013 , publisher=

    Mucherino, Antonio and Lavor, Carlile and Liberti, Leo and Maculan, Nelson , title=. 2013 , publisher=

    work page 2013

  17. [17]

    Geo-indistinguishability: Differential privacy for location-based systems , booktitle=

    Andr. Geo-indistinguishability: Differential privacy for location-based systems , booktitle=

    work page

  18. [18]

    2014 , publisher =

    Schneider, Rolf , title =. 2014 , publisher =

    work page 2014

  19. [19]

    Fast construction of nets in low dimensional metrics and their applications , author=. SIAM J. Computing , volume=

    work page

  20. [20]

    Rodgers , title =

    Clive D. Rodgers , title =. 2000 , publisher =

    work page 2000

  21. [21]

    Data Reconstruction: When You See It and When You Don't , booktitle =

    Edith Cohen and Haim Kaplan and Yishay Mansour and Shay Moran and Kobbi Nissim and Uri Stemmer and Eliad Tsfadia , editor =. Data Reconstruction: When You See It and When You Don't , booktitle =. 2025 , url =. doi:10.4230/LIPICS.ITCS.2025.39 , timestamp =

    work page doi:10.4230/lipics.itcs.2025.39 2025

  22. [22]

    Twomey , title =

    S. Twomey , title =. 1977 , publisher =

    work page 1977

  23. [23]

    and Skiena, S.S

    Disser, Y. and Skiena, S.S. , title =. Handbook of Discrete and Computational Geometry, Third Edition , editor =. 2017 , edition =

    work page 2017

  24. [24]

    Algorithmica , volume =

    Julien Bensmail and Dorian Mazauric and Fionn Mc Inerney and Nicolas Nisse and Stéphane Pérennes , title =. Algorithmica , volume =. 2020 , doi =. hal-01717629v3 , url =

    work page 2020

  25. [25]

    Seager , title =

    Suzanne M. Seager , title =. Ars Combinatoria , volume =. 2013 , url =

    work page 2013

  26. [26]

    Journal of Applied Probability , author=

    Sequential metric dimension for random graphs , volume=. Journal of Applied Probability , author=. 2021 , pages=. doi:10.1017/jpr.2021.16 , number=

    work page doi:10.1017/jpr.2021.16 2021

  27. [27]

    Melter , title =

    Frank Harary and Robert A. Melter , title =. Ars Combinatoria , volume =

    work page

  28. [28]

    Slater , title =

    Peter J. Slater , title =. Congressus Numerantium , volume =

    work page

  29. [29]

    and Frongillo, Rafael M

    Tillquist, Richard C. and Frongillo, Rafael M. and Lladser, Manuel E. , title =. SIAM Review , volume =. 2023 , doi =

    work page 2023

  30. [30]

    Rates of Convergence of Minimum Distance Estimators and Kolmogorov's Entropy , volume =

    Yatracos, Yannis , year =. Rates of Convergence of Minimum Distance Estimators and Kolmogorov's Entropy , volume =. The Annals of Statistics , doi =

    work page

  31. [31]

    1963 , url=

    On Two Problems Of Information Theory , author=. 1963 , url=

    work page 1963

  32. [32]

    2017 , journal =

    Cynthia Dwork and Adam Smith and Thomas Steinke and Jonathan Ullman , title =. 2017 , journal =

    work page 2017

  33. [33]

    The price of privacy and the limits of LP decoding , Year =

    Cynthia Dwork and Frank McSherry and Kunal Talwar , Booktitle =. The price of privacy and the limits of LP decoding , Year =

    work page

  34. [34]

    New Efficient Attacks on Statistical Disclosure Control Mechanisms

    Cynthia Dwork and Sergey Yekhanin , Booktitle =. New Efficient Attacks on Statistical Disclosure Control Mechanisms. , Year =

    work page

  35. [35]

    Iftach Haitner and Noam Mazor and Jad Silbak and Eliad Tsfadia , title =

    work page

  36. [36]

    2024 , eprint=

    ATTAXONOMY: Unpacking Differential Privacy Guarantees Against Practical Adversaries , author=. 2024 , eprint=

    work page 2024

  37. [37]

    Extracting Training Data from Large Language Models , booktitle =

    Nicholas Carlini and Florian Tram. Extracting Training Data from Large Language Models , booktitle =. 2021 , pages =

    work page 2021

  38. [38]

    Extracting training data from diffusion models , year =

    Carlini, Nicholas and Hayes, Jamie and Nasr, Milad and Jagielski, Matthew and Sehwag, Vikash and Tram\`. Extracting training data from diffusion models , year =. Proceedings of the 32nd USENIX Conference on Security Symposium , articleno =

    work page

  39. [39]

    2022 IEEE Symposium on Security and Privacy (SP) , pages=

    Reconstructing training data with informed adversaries , author=. 2022 IEEE Symposium on Security and Privacy (SP) , pages=. 2022 , organization=

    work page 2022

  40. [40]

    Calibrating Noise to Sensitivity in Private Data Analysis , Volume =

    Cynthia Dwork and Frank McSherry and Kobbi Nissim and Adam Smith , Booktitle =. Calibrating Noise to Sensitivity in Private Data Analysis , Volume =

    work page

  41. [41]

    2000 , publisher=

    Topology , author=. 2000 , publisher=

    work page 2000

  42. [42]

    New Results and New Trends in Computer Science , series =

    Emo Welzl , title =. New Results and New Trends in Computer Science , series =. 1991 , doi =

    work page 1991

  43. [43]

    2008 , isbn =

    Mark de Berg and Otfried Cheong and Marc van Kreveld and Mark Overmars , title =. 2008 , isbn =

    work page 2008

  44. [44]

    Convex and Discrete Geometry , author=

    work page

  45. [45]

    Lectures on Discrete Geometry , author=

    work page

  46. [46]

    Journal of the ACM (JACM) , volume=

    A learning theory approach to noninteractive database privacy , author=. Journal of the ACM (JACM) , volume=. 2013 , publisher=

    work page 2013

  47. [47]

    In: Proceedings of the Thirty-ninth Annual AC M Symposium on Theory of Computing, pp

    Dwork, Cynthia and McSherry, Frank and Talwar, Kunal , title =. 2007 , isbn =. doi:10.1145/1250790.1250804 , booktitle =

    work page doi:10.1145/1250790.1250804 2007

  48. [48]

    Sloan and Gy

    Dana Angluin and Martins Krikis and Robert H. Sloan and Gy. Malicious Omissions and Errors in Answers to Membership Queries , journal =. 1997 , url =. doi:10.1023/A:1007311411259 , timestamp =

    work page doi:10.1023/a:1007311411259 1997

  49. [49]

    Slonim , title =

    Dana Angluin and Donna K. Slonim , title =. Mach. Learn. , volume =. 1994 , url =. doi:10.1007/BF00993160 , timestamp =

    work page doi:10.1007/bf00993160 1994