CS Paper Radar

Recovering linear images of sparse signals from indirect observations

Anatoli Juditsky, Arkadi Nemirovski

cs.IT stat.MLcs.LGmath.OC ·submitted 2026-09-05 16:57 UTC · v1
hot direction

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Learning structured linear dynamical systems from missing observations

cs.LG stat.MLeess.SYmath.OC+1 ·2026-10-08 ·Aravinda Kanchana Ruwanpathirana, Hemant Tyagi, Sunny G. W. Wang
similarity 0.68
Abstract · 62 pages, 3 figures

We consider the problem of learning structured linear dynamical systems over convex sets $\mathcal{K}$, where only a small subset of the observations are available at each time point. An estimator which minimizes a bias-corrected, potentially non-convex objective function is proposed. Non-asymptotic bounds are obtained for the statistical error, which depend on the local complexity of $\mathcal{K}$, the trajectory length $T$, and the sub-sampling probability $p$. Convergence of the projected gradient descent algorithm is also established. The general theory is applied to settings where (i) $\mathcal{K}$ is a subspace, (ii) $\mathcal{K}$ is the set of bi-isotonic matrices, and (iii) $\mathcal{K}$ is the set of matrices whose rows are formed by sampling Lipschitz functions. We show meaningful recovery of the transition matrix is possible for values of $T$ much smaller than what is required in the unconstrained case, and for $p = o(1)$.

0.18

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

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

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

Improving the Optimization Landscape of Matrix Completion with $ε$-close Surrogates

cs.LG math.OC ·2026-10-30 ·Ziye Ma
top venue similarity 0.67
Abstract · 30 pages, accepted at NeurIPS'26

Non-convex optimization is central to machine learning and AI, yet unlike its convex counterpart, it still lacks a general and principled framework. In this work, we try to highlight the importance of combining noisy perturbations with over-parametrization mathematically under the classic setting of matrix completion (MC). Matrix completion is an important non-convex recovery problem in which only a subset of a matrix's entries is observed, and the remaining entries must be recovered using low-rank constraints. This problem is notoriously difficult because observations are limited. However, we show that by injecting $ε$-level perturbations into the nullspace of the observation mask, we can construct noisy matrix sensing surrogates whose solutions remain $\mathcal{O}(ε)$-close to the ground truth with valid restricted isometry property (RIP) constants. The existence of RIP further enables powerful tensor frameworks to be applied with theoretical guarantees. This approach reflects a broader empirical trend in which stochasticity or noise improves the curvature of the optimization landscape, allowing over-parameterized (a.k.a large) models to better separate signal from noise. Assuming each matrix entry is observed independently, we establish quantitative recovery guarantees without explicit requirements on sampling rate or incoherence, and discuss how such assumptions can further strengthen our results.

0.36

Sparse Approximation via Polynomial Equations

eess.SP math.NA ·2026-09-10 ·Matija Tomić, Raphaël Widdershoven, Lieven De Lathauwer
similarity 0.66
Abstract · 10 pages, 9 figures, 1 table. Submitted to IEEE Transactions on Signal Processing

We consider the problem of finding sparse solutions of an underdetermined linear system $Ax=b$. In contrast to conventional approaches based on greedy algorithms or convex relaxation, we reformulate sparse approximation as a structured system of polynomial equations and connect with the literature on tensor methods. We develop an eigenvalue decomposition based method that formally guarantees recovery of all sparse solutions if there is more than one. We also develop two optimization-based methods achieving favorable computational complexity. The new methods allow explicit control of the target sparsity. Numerical experiments illustrate the performance and compare to basis pursuit (denoising) and orthogonal matching pursuit.

0.20

Low-rank matrix recovery landscapes beyond RIP with application to rank-one measurements

cs.IT math.OCmath.ST ·2026-09-05 ·Andrew D. McRae
theory similarity 0.66
Abstract

We study the problem of low-rank matrix recovery from linear measurements via the global nonconvex landscape of a low-rank factored formulation of the matrix LASSO (nuclear-norm--regularized least-squares). If the landscape is benign, that is, has no bad local optima, then practical and scalable algorithms can compute good statistical estimates. Previous state-of-the-art landscape guarantees have typically assumed that the linear measurement operator has the restricted isometry property, that is, the operator is approximately an isometry over all low-rank matrices. This is an unrealistic assumption for many applications; in particular, when the individual measurement matrices are themselves low-rank, we typically have poor upper isometry constants. To overcome this, we establish new guarantees of a benign landscape under a weaker isometry condition: rather than requiring upper isometry over all low-rank matrices, we only require it over the linear low-rank tangent space to the low-rank ground truth matrix. To illustrate the utility of this result, we apply it to the problem of matrix recovery from random rank-one linear measurements; via high-probability concentration bounds on the random measurement operator, we prove a novel landscape guarantee with statistically near-optimal sample complexity and recovery error.

0.25

Instance Optimal Sparse Recovery from Nonlinear Observations: A Unified Framework

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