CS Paper Radar

Compressive Sensing - Introduction and Relations to Deep Learning

Hung-Hsu Chou, Johannes Maly, Holger Rauhut

cs.IT ·submitted 2026-08-25 08:19 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

PE-CSNet: An equivariant network architecture with learnable patch-based sparse representation

cs.CV ·2026-08-11 ·Kai Li, Haitao Long, Bo Zhang, Haiwen Zhang, Zhi Zhou
similarity 0.74
Abstract · 35 pages, 10 figures. Under review

Compressive sensing (CS) enables accurate signal reconstruction from sparse measurements and is widely applied in medical imaging, remote sensing, and image compression. However, designing an effective, task-specific sparse transform and the corresponding optimization procedure for high-quality CS remains challenging. This process typically requires expert domain knowledge and laborious parameter tuning. To address this issue, we present a Patch-based Equivariant deep unrolling architecture, termed PE-CSNet, for accurate CS recovery. While traditional CS methods generally use predefined patch-based transform sparsity, we generalize this idea by incorporating learnable transform sparsity that adapts to the specific CS task through an optimization-driven process. Specifically, we first establish a generalized patch-based CS model, which we solve via a block coordinate descent (BCD) algorithm. The BCD solver is then unrolled into a deep neural network, where all parameters of both the CS model and solver are learned through end-to-end training. To improve data efficiency, we introduce a stochastic equivariant training strategy that exploits the patch-wise structure of the network, enabling PE-CSNet to learn effectively even from limited data. We further provide a simpler, parameter-shared version of PE-CSNet and briefly discuss its convergence as an iterative solver. For practical applications, the network uses stage-specific (non-shared) parameters to enhance its expressive power and thereby improve its performance. On the tasks of CS magnetic resonance imaging (CS-MRI) and CS coded diffraction patterns (CS-CDP), PE-CSNet achieves state-of-the-art accuracy with fast computational speed, outperforming traditional methods and existing deep unrolling methods.

0.12

Newton Deep Unfolding for Compressed Sensing

cs.CV ·2026-09-13 ·Changhua He, Xianchao Xiu
code/data similarity 0.66
Abstract

Compressed sensing (CS) reconstructs images from highly limited measurements, but existing deep unfolding methods are typically driven by first-order optimization and weakly exploit the optimization states generated during reconstruction. To address these limitations, we propose a Newton deep unfolding network (NDU-Net), which, to the best of our knowledge, is the first deep unfolding framework that leverages second-order optimization for CS reconstruction. Specifically, NDU-Net introduces a Newton update (NU) module to estimate Newton-type update directions and generate optimization states that characterize the current reconstruction process. Furthermore, a Newton-guided multi-scale prior (MP) module is designed to incorporate these optimization states into multi-scale feature restoration, thereby enabling the learned prior to adapt to the current reconstruction stage. Experimental results under different CS ratios confirm that our proposed NDU-Net achieves promising reconstruction performance and exhibits enhanced robustness. Our code is available at https://github.com/xianchaoxiu/DNU-Net.

0.30

Implicit Bias of (Stochastic) Gradient Descent on Deep Linear Diagonal Networks

cs.LG math.OC ·2026-10-29 ·Wiebke Bartolomaeus, Holger Rauhut
similarity 0.66
Abstract · 38 pages, 14 figures

Modern machine learning models are often overparameterized, i.e., have more parameters than training data. This typically implies that the loss function admits multiple minimizers so that training methods (and their hyperparameter choices) have significant influence on the computed solution. We study this so-called implicit bias phenomenon in the context of training deep linear diagonal networks. Previous work has shown that the gradient flow for learning such networks converges to (almost) sparse solutions when initialized small. For an arbitrary number of layers, we extend this analysis to the practically more realistic (stochastic) gradient descent iterations. Our approach identifies (stochastic) gradient descent as a perturbed (stochastic) mirror gradient descent. This allows us to establish convergence and characterize the limiting solution, relating it to weighted $\ell_1$-minimization. Moreover, we provide sufficient conditions on the step sizes and quantify the influence of the step sizes on the implicit bias.

0.39

Grokking through the Lens of Minimum-Norm Interpolation

cs.LG math.STstat.ML ·2026-09-29 ·Gil Kur, Ileana Rugina, Clémentine Carla Juliette Dominé, Marco Mondelli
theory similarity 0.65
Abstract · Submitted

Grokking shows that fitting the training data and learning the underlying signal can occur at very different stages. However, existing theories offer limited quantitative insight into how this delayed generalization depends on inductive bias and signal structure. Our work addresses the gap by developing a statistical theory that characterizes how regularization geometry and signal sparsity govern generalization near interpolation. In particular, we focus on the prototypical setting of high-dimensional regression and identify regimes in which sparsity-promoting regularization makes exact interpolation much more accurate than approximate fitting. In strongly overparameterized noiseless problems, we prove a zero--one generalization law and construct a family of convex norms whose interpolators transition from the trivial risk of the all-zero predictor to exact recovery, while keeping the training error equal to $0$. Furthermore, when feature dimension and sample size are proportional, we provide a precise characterization of training and generalization errors along $\ell_r$-regularization paths. This in turn allows us to quantify the generalization gain that remains near interpolation: we show that this gain increases as the norm becomes more sparsity-promoting and as the target becomes sparser, with a sharp drop in generalization reached for noiseless data and $\ell_1$ regularization. Experiments on diagonal linear networks and transformers trained on modular arithmetic demonstrate the generality of our theoretical predictions. Finally, beyond grokking, our work reveals a statistical instability in minimum-norm interpolation: small perturbations in the regularization strength can lead to drastically different generalization, while preserving small training error.

0.21

Scaled-Gradient Hard Thresholding Algorithms for Sparse Signal Recovery

cs.IT ·2026-10-30 ·Nan Meng, Yun-Bin Zhao
similarity 0.65
Abstract

Thresholding methods provide a simple iterative framework for sparse signal recovery by combining a search direction with a thresholding operation. Gradient-based search directions are computationally efficient because they require only first-order information for the error metric. We incorporate componentwise gradient scaling into this framework by preserving large-magnitude components and attenuating the remaining components of the gradient of error metric. Combining this strategy with hard thresholding yields scaled-gradient hard thresholding (SGHT) and its pursuit variant SGHTP. Under suitable restricted isometry conditions, we establish recovery error bounds for both methods that account for measurement noise and deviations from exact sparsity. Numerical experiments indicate that SGHTP achieves recovery performance comparable to established pursuit methods on the tested ECG signals.

0.17

Event-driven signal reconstruction through neuromorphic compressive sensing

eess.SP ·2026-09-23 ·Zeru Fang, Yanzhen Liu, Geoffrey Ye
similarity 0.65
Abstract

Compressive sensing (CS) exploits intrinsic signal sparsity for efficient representation of high-dimensional data. However, conventional CS relies on fixed-length measurement representations and dense reconstruction operations, leaving communication and computational costs largely determined by system dimensions rather than signal sparsity. Here, we propose a neuromorphic CS framework centred on a spike-driven learned iterative shrinkage-thresholding algorithm (S-LISTA). By representing compressed measurements and reconstruction updates as sparse events, the framework links intrinsic signal sparsity to the spatiotemporal sparsity of spiking neural networks (SNNs), extending the benefits of sparsity across sensing, transmission and reconstruction. Communication and computational costs consequently depend on event activity, allowing sparse representations to translate into resource savings. Extensive experiments demonstrate substantial reductions in transmitted data volume and estimated reconstruction energy while maintaining competitive reconstruction and downstream task performance. The framework also exhibits robustness under challenging channel conditions. These findings establish neuromorphic CS as a promising paradigm for signal reconstruction in resource-constrained scenarios.

0.35

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

Statistical Benefits of Fine-Tuning from Pretrained Initialization in Diagonal Linear Networks

cs.LG stat.ML ·2026-09-28 ·Alexandre Declèves, Etienne Boursier, Nicolas Flammarion
similarity 0.63
Abstract

Adapting pretrained models to downstream tasks with limited data has become a central paradigm in modern deep learning. Yet, despite its widespread practical success, how fine-tuning leverages information from pretraining remains poorly understood theoretically. We study fine-tuning from pretrained weights through the lens of sparse linear regression and two-layer diagonal linear networks. In our setting, pretraining provides information through the support (and signs) of the initialization predictor, which may contain coordinates relevant to the downstream task. We show how pretrained information reshapes the implicit bias and training dynamics, and can thereby reduce the sample complexity of recovering the target parameters and support. In particular, for a clean initialization with correctly inherited signs, we show that the required sample size is comparable to that of a weighted Lasso estimator that explicitly exploits the pretrained support through a suitably chosen regularizer. Our results thus show how information encoded in pretrained weights can be implicitly exploited by gradient-based fine-tuning, reducing the amount of data needed to recover a downstream task.

0.26