stat.MLSep 5, 2026

Recovering linear images of sparse signals from indirect observations

Authors: Anatoli Juditsky, Arkadi Nemirovski

Organizations: LJK, Université Grenoble Alpes, 700 Avenue Centrale, 38401 Domaine Universitaire de Saint-Martin-d’Hères, France · Georgia Institute of Technology, Atlanta, Georgia 30332, USA

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

In this paper, we develop and analyze techniques for recovering a linear image BxBx of an unknown signal xx from indirect noisy observation ω=Ax+ξω=Ax+ξ. It is {\em a priori} known that x∈\cXx\in \cX, a given convex compact set, and that xx is ss-sparse---has at most ss nonvanishing entries. The proposed estimates belong to a large family of recovery routines by ℓ1\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 AA 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.

Figures & tables

Figure 1: Bounds for risks of recovery of the entries xjx_{j} , j=1,...,64j=1,...,64 , sparsity parameter s=4s=4 .
Figure 2: Bounds for risks of recovery of the entries xjx_{j} , j=1,...,64j=1,...,64 . Left plot: sparsity s=3s=3 ; right plot:sparsity s=2s=2 .
Figure 3: Upper bounds for risks of recovery of the entries xjx_{j} , j=1,...,64j=1,...,64 , of the sparse signal in the setup of the first experiment in Section 7.1 . Left plot: sparsity parameter s=3s=3 ; right plot: sparsity parameter s=2s=2 .
Figure 4: Upper bounds for risks of estimation of random linear functionals gTxg^{T}x , sparsity parameter s=s‾(A[k])s=\underline{s}(A[k]) . Left plot: cumulative distributions of the risk bounds; right plot: distributions of the ratios of the risk bounds.
Figure 5: Upper bounds for risks of estimation of random linear functionals gTxg^{T}x , sparsity parameter s=s‾(A[k])−1s=\underline{s}(A[k])-1 . Left plot: cumulative distributions of the risk bounds; right plot: distributions of the ratios of the risk bounds.
Figure 6: ℓ2\ell_{2} -estimation errors and upper risk bounds for recovery of random 33 -sparse ( s=3s=3 )signals using routines from Sections 4 and 5 . Red bars represent the corresponding risk bounds.
Figure 7: ℓ1\ell_{1} -estimation errors and upper risk bounds for recovery of random 33 -sparse ( s=3s=3 ) signals using routines from Sections 4 and 5
Figure 8: ℓ2\ell_{2} -estimation errors and upper risk bounds for recovery of random 55 -sparse ( s=5s=5 ) signals using routines from Sections 4 and 5 .
Figure 9: ℓ1\ell_{1} -estimation errors and upper risk bounds for recovery of random 55 -sparse ( s=5s=5 ) signals using routines from Sections 4 and 5

Explore similar work

CardsList

  1. Demixing Sparse Signals from Nonlinear Observations using Generalized Non-convex Regularization

    Jul 12, 2026Raziyeh TakbiriSparse RecoveryNonconvex Optimization

    School of Electrical Engineering, Iran University of Science and Technology, Tehran, Iran

  2. The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements

    Sep 1, 2025Youssef Chaabouni, David GamarnikSparse RecoverySample Complexity

    Massachusetts Institute of Technology

  3. Robustness to Sparse Adversarial Corruption in Arbitrary Linear Measurements: Beyond Exact Recovery

    Oct 28, 2025Vishal Halder, Alexandre Reiffers-Masson, Abdeldjalil Aïssa-El-Bey +1Sparse RecoveryAdversarial Robustness

    IMT Atlantique, Lab-STICC, CNRS UMR 6285, Brest, France · Department of Computer Science and Automation, Indian Institute of Science, Bengaluru, India