Post-processing optimization and optimal bounds for non-adaptive shadow tomography

• URL: http://arxiv.org/abs/2601.16266v1
• Date: Thu, 22 Jan 2026 19:01:01 GMT
• Title: Post-processing optimization and optimal bounds for non-adaptive shadow tomography
• Authors: Andrea Caprotti, Joshua Morris, Borivoje Dakić,
• Abstract summary: Overcomplete POVMs are known to outperform minimally complete measurements in many tomography and estimation tasks.<n>We formulate the choice of reconstruction coefficients as a convex minimax problem and give an algorithm with guaranteed convergence.<n> Numerical examples show that the resulting estimators can dramatically reduce sampling complexity.
• Score: 0.12234742322758417
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Informationally overcomplete POVMs are known to outperform minimally complete measurements in many tomography and estimation tasks, and they also leave a purely classical freedom in shadow tomography: the same observable admits infinitely many unbiased linear reconstructions from identical measurement data. We formulate the choice of reconstruction coefficients as a convex minimax problem and give an algorithm with guaranteed convergence that returns the tightest state-independent variance bound achievable by post-processing for a fixed POVM and observable. Numerical examples show that the resulting estimators can dramatically reduce sampling complexity relative to standard (canonical) reconstructions, and can even improve the qualitative scaling with system size for structured noncommuting targets.

Related papers

• Multi-Dimensional Visual Data Recovery: Scale-Aware Tensor Modeling and Accelerated Randomized Computation [51.65236537605077]
  We propose a new type of network compression optimization technique, fully randomized tensor network compression (FCTN)<n>FCTN has significant advantages in correlation characterization and transpositional in algebra, and has notable achievements in multi-dimensional data processing and analysis.<n>We derive efficient algorithms with guarantees to solve the formulated models.
  arXiv  Detail & Related papers  (2026-02-13T14:56:37Z)
• On the Optimal Construction of Unbiased Gradient Estimators for Zeroth-Order Optimization [57.179679246370114]
  A potential limitation of existing methods is the bias inherent in most perturbation estimators unless a stepsize is proposed.<n>We propose a novel family of unbiased gradient scaling estimators that eliminate bias while maintaining favorable construction.
  arXiv  Detail & Related papers  (2025-10-22T18:25:43Z)
• Low-Rank Tensor Recovery via Variational Schatten-p Quasi-Norm and Jacobian Regularization [49.85875869048434]
  We propose a CP-based low-rank tensor function parameterized by neural networks for implicit neural representation.<n>To achieve sparser CP decomposition, we introduce a variational Schatten-p quasi-norm to prune redundant rank-1 components.<n>For smoothness, we propose a regularization term based on the spectral norm of the Jacobian and Hutchinson's trace estimator.
  arXiv  Detail & Related papers  (2025-06-27T11:23:10Z)
• Dimension reduction via score ratio matching [0.9012198585960441]
  We propose a framework, derived from score-matching, to extend gradient-based dimension reduction to problems where gradients are unavailable.<n>We show that our approach outperforms standard score-matching for problems with low-dimensional structure.
  arXiv  Detail & Related papers  (2024-10-25T22:21:03Z)
• Enabling Tensor Decomposition for Time-Series Classification via A Simple Pseudo-Laplacian Contrast [26.28414569796961]
  We propose a novel Pseudo Laplacian Contrast (PLC) tensor decomposition framework. It integrates the data augmentation and cross-view Laplacian to enable the extraction of class-aware representations. Experiments on various datasets demonstrate the effectiveness of our approach.
  arXiv  Detail & Related papers  (2024-09-23T16:48:13Z)
• With or Without Replacement? Improving Confidence in Fourier Imaging [5.542462410129539]
  We show how a transition between sampling with and without replacement can lead to a weighted reconstruction scheme with improved performance for the standard LASSO. In this paper, we illustrate how this reweighted sampling idea can also improve the debiased estimator.
  arXiv  Detail & Related papers  (2024-07-18T15:15:19Z)
• Sampling from Gaussian Process Posteriors using Stochastic Gradient Descent [43.097493761380186]
  gradient algorithms are an efficient method of approximately solving linear systems. We show that gradient descent produces accurate predictions, even in cases where it does not converge quickly to the optimum. Experimentally, gradient descent achieves state-of-the-art performance on sufficiently large-scale or ill-conditioned regression tasks.
  arXiv  Detail & Related papers  (2023-06-20T15:07:37Z)
• Design of Compressed Sensing Systems via Density-Evolution Framework for Structure Recovery in Graphical Models [10.667885727418705]
  It has been shown that learning the structure of Bayesian networks from observational data is an NP-Hard problem. We propose a novel density-evolution based framework for optimizing compressed linear measurement systems. We show that the structure of GBN can indeed be recovered from resulting compressed measurements.
  arXiv  Detail & Related papers  (2022-03-17T22:16:38Z)
• A Model for Multi-View Residual Covariances based on Perspective Deformation [88.21738020902411]
  We derive a model for the covariance of the visual residuals in multi-view SfM, odometry and SLAM setups. We validate our model with synthetic and real data and integrate it into photometric and feature-based Bundle Adjustment.
  arXiv  Detail & Related papers  (2022-02-01T21:21:56Z)
• Fast Scalable Image Restoration using Total Variation Priors and Expectation Propagation [7.7731951589289565]
  This paper presents a scalable approximate Bayesian method for image restoration using total variation (TV) priors. We use the expectation propagation (EP) framework to approximate minimum mean squared error (MMSE) estimators and marginal (pixel-wise) variances.
  arXiv  Detail & Related papers  (2021-10-04T17:28:41Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sampling (AIS) and related algorithms are highly effective tools for marginal likelihood estimation. Differentiability is a desirable property as it would admit the possibility of optimizing marginal likelihood as an objective. We propose a differentiable algorithm by abandoning Metropolis-Hastings steps, which further unlocks mini-batch computation.
  arXiv  Detail & Related papers  (2021-07-21T17:10:14Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  We propose a simple and efficient unsupervised feature selection method, by combining reconstruction error with $l_2,p$-norm regularization. We present an efficient optimization algorithm to solve the proposed unsupervised model, and analyse the convergence and computational complexity of the algorithm theoretically.
  arXiv  Detail & Related papers  (2020-12-29T04:08:38Z)

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.