Near-optimality of linear recovery from indirect observations (Q1739121)

Summary: 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 \(\mathbb R^m\) and by the nuclear norm on the space of matrices), one can build, in a computationally efficient manner, a ``seemingly good'' \textit{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 [\textit{D. L. Donoho} et al., Ann. Stat. 18, No. 3, 1416--1437 (1990; Zbl 0705.62018); \textit{M. S. Pinsker}, Probl. Inf. Transm. 16, 120--133 (1980; Zbl 0452.94003); translation from Probl. Peredachi Inf. 16, No. 2, 52--68 (1980)] and of the recent work [the authors, Ann. Stat. 46, No. 4, 1603--1629 (2018; Zbl 1403.62047)], where the assumptions on \(\mathcal X\) were more restrictive, and the norm \(\|\cdot\|\) was assumed to be the Euclidean one.