CS Paper Radar

Full-Model Optimality for Tunable Linear Generative Priors in Compressed Sensing

Zhaoming Li, Paul Hand

cs.LG stat.ML ·submitted 2026-09-02 16:22 UTC · v1
theory

Abstract

Generative models have been studied experimentally and theoretically as priors for inverse problems such as compressed sensing. Recent work by Gunn et al. studied the use of generative priors with tunable complexity, where a family of generative priors with varying complexity is maintained and a specific complexity can be selected at inversion time. They demonstrated that lower reconstruction errors can be experimentally attained for a variety of inverse problems by appropriately tuning the complexity of the generative prior. In the present paper, we establish theory for compressed sensing in the setting of a tunable family of linear generative priors naturally related through their singular value decompositions. We prove that in noiseless Gaussian compressed sensing, the full-dimensional linear prior attains the minimum expected reconstruction error over the entire family of linear priors. Thus, in this idealized linear noiseless setting, tuning to a lower-complexity prior does not improve the expected reconstruction error. This result is in contract to the behavior of denoising, where lower complexity priors attain lower reconstruction errors due to a standard bias-variance tradeoff. This result indicates that the experimental benefits of tunability in compressed sensing with neural network priors arises due to nonlinearities in the generative models.

Comment
32 pages 3 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Diffusion Models are Provably Efficient Priors for Sparse Recovery

cs.IT stat.MLcs.LGmath.OC ·2026-11-18 ·Ivan Lee, Xingyu Xu, Yuejie Chi
similarity 0.77
Abstract

Diffusion models have transformed generative modeling through their ability to capture and generate samples from complex data distributions. This success has spurred substantial interest in using pretrained diffusion models as expressive priors for highly ill-posed inverse problems in imaging and sensing. Despite strong empirical performance, theoretical understanding of this approach remains limited: existing guarantees are often asymptotic or entail prohibitive computational costs in the worst case. In this paper, we address this gap by studying sparse recovery from a small number of linear measurements, a classical problem in compressed sensing. We show that, given an accurate diffusion model capturing a sparsity-promoting Bernoulli-Gaussian prior, a likelihood-guided annealed Langevin sampler provably recovers the sparse signal in polynomial time with near-optimal sample complexity for a broad family of random and deterministic sensing matrices. When the signal is indeed drawn from the postulated prior, we further establish total variation guarantees for posterior sampling after a final denoising step. These results lay a theoretical foundation for statistically and computationally efficient inverse solvers with diffusion priors.

0.14

Recovery Guarantees for Posterior Sampling of One-Bit Compressed Sensing

cs.LG cs.IT ·2026-10-08 ·Jing Ma, Yujia Wu, Zhaoqiang Liu
top venuetheory similarity 0.72
Abstract · Accepted to NeurIPS 2026

We study the sample complexity of noisy one-bit compressed sensing for signals drawn from a prior distribution. By characterizing the effective distributional complexity of the prior via its approximate covering number, we prove that posterior sampling achieves accurate recovery with high probability when the number of measurements scales with the logarithm of the approximate covering number, up to a one-bit separation gap factor. This upper bound is robust to learned prior mismatch. Specifically, we show that posterior sampling with an approximate prior remains reliable, provided that the learned prior distribution is sufficiently close to the true signal distribution in Wasserstein distance. In addition, we establish a sample complexity lower bound for any reliable method of noisy one-bit compressed sensing, showing that our upper bound is nearly matched in its main prior dependent term. To approximate the ideal posterior sampling process for real world scenarios, we instantiate posterior sampling through a plug-and-play algorithm with diffusion priors. Experiments on the FFHQ and ImageNet datasets demonstrate the effectiveness of our proposed approach.

0.41

Principled MAP estimation for inverse problems: bridging the gap between convergence and performance

cs.CV cs.LG ·2026-09-29 ·Alexandre Lagier, Valentine Tosel, Anne Gagneux, Mathurin Massias, Ségolène Martin
theory similarity 0.66
Abstract

Pretrained denoisers provide a powerful way to incorporate image priors into restoration algorithms. Plug-and-Play and RED approaches exploit fixed-noise-level denoisers within first-order optimization schemes, with convergence guarantees, but often struggle to achieve high-quality reconstruction on severely ill-posed inverse problems. In contrast, recent state-of-the-art approaches leverage denoisers derived from flow- or diffusion-based generative models and evaluate them along a sequence of decreasing noise levels. While these methods achieve strong empirical performance, their convergence theory remains limited. In this paper, we bridge this gap by specifically designing an algorithm that combines denoisers at decreasing noise levels with a schedule tailored to ensure convergence. From a Bayesian perspective, we prove that our method converges to a $\textit{Maximum a Posteriori}$ (MAP) estimate, under suitable assumptions. Subsequently, we apply our method to various ill-posed inverse problems and show that it surpasses convergent methods while competing with state-of-the-art empirical ones.

0.17

Exact signal recovery from generative priors with sigmoid output activation

cs.IT eess.SPstat.ML ·2026-11-03 ·Matthew S. Scott, Yaniv Plan, Özgür Yılmaz
similarity 0.64
Abstract · 9 pages

We show exact signal recovery in generative compressed sensing for feedforward neural networks with piecewise-linear activations and a final sigmoid activation, with no assumption of expansivity. Consider a ReLU network of depth $d$ with a sigmoid final activation, whose input layer, of dimension $k$, is the narrowest, and let $K$ be the geometric mean of the widths of its layers. We show that, with high probability, all signals of the range whose entries lie in $[δ, 1 - δ]$ are uniformly recovered from $m \gtrsim k(d \log(K/k) + \log(1+\log(1/δ)))$ measurements.

0.24

Superfast Spectral Compressed Sensing with Quadratic Convergence

cs.IT eess.SPmath.NA ·2026-10-15 ·Xunmeng Wu, Jian-Feng Cai, Zongben Xu, Zai Yang
similarity 0.63
Abstract

In this paper, we study the spectral compressed sensing problem of recovering a spectrally sparse signal from linear compressive measurements. Exploiting the low-rank Hankel structure associated with the signal, we formulate a nonconvex fixed-rank optimization problem with a Hankel regularization. We propose a Superfast Iterative Hard Thresholding (SIHT) algorithm, where each iteration consists of a tangent-space least-squares update followed by a fixed-rank hard thresholding projection. SIHT is the first nonconvex algorithm with provable quadratic convergence for spectral compressed sensing. For random Gaussian measurements, it achieves exact recovery in the noiseless case and stable recovery in the noisy case with near-optimal sample complexity. To efficiently implement SIHT, we develop a parameterized conjugate gradient method for solving the least-squares subproblem, endowing SIHT with state-of-the-art computational and memory efficiency. Numerical experiments are provided to validate our results.

0.13

Lifted Restricted Isometry Property and Fast Algorithm for Spectral Compressed Sensing With Near-Optimal Sample Complexity

eess.SP math.OC ·2026-10-13 ·Xunmeng Wu, Jian-Feng Cai, Zongben Xu, Zai Yang
similarity 0.59
Abstract

This paper studies the spectral compressed sensing problem, which aims to recover an $r$-spectrally-sparse signal of length $N$ from linear compressive measurements. We reformulate the problem as the recovery of a low-rank Hankel matrix. Motivated by this formulation, we propose a Lifted Restricted Isometry Property (LRIP) for the measurement matrix and show that Gaussian measurement matrices satisfy LRIP under certain conditions. Unlike classical RIP, LRIP imposes a rank constraint in the lifted matrix domain while taking measurements in the signal domain through the adjoint Hankel operator. To solve the resulting nonconvex problem efficiently, we introduce a Fast Iterative Hard Thresholding (FIHT) algorithm. Based on LRIP, we show that FIHT converges linearly to the true signal with high probability using $\mathcal{O}(r \ln r \ln^2 N)$ scaled Gaussian measurements, which is near-optimal up to log factors and improves the state-of-the-art order of $r^2$ for nonconvex Hankel methods. Extensive numerical results demonstrate the superiority of FIHT as compared to state-of-the-art convex methods in terms of phase transitions, computational time, and robustness to noise.

0.40

Computational compressive imaging reconstruction with a simulated-annealing-based Ising solver

cs.CV physics.opticscs.DCmath-ph+1 ·2026-10-14 ·Ze Zheng, Xiaoyan Wu, Hang Xu, Jingzheng Huang, Tailong Xiao +1 more
similarity 0.59
Abstract · 15 pages, 6 figures

Computational compressive imaging, such as single-pixel imaging and lensless imaging, is a promising imaging technique, enabling the reconstruction of objects from under-sampled measurements through compressed sensing algorithms or deep learning methods. However, the demand for electronic computational resources grows rapidly when recovering high-resolution and multi-dimensional images and training neural networks with numerous parameters, which has become a bottleneck for the widespread adoption of this technique. Here, we propose a physics-driven reconstruction framework that formulates imaging inverse problems as Ising models and directly recovers target objects through the self-evolution of non-von Neumann Ising machines toward the ground state of the Hamiltonian. We employ a simulated-annealing-based Ising solver to demonstrate this proof-of-concept by reconstructing objects in both single-pixel imaging and a lensless diffuser camera at sampling rates ranging from 1% to 25%. By further incorporating a foreground-sparsity constraint and a smoothness constraint, the reconstruction quality of our method is comparable to or even better than that of mainstream algorithms. This approach has the potential to substantially reduce the electronic computational burden of inverse reconstruction, paving the way for real-time, low-power computational imaging.

0.22

The Prior-Force Family of Implicit Denoiser Priors and Its Decisions in Linear Inverse Problems

cs.LG stat.MLmath.OC ·2026-10-30 ·Weijie Liang, Chuling Wen, Jian Lu
similarity 0.58
Abstract · 49 pages, 4 figures, 5 tables

Implicit priors given by Gaussian denoisers successfully regularize a wide range of inverse problems in approaches such as plug-and-play (PnP), regularization by denoising (RED) and score-based methods. Such a prior depends on the noise level, and how it selects among signals consistent with the data remains largely uncharacterized. To put implicit and explicit priors on the same footing, we define the prior-force family $W_t=t^{-1}(D_t^{-1}-I)$ of any Gaussian denoiser $D_t$ at noise variance $t>0$ (inverse in the graph sense), the normalized denoising residual as an operator on clean signals. At a common effective prior weight, the equilibrium equations differ only in their prior terms: PnP uses $W_t$, RED/score-based methods the score force (the normalized residual as an operator on noisy inputs), and maximum a posteriori (MAP) estimation the MAP force (the negative log-prior gradient). For the minimum mean-square error (MMSE) denoisers of a prior $π$, we compare the corresponding energies at three levels. Without observation, raising the noise level favors PnP minima that retain more posterior variance. On signals consistent with the data, the leading-order PnP energy for separated modes is the proximal hull of the MAP energy, which lets PnP select signals between modes; modes of equal data fit are ranked by peak height at small noise levels and by mass at large ones. For recovery, $W_t$ at the truth bounds the local bias, and an oracle noise level balances this bias against denoiser error. These results show that the noise level is a parameter of the prior rather than a step size. Experiments with exact priors support these predictions, including the mixture components that PnP selects on unseen data.

0.25