Near-optimality of linear recovery from indirect observations

Abstract

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 $\Vert \cdot \Vert$ used to measure the recovery error (satisfied, e.g. by $\Vert \cdot {\Vert }_p$-norms, $1\le p\le 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 $\Vert \cdot \Vert$-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 $\Vert \cdot \Vert$ was assumed to be the Euclidean one.