Recovering linear images of sparse signals from indirect observations
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∈ 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 ℓ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.
Related
- Recovering Weak Signals with Normalizing Flows
- Logarithmic stability for recovering initial data of fractional heat equations from thin-set observations
- Twoblock clustering trees with coskewness-based dimension reduction: recovering piecewise multivariate linear regimes
- Linear Codes over 𝔽q+u𝔽q associated with Simplicial Complexes, Their Gray Images, and Subfield Codes
- Observations on the variety of equationally linear Heyting semilattices
BibTeX
@misc{juditsky2026recovering,
title = {{Recovering linear images of sparse signals from indirect observations}},
author = {Anatoli Juditsky and Arkadi Nemirovski},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.06182},
eprint = {2609.06182},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.06182},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Recovering linear images of sparse signals from indirect observations
AU - Anatoli Juditsky
AU - Arkadi Nemirovski
PY - 2026
DA - 2026/09/05
PB - arXiv
DO - 10.48550/arxiv.2609.06182
UR - https://arxiv.org/abs/2609.06182
AB - 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∈ 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 ℓ_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.
ER -