- journal article metadata
European Mathematical Society Publishing House
2018-09-08 23:30:01
Mathematical Statistics and Learning
Math. Stat. Learn.
MSL
2520-2316
2520-2324
Statistics
10.4171/MSL
http://www.ems-ph.org/doi/10.4171/MSL
subscribers
European Mathematical Society Publishing House
Zuerich, Switzerland
1
2018
2
Near-optimality of linear recovery from indirect observations
Anatoli
Juditsky
Université Grenoble-Alpes, Saint-Martin-d’Hères, France
Arkadi
Nemirovski
Georgia Institute of Technology, Atlanta, USA
Nonparametric estimation, linear estimation, minimax estimation, conic optimization
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.
Statistics
Numerical analysis
Operations research, mathematical programming
171
225
10.4171/MSL/1-2-2
http://www.ems-ph.org/doi/10.4171/MSL/1-2-2
9
5
2018