On robust recovery of signals from indirect observations

We consider an uncertain linear inverse problem as follows. Given observation ω=Ax_*+zeta where A∈ bf Rm× p and zeta∈ bf Rm is observation noise, we want to recover unknown signal x_*, known to belong to a convex set cal Xsubsetbf Rn. As opposed to the "standard" setting of such problem, we suppose that the model noise zeta is "corrupted" -- contains an uncertain (deterministic dense or singular) component. Specifically, we assume that zeta decomposes into zeta=Nnu_*+xi where xi is the random noise and Nnu_* is the "adversarial contamination" with known cal Nsubset bf Rn such that nu_*∈ cal N and N∈ bf Rm× n. We consider two "uncertainty setups" in which cal N is either a convex bounded set or is the set of sparse vectors (with at most s nonvanishing entries). We analyse the performance of "uncertainty-immunized" polyhedral estimates -- a particular class of nonlinear estimates as introduced in [15, 16] -- and show how "presumably good" estimates of the sort may be constructed in the situation where the signal set is an ellitope (essentially, a symmetric convex set delimited by quadratic surfaces) by means of efficient convex optimization routines.