Recovering linear images of sparse signals from indirect observations

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 a priori known that x in, 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.