Optimal Reconstruction from Linear Queries

• URL: http://arxiv.org/abs/2605.19625v1
• Date: Tue, 19 May 2026 10:04:37 GMT
• Title: Optimal Reconstruction from Linear Queries
• Abstract summary: We study the problem of reconstructing an unknown point in $mathbbRd$ from approximate linear queries.<n>This setting arises naturally in applications ranging from low-dimensional remote sensing and signal recovery to high-dimensional data analysis and privacy-sensitive inference.
• Score: 22.749520200232624
• License: http://creativecommons.org/licenses/by/4.0/
• 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 $δ$. We first analyze the limit $T \to \infty$ and show that the optimal reconstruction error converges to the explicit value $\sqrt{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 \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.

Related papers

• A Closed-Form Formula for Consistent Lipschitz Regression on Metric Spaces with Sparse Neural Network Realizations [10.292476979020522]
  We introduce a simple closed-form two-stage'' formula $hatf$ for reconstructing an unknown Lipschitz function.<n>Our main result is a high-probability uniform ($Linfty$) recovery guarantee that jointly controls approximation and statistical errors.
  arXiv  Detail & Related papers  (2026-09-02T20:10:29Z)
• Bayesian Best-Arm Identification with Abstention: A Polynomial-to-Exponential Phase Transition [51.253617466579335]
  We study the Bayesian fixed-budget best-arm identification problem in which a learner can abstain from making a terminal recommendation.<n>We analyze the probability of undetected error--the risk of recommending a suboptimal arm without abstaining.
  arXiv  Detail & Related papers  (2026-06-28T05:07:27Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  A fundamental and long-standing challenge is their efficient approximation.<n>We develop a linear-space algorithm that requires $P(|hatboldsymbol-boldsymbol|_2geq)leq $ for all commonly used semi-values.<n>Our algorithm allows explicit minimization of the mean square error for each specific utility function.
  arXiv  Detail & Related papers  (2026-04-09T16:38:14Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem.<n>Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms.
  arXiv  Detail & Related papers  (2026-03-19T15:53:41Z)
• The power of small initialization in noisy low-tubal-rank tensor recovery [19.197039630139464]
  We study the problem of recovering a low-tubal-rank tensor $mathcalX_starin mathbbRn times n times k$ from noisy linear measurements.
  arXiv  Detail & Related papers  (2026-03-03T08:29:04Z)
• Parameter-free Algorithms for the Stochastically Extended Adversarial Model [59.81852138768642]
  Existing approaches for the Extended Adversarial (SEA) model require prior knowledge of problem-specific parameters, such as the diameter of the domain $D$ and the Lipschitz constant of the loss functions $G$.<n>We develop parameter-free methods by leveraging the Optimistic Online Newton Step (OONS) algorithm to eliminate the need for these parameters.
  arXiv  Detail & Related papers  (2025-10-06T10:53:37Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks. In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
  arXiv  Detail & Related papers  (2024-04-29T15:04:07Z)
• Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computation [52.73824786627612]
  This paper establishes new convergence results for textitgeodesic strongly monotone games.<n>Our key result shows that RGD attains last-iterate linear convergence in a textitgeometry-agnostic fashion.<n>Overall, this paper presents the first geometry-agnostic last-iterate convergence analysis for games beyond the Euclidean settings.
  arXiv  Detail & Related papers  (2023-06-29T01:20:44Z)
• Restricted Strong Convexity of Deep Learning Models with Smooth Activations [31.003601717265006]
  We study the problem of optimization of deep learning models with smooth activation functions. We introduce a new analysis of optimization based on Restricted Strong Convexity (RSC) Ours is the first result on establishing geometric convergence of GD based on RSC for deep learning models.
  arXiv  Detail & Related papers  (2022-09-29T21:24:26Z)
• Last iterate convergence of SGD for Least-Squares in the Interpolation regime [19.05750582096579]
  We study the noiseless model in the fundamental least-squares setup. We assume that an optimum predictor fits perfectly inputs and outputs $langle theta_*, phi(X) rangle = Y$, where $phi(X)$ stands for a possibly infinite dimensional non-linear feature map.
  arXiv  Detail & Related papers  (2021-02-05T14:02:20Z)
• Multiscale regression on unknown manifolds [13.752772802705978]
  We construct low-dimensional coordinates on $mathcalM$ at multiple scales and perform multiscale regression by local fitting. We analyze the generalization error of our method by proving finite sample bounds in high probability on rich classes of priors. Our algorithm has quasilinear complexity in the sample size, with constants linear in $D$ and exponential in $d$.
  arXiv  Detail & Related papers  (2021-01-13T15:14:31Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  We study the problem of high-dimensional robust linear regression where a learner is given access to $n$ samples from the generative model $Y = langle X,w* rangle + epsilon$ We propose estimators for this problem under two settings: (i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance and (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  arXiv  Detail & Related papers  (2020-07-16T06:44:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.