Mathematical Statistics and Learning
Full-Text PDF (531 KB) | Metadata | Table of Contents | MSL summary
Published online: 2018-09-05
Near-optimality of linear recovery from indirect observationsAnatoli Juditsky and Arkadi Nemirovski (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 , 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