CS Paper Radar

Scaled-Gradient Hard Thresholding Algorithms for Sparse Signal Recovery

Nan Meng, Yun-Bin Zhao

cs.IT ·submitted 2026-10-30 06:02 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Sparse descent subspace-Newton thresholding algorithm for sparse optimization problems

cs.IT math.OC ·2026-10-30 ·Zhong-Feng Sun, Nan Meng, Yun-Bin Zhao
similarity 0.75
Abstract

In this paper, we propose a sparse descent direction derived from the Newton direction within a low-dimensional subspace for sparse optimization problems. Building upon this direction and incorporating hard thresholding and orthogonal projection, we develop a novel algorithm termed the sparse descent subspace-Newton thresholding (SDSNT) algorithm. We further establish its global convergence under the restricted isometry property $δ_{3k}\leq \sqrt{3/20}$ of the measurement matrix. Numerical experiments on random sparse vector recovery and audio signal reconstruction reveal that SDSNT achieves comparable performance to several state-of-the-art algorithms. Notably, relative to most of them, it delivers superior recovery at high sparsity levels and improved efficiency at low sparsity levels.

0.24

Instance Optimal Sparse Recovery from Nonlinear Observations: A Unified Framework

cs.IT eess.SPmath.ST ·2026-09-02 ·Junren Chen, Arian Maleki
similarity 0.71
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

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

Compressive Sensing - Introduction and Relations to Deep Learning

cs.IT ·2026-08-25 ·Hung-Hsu Chou, Johannes Maly, Holger Rauhut
similarity 0.65
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

Recovering linear images of sparse signals from indirect observations

cs.IT stat.MLcs.LGmath.OC ·2026-09-05 ·Anatoli Juditsky, Arkadi Nemirovski
hot direction similarity 0.65
Abstract

In this paper, we develop and analyze techniques for recovering a linear image $Bx$ of an unknown signal $x$ from indirect noisy observation $ω=Ax+ξ$. It is {\em a priori} known that $x\in \cX$, a given convex compact set, and that $x$ is $s$-sparse---has at most $s$ nonvanishing entries. The proposed estimates belong to a large family of recovery routines by $\ell_1$-minimization. However, unlike the classical result describing performance of such estimates, we do not make any special (and hard to check) assumptions about the sensing matrix $A$ such as nullspace or Restricted Isometry condition and the like. As a consequence, parameters of the estimates and the upper bounds on their risks are not available in a closed analytic form, but are delivered instead by efficient computation as solutions to explicit convex optimization problems.

0.26

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

Distinguishability and Recovery for a Doubly Sparse Spiked Wigner Model

cs.LG stat.ML ·2026-10-16 ·Ioana Dumitriu, JD Flynn, Zhichao Wang
similarity 0.63
Abstract · 50 pages, 9 figures, 8 tables

We study distinguishability and recovery of a sparse rank-one signal in a spiked Wigner model with independently sparse noise through a variety of algorithms and parameter regimes. The signal and noise have separate sparsity parameters, while the signal-to-noise ratio (SNR) remains of constant order as the matrix size grows. For sub-Gaussian noise and spikes whose nonzero coordinates are bounded away from zero, a leave-one-out quadratic thresholding procedure (a generalization of Ding et al., 2024) identifies the support. Sign synchronization yields exact recovery for a Rademacher spike, and spectral refinement yields strong recovery. The quadratic thresholding search parameter gives an explicit tradeoff between signal sparsity, noise sparsity, and computational cost. We also study extensions to sub-Gaussian spike priors through diagonal and quadratic thresholding. For Rademacher spikes with continuous nonzero noise, we develop an identical search algorithm that exploits unblurred signal entries, the existence of which permits distinguishability; connectivity of the graph they reveal provides a sufficient condition for exact recovery. These guarantees do not require moment assumptions on the continuous noise distribution. Together with our previous PCA results (Dumitriu et al., 2026), our analysis covers almost the entire space of parameters and regimes for distinguishing and recovering in our doubly sparse spiked Wigner model.

0.35

Guaranteed Low-Rank Tensor Recovery from Modewise Measurements via Normalized Block-Weighted Riemannian Gradient Descent

cs.LG ·2026-09-21 ·Yushi Zhou, Feng Zhang
similarity 0.60
Abstract

We consider the recovery of low-multilinear-rank tensors from linear measurements and propose an adaptive block-weighted modewise Riemannian gradient descent method. The method combines memory-efficient modewise measurements with a normalized adaptive weighting strategy for the core and factor components of the Riemannian gradient. The weighting improves convergence without increasing the multilinear-rank bound of the search direction or the size of the reduced core used for retraction. Under the tensor restricted isometry property and a suitable initialization, we establish local linear convergence and derive sampling guarantees for sub-Gaussian and subsampled orthogonal with random sign (SORS) measurements. Numerical experiments on synthetic low-Tucker-rank tensors show that the proposed method reduces iteration counts and computational time while maintaining reliable recovery performance, especially near the recovery threshold and for structured SORS measurements.

0.20