# Partially deterministic sampling for compressed sensing with denoising guarantees

arXiv: https://arxiv.org/abs/2604.04802 · HTML: https://mlsanity.com/paper/2604.04802/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 19 references that are in the map.
- First posted on arXiv 6 Apr 2026.

## Builds on (most cited first, 6 of 6)

- [Deep Learning Face Attributes in the Wild](https://mlsanity.com/paper/1411.7766/) (2014)
- [CS4ML: A general framework for active learning with arbitrary data based on Christoffel functions](https://mlsanity.com/paper/2306.00945/) (2023)
- [A coherence parameter characterizing generative compressed sensing with Fourier measurements](https://mlsanity.com/paper/2207.09340/) (2022)
- [Model-adapted Fourier sampling for generative compressed sensing](https://mlsanity.com/paper/2310.04984/) (2023)
- [A unified framework for learning with nonlinear model classes from arbitrary linear samples](https://mlsanity.com/paper/2311.14886/) (2023)
- [Denoising guarantees for optimized sampling schemes in compressed sensing](https://mlsanity.com/paper/2504.01046/) (2025)

## Abstract (arXiv)

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.