The EMS Publishing House is now **EMS Press** and has its new home at ems.press.

Please find all EMS Press journals and articles on the new platform.

# Mathematical Statistics and Learning

Full-Text PDF (531 KB) | Metadata | Table of Contents | MSL summary

**Volume 1, Issue 2, 2018, pp. 171–225**

**DOI: 10.4171/MSL/1-2-2**

Published online: 2018-09-05

Near-optimality of linear recovery from indirect observations

Anatoli Juditsky^{[1]}and Arkadi Nemirovski

^{[2]}(1) Université Grenoble-Alpes, Saint-Martin-d’Hères, France

(2) Georgia Institute of Technology, Atlanta, USA

We consider the problem of recovering linear image $Bx$ of a signal $x$ known to belong to a given convex compact set $\mathcal X$ from indirect observation $\omega=Ax+\xi$ of $x$ corrupted by random noise $\xi$ with finite covariance matrix. It is shown that under some assumptions on $\mathcal X$ (satisfied, e.g. when $\mathcal X$ is the intersection of $K$ concentric ellipsoids/elliptic cylinders, or the unit ball of the spectral norm in the space of matrices) and on the norm $\|\cdot\|$ used to measure the recovery error (satisfied, e.g. by $\|\cdot\|_p$-norms, $1\leq p\leq 2$, on $\mathbf R^m$ and by the nuclear norm on the space of matrices), one can build, in a computationally efficient manner, a "seemingly good“ *linear in observations estimate*. Further, in the case of zero mean Gaussian observation noise and general mappings $A$ and $B$, this estimate is near-optimal among all (linear and nonlinear) estimates in terms of the maximal over $x\in \mathcal X$ expected $\|\cdot\|$-loss. These results form an essential extension of classical results [7, 24] and of the recent work [13], where the assumptions on $\mathcal X$ were more restrictive, and the norm $\|\cdot\|$ was assumed to be the Euclidean one.

*Keywords: *Nonparametric estimation, linear estimation, minimax estimation, conic optimization

Juditsky Anatoli, Nemirovski Arkadi: Near-optimality of linear recovery from indirect observations. *Math. Stat. Learn.* 1 (2018), 171-225. doi: 10.4171/MSL/1-2-2