Title: Near-Optimality of Linear Recovery from Indirect Observations Show Chinese title

Title: 从间接观测中进行线性恢复的近似最优性

Abstract: We consider the problem of recovering linear image $Bx$ of a signal $x$ known to belong to a given convex compact set ${\cal 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 ${\cal X}$ (satisfied, e.g., when ${\cal 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 "presumably good" linear in observations estimate, and that in the case of zero mean Gaussian observation noise, this estimate is near-optimal among all (linear and nonlinear) estimates in terms of its worst-case, over $x\in {\cal X}$, expected $\|\cdot\|$-loss. These results form an essential extension of those in our paper arXiv:1602.01355, where the assumptions on ${\cal X}$ were more restrictive, and the norm $\|\cdot\|$ was assumed to be the Euclidean one. In addition, we develop near-optimal estimates for the case of "uncertain-but-bounded" noise, where all we know about $\xi$ is that it is bounded in a given norm by a given $\sigma$. Same as in arXiv:1602.01355, our results impose no restrictions on $A$ and $B$. This arXiv paper slightly strengthens the journal publication Juditsky, A., Nemirovski, A. "Near-Optimality of Linear Recovery from Indirect Observations," Mathematical Statistics and Learning 1:2 (2018), 171-225. Show Chinese abstract

Abstract: We consider the problem of recovering linear image $Bx$ of a signal $x$ known to belong to a given convex compact set ${\cal X}$ from indirect observation $\omega=Ax+\xi$ of $x$ corrupted by random noise $\xi$ with finite covariance matrix. 结果表明，在关于${\cal X}$的一些假设下（例如，当${\cal X}$是$K$个同心椭球/椭圆柱的交集时满足此条件，或者在矩阵空间中为谱范数下的单位球时也满足），以及关于用于测量恢复误差的范数$\|\cdot\|$（例如，由$\|\cdot\|_p$-范数，$1\leq p\leq 2$在${\mathbf{R}}^m$上，以及矩阵空间中的核范数满足），可以以计算高效的方式构建一个“可能良好”的观测线性估计，并且在零均值高斯观测噪声的情况下，这种估计在$x\in {\cal X}$上相对于所有（线性和非线性）估计的最坏情况下的$\|\cdot\|$-损失期望来说是接近最优的。 这些结果是对我们发表在arXiv:1602.01355上的论文中的结果的重要扩展，在那篇论文中，关于${\cal X}$的假设更加严格，并且假定$\|\cdot\|$的范数为欧几里得范数。 此外，我们针对“不确定但有界”的噪声情况发展了接近最优的估计方法，在这种情况下，我们对于$\xi$所知的只是它在一个给定范数下由$\sigma$给出的界限内。 与arXiv:1602.01355相同，我们的结果对$A$和$B$没有任何限制。 这篇arXiv论文略微加强了期刊出版物Juditsky, A., Nemirovski, A.的成果： “从间接观测中进行线性恢复的近似最优性”， 《数学统计与学习》1:2（2018），171-225。