This paper presents several novel theoretical results regarding the recovery
of a low-rank matrix from just a few measurements consisting of linear
combinations of the matrix entries. We show that properly constrained
nuclear-norm minimization stably recovers a low-rank matrix from a constant
number of noisy measurements per degree of freedom; this seems to be the first
result of this nature. Further, the recovery error from noisy data is within a
constant of three targets: 1) the minimax risk, 2) an oracle error that would
be available if the column space of the matrix were known, and 3) a more
adaptive oracle error which would be available with the knowledge of the column
space corresponding to the part of the matrix that stands above the noise.
Lastly, the error bounds regarding low-rank matrices are extended to provide an
error bound when the matrix has full rank with decaying singular values. The
analysis in this paper is based on the restricted isometry property (RIP)
introduced in [6] for vectors, and in [22] for matrices.

本文研究了低秩矩阵通过线性组合测量进行恢复的方法，结果表明经过妥善约束的核范数最小化可以从恒定数量的带有噪声的测量中稳定地恢复低秩矩阵，从噪声数据中恢复误差不超过三个目标。同时，本文对低秩矩阵的误差界限进行了扩展，并基于限制等距性质进行了分析。