The EMS Publishing House is now EMS Press and has its new home at

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