Near-optimality of linear recovery from indirect observations

Source 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 \|\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.