NEAR-OPTIMALITY OF LINEAR RECOVERY IN GAUSSIAN OBSERVATION SCHEME UNDER ∥.∥22-LOSS

We consider the problem of recovering linear image Bx of a signal x known to belong to a given convex compact set chi from indirect observation omega = Ax + sigma xi of x corrupted by Gaussian noise xi. It is shown that under some assumptions on chi (satisfied, e.g., when chi 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 is an element of chi, expected parallel to.parallel to(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 chi is given by a "separable" constraint like chi = {x : Sigma(i)a(i)(2)x(i)(2) <= 1} or chi = {x : max(i) vertical bar a(i)x(i)vertical bar <= 1}.