CS Paper Radar

Instance Optimal Sparse Recovery from Nonlinear Observations: A Unified Framework

Junren Chen, Arian Maleki

cs.IT eess.SPmath.ST ·submitted 2026-09-02 05:19 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Scaled-Gradient Hard Thresholding Algorithms for Sparse Signal Recovery

cs.IT ·2026-10-30 ·Nan Meng, Yun-Bin Zhao
similarity 0.71
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

The Generalized Twin Image: Understanding Regularized Phase Retrieval

eess.IV physics.optics ·2026-10-30 ·Zhiyuan Hu, Michael Unser, Jonathan Dong
similarity 0.66
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

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

The Fusion Frame Phase Retrieval

cs.IT ·2026-09-08 ·Haixia Liu, Bing Gao, Yang Wang
similarity 0.65
Abstract · 32 pages, 2 figures

The phase retrieval problem involves reconstructing a function or signal solely from the magnitude of linear measurements. Most theoretical analyses of phase retrieval algorithms rely on i.i.d. Gaussian random measurements or sub-Gaussian random measurements. In this paper, our focus is on the fusion frame phase retrieval problem, where the sampling matrices are i.i.d. rank-$r$ orthogonal projections drawn from the Haar measure. We present concentration inequalities for functions on the set of rank-$r$ orthogonal projection matrices. These inequalities are crucial for the theoretical analysis of the fusion frame phase retrieval problem. Based on these inequalities, we demonstrate that gradient descent, combined with a two-stage initialization, achieves linear convergence to the target signal up to a global phase with a measurement complexity of $O(d\log^2 d)$ when the rank $r = O(1)$. We verify this convergence through numerical results.

0.16

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

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

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

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