Near-Optimality of Linear Recovery in Gaussian Observation Scheme under l2 -loss
Résumé
We consider recovering linear image $Bx$ of a signal $x$ known to belong to a given convex compact set $X$ from indirect observation $\omega=Ax+\sigma\xi$ of $x$ corrupted by Gaussian noise $\xi$. It is shown that under some assumptions on $X$ (satisfied, e.g., when $X$ is the intersection of $K$ concentric ellipsoids/elliptic cylinders), an easy-to-compute linear estimate is near-optimal in terms of its worst-case, over $x\in X$, expected $|\cdot|_2^2$-loss. The main novelty here is that the result imposes no restrictions on $A$ and $B$. To the best of our knowledge, preceding results on optimality of linear estimates dealt either with one-dimensional $Bx$ (estimation of linear forms) or with the ``diagonal case’’ where $A$, $B$ are diagonal and $X$ is given by a ``separable’’ constraint like $X={x :\sum_ia_i^2x_i^2\leq 1}$ or $X={x :\max_i|a_ix_i|\leq1}$. Joint work with A. Nemirovski (Georgia Tech).