Denoising guarantees for optimized sampling schemes in compressed sensing

• URL: http://arxiv.org/abs/2504.01046v1
• Date: Tue, 01 Apr 2025 02:04:03 GMT
• Title: Denoising guarantees for optimized sampling schemes in compressed sensing
• Authors: Yaniv Plan, Matthew S. Scott, Xia Sheng, Ozgur Yilmaz,
• Abstract summary: 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.
• Score: 3.624865764637671
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Compressed sensing with subsampled unitary matrices benefits from \emph{optimized} sampling schemes, which feature improved theoretical guarantees and empirical performance relative to uniform subsampling. We provide, in a first of its kind in compressed sensing, theoretical guarantees showing that the error caused by the measurement noise vanishes with an increasing number of measurements for optimized sampling schemes, assuming that the noise is Gaussian. We moreover provide similar guarantees for measurements sampled with-replacement with arbitrary probability weights. All our results hold on prior sets contained in a union of low-dimensional subspaces. Finally, we demonstrate that this denoising behavior appears in empirical experiments with a rate that closely matches our theoretical guarantees when the prior set is the range of a generative ReLU neural network and when it is the set of sparse vectors.

Related papers

• Unrolled denoising networks provably learn optimal Bayesian inference [54.79172096306631]
  We prove the first rigorous learning guarantees for neural networks based on unrolling approximate message passing (AMP) For compressed sensing, we prove that when trained on data drawn from a product prior, the layers of the network converge to the same denoisers used in Bayes AMP.
  arXiv  Detail & Related papers  (2024-09-19T17:56:16Z)
• Risk-Sensitive Diffusion: Robustly Optimizing Diffusion Models with Noisy Samples [58.68233326265417]
  Non-image data are prevalent in real applications and tend to be noisy. Risk-sensitive SDE is a type of differential equation (SDE) parameterized by the risk vector. We conduct systematic studies for both Gaussian and non-Gaussian noise distributions.
  arXiv  Detail & Related papers  (2024-02-03T08:41:51Z)
• Fast Semisupervised Unmixing Using Nonconvex Optimization [80.11512905623417]
  We introduce a novel convex convex model for semi/library-based unmixing. We demonstrate the efficacy of Alternating Methods of sparse unsupervised unmixing.
  arXiv  Detail & Related papers  (2024-01-23T10:07:41Z)
• Geometry of Sensitivity: Twice Sampling and Hybrid Clipping in Differential Privacy with Optimal Gaussian Noise and Application to Deep Learning [18.92302645198466]
  We study the problem of the construction of optimal randomization in Differential Privacy. Finding the minimal perturbation for properly-selected sensitivity sets is a central problem in DP research.
  arXiv  Detail & Related papers  (2023-09-06T02:45:08Z)
• Learning Rate Free Sampling in Constrained Domains [21.853333421463603]
  We introduce a suite of new particle-based algorithms for sampling in constrained domains which are entirely learning rate free. We demonstrate the performance of our algorithms on a range of numerical examples, including sampling from targets on the simplex.
  arXiv  Detail & Related papers  (2023-05-24T09:31:18Z)
• Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors [59.33977545294148]
  We show that $O(k log L)$ samples suffice to guarantee that the signal is close to any vector that minimizes an amplitude-based empirical loss function. We adapt this result to sparse phase retrieval, and show that $O(s log n)$ samples are sufficient for a similar guarantee when the underlying signal is $s$-sparse and $n$-dimensional.
  arXiv  Detail & Related papers  (2021-06-29T12:49:54Z)
• Square Root Principal Component Pursuit: Tuning-Free Noisy Robust Matrix Recovery [8.581512812219737]
  We propose a new framework for low-rank matrix recovery from observations corrupted with noise and outliers. Inspired by the square root Lasso, this new formulation does not require prior knowledge of the noise level. We show that a single, universal choice of the regularization parameter suffices to achieve reconstruction error proportional to the (a priori unknown) noise level.
  arXiv  Detail & Related papers  (2021-06-17T02:28:11Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  It is essential to theoretically guarantee that algorithms provide small objective residual with high probability. Existing methods for non-smooth convex optimization have complexity bounds with dependence on confidence level. We propose novel stepsize rules for two methods with gradient clipping.
  arXiv  Detail & Related papers  (2021-06-10T17:54:21Z)
• SNIPS: Solving Noisy Inverse Problems Stochastically [25.567566997688044]
  We introduce a novel algorithm dubbed SNIPS, which draws samples from the posterior distribution of any linear inverse problem. Our solution incorporates ideas from Langevin dynamics and Newton's method, and exploits a pre-trained minimum mean squared error (MMSE) We show that the samples produced are sharp, detailed and consistent with the given measurements, and their diversity exposes the inherent uncertainty in the inverse problem being solved.
  arXiv  Detail & Related papers  (2021-05-31T13:33:21Z)
• Sampling-free Variational Inference for Neural Networks with Multiplicative Activation Noise [51.080620762639434]
  We propose a more efficient parameterization of the posterior approximation for sampling-free variational inference. Our approach yields competitive results for standard regression problems and scales well to large-scale image classification tasks.
  arXiv  Detail & Related papers  (2021-03-15T16:16:18Z)
• Reconstruction of Sparse Signals under Gaussian Noise and Saturation [1.9873949136858349]
  Most compressed sensing algorithms do not account for the effect of saturation in noisy compressed measurements. We propose a new data fidelity function which is based on ensuring a certain form of consistency between the signal and the saturated measurements.
  arXiv  Detail & Related papers  (2021-02-08T03:01:46Z)
• Sample Complexity Bounds for 1-bit Compressive Sensing and Binary Stable Embeddings with Generative Priors [52.06292503723978]
  Motivated by advances in compressive sensing with generative models, we study the problem of 1-bit compressive sensing with generative models. We first consider noiseless 1-bit measurements, and provide sample complexity bounds for approximate recovery under i.i.d.Gaussian measurements. We demonstrate that the Binary $epsilon$-Stable Embedding property, which characterizes the robustness of the reconstruction to measurement errors and noise, also holds for 1-bit compressive sensing with Lipschitz continuous generative models.
  arXiv  Detail & Related papers  (2020-02-05T09:44:10Z)

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.