Near-Optimality of Linear Recovery in Gaussian Observation Scheme under $\Vert \cdot \Vert_{2}^{2}$-Loss

Anatoli B. Juditsky (1) , Arkadi Nemirovski (2)

1 DAO - Données, Apprentissage et Optimisation
2 ISyE - School of Industrial and Systems Engineering [Georgia Tech]

We consider the problem of recovering linear image Bx of a signal x known to belong to a given convex compact set X from indirect observation ω = Ax + σξ of x corrupted by Gaussian noise ξ. 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 ∈ X , expected · 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 : i a 2 i x 2 i ≤ 1} or X = {x : max i |a i x i | ≤ 1}.

Domaines: Statistiques [math.ST]

Anatoli B. Juditsky, Arkadi Nemirovski. Near-Optimality of Linear Recovery in Gaussian Observation Scheme under $\Vert \cdot \Vert_{2}^{2}$-Loss. Annals of Statistics, 2018, 46 (4), pp.1603-1629. ⟨10.1214/17-AOS1596⟩. ⟨hal-01336112⟩