Partially deterministic sampling for compressed sensing with denoising guarantees

• URL: http://arxiv.org/abs/2604.04802v1
• Date: Mon, 06 Apr 2026 16:07:49 GMT
• Title: Partially deterministic sampling for compressed sensing with denoising guarantees
• Abstract summary: We study compressed sensing when the sampling vectors are chosen from the rows of a unitary matrix.<n>We derive an optimized sampling scheme for Bernoulli selectors which naturally combines random and deterministic selection of rows.
• Score: 1.9116784879310027
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study compressed sensing when the sampling vectors are chosen from the rows of a unitary matrix. In the literature, these sampling vectors are typically chosen randomly; the use of randomness has enabled major empirical and theoretical advances in the field. However, in practice there are often certain crucial sampling vectors, in which case practitioners will depart from the theory and sample such rows deterministically. In this work, we derive an optimized sampling scheme for Bernoulli selectors which naturally combines random and deterministic selection of rows, thus rigorously deciding which rows should be sampled deterministically. This sampling scheme provides measurable improvements in image compressed sensing for both generative and sparse priors when compared to with-replacement and without-replacement sampling schemes, as we show with theoretical results and numerical experiments. Additionally, our theoretical guarantees feature improved sample complexity bounds compared to previous works, and novel denoising guarantees in this setting.

Related papers

• Amortized Bandwidth Learning for Kernel Density Estimation under Logarithmic Score [0.0]
  An amortized framework is proposed that learns mapping across a distribution of density-estimation tasks by optimizing the logarithmic score.<n>Experiments under Gaussian sampling, a multi-family benchmark, and randomized Gaussian-mixture training show that the amortized selector consistently and substantially outperforms Silverman's rule.
  arXiv  Detail & Related papers  (2026-08-20T15:56:59Z)
• How Sampling Shapes LLM Alignment: From One-Shot Optima to Iterative Dynamics [65.67654005892469]
  We show that proper instance-dependent sampling can yield stronger ranking guarantees, while skewed on-policy sampling can induce excessive concentration under structured preferences.<n>We then analyze iterative alignment dynamics in which the learned policy feeds back into future sampling and reference policies.<n>Our theoretical insights extend to Direct Preference Optimization, indicating the phenomena we captured are common to a broader class of preference-alignment methods.
  arXiv  Detail & Related papers  (2026-02-12T17:11:08Z)
• Revisiting Randomization in Greedy Model Search [16.15551706774035]
  We propose and analyze an ensemble of greedy forward selection estimators that are randomized by feature subsampling.<n>We design a novel implementation based on dynamic programming that greatly improves its computational efficiency.<n>Contrary to prevailing belief that randomized ensembling is analogous to shrinkage, we show that it can simultaneously reduce training error and degrees of freedom.
  arXiv  Detail & Related papers  (2025-06-18T17:13:53Z)
• Denoising guarantees for optimized sampling schemes in compressed sensing [3.624865764637671]
  We provide theoretical guarantees showing that the error caused by the measurement noise vanishes with an increasing number of measurements.<n>All our results hold on prior sets contained in a union of low-dimensional subspaces.
  arXiv  Detail & Related papers  (2025-04-01T02:04:03Z)
• Gaussian Processes Sampling with Sparse Grids under Additive Schwarz Preconditioner [6.408773096179187]
  We propose a scalable algorithm for sampling random realizations of the prior and posterior of GP models. The proposed algorithm leverages inducing points approximation with sparse grids, as well as additive Schwarz preconditioners.
  arXiv  Detail & Related papers  (2024-08-01T00:19:36Z)
• Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers [143.6249073384419]
  In this paper, we propose a distributed sampling scheme based on the alternating direction method of multipliers. We provide both theoretical guarantees of our algorithm's convergence and experimental evidence of its superiority to the state-of-the-art. In simulation, we deploy our algorithm on linear and logistic regression tasks and illustrate its fast convergence compared to existing gradient-based methods.
  arXiv  Detail & Related papers  (2024-01-29T02:08:40Z)
• Refined bounds for randomized experimental design [7.899055512130904]
  Experimental design is an approach for selecting samples among a given set so as to obtain the best estimator for a given criterion. We propose theoretical guarantees for randomized strategies on E and G-optimal design.
  arXiv  Detail & Related papers  (2020-12-22T20:37:57Z)
• Pathwise Conditioning of Gaussian Processes [72.61885354624604]
  Conventional approaches for simulating Gaussian process posteriors view samples as draws from marginal distributions of process values at finite sets of input locations. This distribution-centric characterization leads to generative strategies that scale cubically in the size of the desired random vector. We show how this pathwise interpretation of conditioning gives rise to a general family of approximations that lend themselves to efficiently sampling Gaussian process posteriors.
  arXiv  Detail & Related papers  (2020-11-08T17:09:37Z)
• Robust Sampling in Deep Learning [62.997667081978825]
  Deep learning requires regularization mechanisms to reduce overfitting and improve generalization. We address this problem by a new regularization method based on distributional robust optimization. During the training, the selection of samples is done according to their accuracy in such a way that the worst performed samples are the ones that contribute the most in the optimization.
  arXiv  Detail & Related papers  (2020-06-04T09:46:52Z)
• Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
  We give the first relative-error algorithms for column subset selection, subspace approximation, projective clustering, and volume on turnstile streams that use space sublinear in $n$. Our adaptive sampling procedure has a number of applications to various data summarization problems that either improve state-of-the-art or have only been previously studied in the more relaxed row-arrival model.
  arXiv  Detail & Related papers  (2020-04-23T05:00:21Z)
• Efficiently Sampling Functions from Gaussian Process Posteriors [76.94808614373609]
  We propose an easy-to-use and general-purpose approach for fast posterior sampling. We demonstrate how decoupled sample paths accurately represent Gaussian process posteriors at a fraction of the usual cost.
  arXiv  Detail & Related papers  (2020-02-21T14:03:16Z)

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.