CS Paper Radar

Phase Transition in Binary Compressed Sensing via Annealing with Adaptive Regularization

Xiaoxin Huang, Masayuki Ohzeki

cs.IT quant-ph ·submitted 2026-09-15 06:35 UTC · v1
published

Abstract

Regularization choice changes the recovery phase diagrams of annealing-based binary compressed sensing. We develop a regularization-selection method that combines systematic parameter search with random forest regression. Under noiseless Gaussian measurements with known sparsity, reference parameters are selected from a candidate grid by minimizing mean squared reconstruction error over repeated simulated annealing (SA) trials. The fitted model predicts these reference values from signal dimension, sampling ratio, and sparsity. With predicted regularization, the SA recovery transition broadly follows the asymptotic reference boundary for box-constrained $\ell_1$ recovery at the larger signal dimensions examined. Without retraining, the same predictor supplies identical regularization values to SA and a quantum--classical hybrid solver. On matched problem instances, the hybrid solver yields smaller mean squared reconstruction errors than SA in parts of the evaluated parameter space. The resulting rule reuses the searched information for subsequent reconstruction without repeating candidate searches at each setting. The results quantify empirical performance under the stated finite candidate grid and solver settings; they do not constitute a solver-independent recovery guarantee or a time-to-solution comparison.

Comment
8 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Instance Optimal Sparse Recovery from Nonlinear Observations: A Unified Framework

cs.IT eess.SPmath.ST ·2026-09-02 ·Junren Chen, Arian Maleki
similarity 0.60
Abstract

This paper develops a unified framework for instance optimal sparse recovery from nonlinear observations. The main ingredient is a signal-dependent restricted approximate invertibility condition (RAIC) of some gradient, which leads to the instance optimality of iterative hard thresholding. Under Gaussian designs, we apply the proposed framework to phaseless, one-bit, and ReLU measurements, which correspond to the problems of sparse phase retrieval, one-bit compressed sensing, and sparse ReLU regression, respectively. For sparse phase retrieval, we propose a variant of thresholded amplitude flow and show its instance optimality under $O(s^3)$ measurements (up to logarithmic factors), where $s$ is the sparsity level. To our best knowledge, this is the first instance optimal efficient algorithm for sparse phase retrieval and complements Gao, Wang and Xu (2016) that achieved this via a computationally intractable program. In one-bit compressed sensing, we establish the instance optimality of normalized binary iterative hard thresholding and strengthen the recent result of Matsumoto and Mazumdar (2024). In sparse ReLU regression, it is shown that a slight variant of the algorithm in Soltanolkotabi (2017) is instance optimal. Moreover, $(\ell_2,\ell_2)$ non-uniform instance optimal guarantees are obtained for these problems. The analysis is built upon a number of high-dimensional concentration bounds, including bounds on restricted eigenvalues and a novel instance-dependent hyperplane tessellation result.

0.51

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.57
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.23

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.57
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

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.57
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 Generalized Twin Image: Understanding Regularized Phase Retrieval

eess.IV physics.optics ·2026-10-30 ·Zhiyuan Hu, Michael Unser, Jonathan Dong
similarity 0.56
Abstract

Image priors can dramatically improve phase retrieval reconstruction, but their effectiveness strongly varies between imaging modalities. We introduce the generalized twin image, which extends the classical twin-image ambiguity from Fourier phase retrieval to any invertible sensing operator, to understand this effectiveness. The ambiguity extends to undersampled and oversampled measurements, remaining exact under undersampling and for oversampled coded Fourier measurements. We show that it provides a simple criterion to assess regularization effectiveness: the image prior should favor the ground truth over its generalized twin image. We propose the total-variation ratio as a simple measure of this preference, and derive closed-form estimates for structured random phase retrieval models. Experiments with a pretrained denoiser demonstrate that the ratio predicts regularized reconstruction performance across different sensing models.

0.30

Seeing Through Sparse Signals: CS-Enhanced Sensing With QoS Guarantees for 6G ISAC

eess.SP ·2026-10-15 ·Yifei Wang, Pradyumna Kumar Bishoyi, Marina Petrova
similarity 0.56
Abstract

In integrated sensing and communication (ISAC) systems, communication and sensing share time-frequency resources, creating a fundamental trade-off between communication quality of service (QoS) and quality of sensing (QoSe). Reusing 5G new radio (NR) reference signals (RSs) enables standard-compliant sensing, but their inherent sparsity leads to undersampled channels and strong sidelobes that degrade weak-target detection. Compressed sensing (CS) can mitigate these effects, yet existing methods either overlook communication QoS constraints or rely on reconstruction algorithms that are step-size-sensitive or employ global thresholding, leading to weak-target masking in multi-target scenarios. The multi-target detection problem, therefore, requires a joint design of resource scheduling and CS-based reconstruction. In this work, we investigate the impact of two scheduling schemes, namely QoS-guaranteed scheduling and proportional-fairness (PF)-based scheduling, on the sensing-communication trade-off. To further enhance sensing performance, we employ a 2D max-median complex approximate message passing (2D-mmCAMP) algorithm that performs adaptive row- and column-wise thresholding to suppress sidelobes while preserving weak-target responses in multi-target scenarios. Simulations demonstrate an improvement of >= 16% in weak-target detection over baseline reconstruction algorithms while meeting downlink (DL) QoS constraints, validating the effectiveness of the proposed NR-compliant ISAC scheme.

0.20

RMSampler: Sparse Radio Map Reconstruction with Active Sampling and Diffusion Posterior Correction

eess.SP ·2026-10-20 ·Nan Cheng, Xiucheng Wang
similarity 0.55
Abstract

Reconstructing a radio map (RM) from sparse received-power measurements supports non-cooperative interference monitoring and spectrum management. However,sparse measurements leave uncertainty about both the global RM and the interfering emitter location, making informative sampling and accurate reconstruction challenging. To address these challenges, a novel joint sampling and reconstruction method named RMSampler is proposed in this paper to improve measurement selection and RM reconstruction under limited measurement budgets. For measurement selection, RMSampler evaluates global RM error reduction using the covariance of diffusion-generated RMs and localization error reduction using candidate emitter locations. Because these errors have different units, their expected relative reductions are combined into a scale-invariant sampling criterion, with each acquired measurement updating both uncertainty estimates. After sampling, the updated emitter-location probabilities guide a separate conditional diffusion ensemble for final reconstruction. To improve measurement agreement, an effective sample size (ESS) target guides robust posterior correction, followed by a minimum-distortion projection enforcing measurement and building constraints. For the reconstruction ensemble, analysis establishes that increasing likelihood power reduces expected robust measurement loss, while pretrained neural parameters and architecture remain unchanged. Experiments using simulated and real-world measured data demonstrate improved reconstruction under matched measurement budgets. In the Chongqing real-world measured data experiment, root mean square error (RMSE) decreases from 3.54 to 2.73~dB relative to random sampling under a common reconstruction method.

0.39

Compressive Sensing - Introduction and Relations to Deep Learning

cs.IT ·2026-08-25 ·Hung-Hsu Chou, Johannes Maly, Holger Rauhut
similarity 0.54
Abstract

Compressive sensing predicts that sparse vectors (signals) can be recovered from a small number of linear measurements via efficient algorithms. This finding, which dates back two decades, has triggered a paradigm shift in signal processing and initiated many developments both in practical signal-processing applications, such as medical imaging, radar, and astronomy, and on the theoretical side. More recently, seminal connections to the field of deep learning have led to further advances in the field, such as the use of unrolled neural networks for sparse recovery and the discovery that common training algorithms (variants of gradient descent) favor sparsity in overparameterized scenarios -- the so-called implicit bias phenomenon. This article gives an introduction to compressive sensing and outlines connections to deep learning. In particular, we will discuss generalization for neural networks generated by unrolling sparse recovery algorithms and implicit regularization for gradient descent applied to learning simplified linear neural networks.

0.06