The matrix completion problem concerns the reconstruction of a low-rank matrix from a subset of its entries. In recent years, nuclear norm minimization has emerged as a popular reconstruction method, and there is now a solid theoretical foundation for matrix completion using nuclear norm minimization and related algorithms. However, existing recovery guarantees assume that the revealed entries are uniformly distributed. This severely restricts the types of matrices that can be recovered; they need to be incoherent, or have their mass spread out uniformly across all elements. Here, we show that nuclear norm minimization can in fact recover an arbitrary low-rank matrix from very few entries -- no matter how coherent, or spiky the matrix -- provided the sampling distribution is dependent, in the right way, on the matrix. Within this general framework, incoherent matrix completion from uniformly distributed entries is a special case.

本文提出了一种特定偏向分布的采样方式，利用该采样方式可以从少量采样的数据中精确恢复任何秩为r的nxn的矩阵（无需满足之前已有的结构限制要求），而且在没有先验信息下本文建立了三种使用该采样方式的方法，其中还包括分析了针对非均匀采样情形中，加权核范数/迹范数惩罚的优点。

可证明地补全任意低秩矩阵