The problem of recovering a matrix of low rank from an incomplete and
possibly noisy set of linear measurements arises in a number of areas. In order
to derive rigorous recovery results, the measurement map is usually modeled
probabilistically. We derive sufficient conditions on the minimal amount of
measurements ensuring recovery via convex optimization. We establish our
results via certain properties of the null space of the measurement map. In the
setting where the measurements are realized as Frobenius inner products with
independent standard Gaussian random matrices we show that $10 r (n_1 + n_2)$
measurements are enough to uniformly and stably recover an $n_1 \times n_2$
matrix of rank at most $r$. We then significantly generalize this result by
only requiring independent mean-zero, variance one entries with four finite
moments at the cost of replacing $10$ by some universal constant. We also study
the case of recovering Hermitian rank-$r$ matrices from measurement matrices
proportional to rank-one projectors. For $m \geq C r n$ rank-one projective
measurements onto independent standard Gaussian vectors, we show that nuclear
norm minimization uniformly and stably reconstructs Hermitian rank-$r$ matrices
with high probability. Next, we partially de-randomize this by establishing an
analogous statement for projectors onto independent elements of a complex
projective 4-designs at the cost of a slightly higher sampling rate $m \geq C
rn \log n$. Moreover, if the Hermitian matrix to be recovered is known to be
positive semidefinite, then we show that the nuclear norm minimization approach
may be replaced by minimizing the $\ell_2$-norm of the residual subject to the
positive semidefinite constraint. Then no estimate of the noise level is
required a priori. We discuss applications in quantum physics and the phase
retrieval problem.

本文介绍了通过测量映射来恢复不完整且可能带有噪声的低秩矩阵，探讨了通过凸优化推导恢复结果的条件。并阐述了通过测量矩阵实现 Frobenius 内积和独立标准高斯随机矩阵来恢复秩最多为 r 的 n1 × n2 矩阵的恢复结果等。最后，对量子物理和相位回收问题的应用进行了讨论。