矩阵补全是利用观测到的矩阵元素去估计未知元素,从而恢复整个矩阵。它被广泛应用于协同过滤,推荐系统等机器学习应用中。在这些机器学习应用中,通常用一个矩阵来存储数据。这些数据矩阵通常是低秩的,而且有一些缺失数据,如何通过观测到的数据,应用矩阵低秩的特性,来预测这些缺失数据从而恢复矩阵就是低秩矩阵补全的问题。推荐系统是矩阵补全的一个典型的应用,例如在MovieLens中,存有部分用户对一些电影的打分,矩阵补全就是根据这些已有的打分预测用户对于其他电影的打分,从而推荐用户可能感兴趣的电影。通常我们把低秩作为一个限制条件,然而最小化秩的问题是一个NP Hard的问题,所以通常整个问题会被凸松弛成一个矩阵核范数最小化问题。在解决核范数最小化问题时,通常通过迭代求解,然而在迭代过程中需要对这些数据矩阵做一次或多次的奇异值分解(Singular Value Decomposition,SVD)。由于奇异值分解(SVD)计算复杂度较高,所以当数据矩阵规模较大时,一些常规的矩阵补全算法会受到限制。本文通过引入随机投影来解决这个问题。本文引入随机投影,来对大规模的数据矩阵做随机奇异值分解,从而来加快矩阵的奇异值分解,从而加快经典的Soft-Impute算法。同时本文还对这个算法做了复杂度和界的理论分析。本文在两个典型的推荐系统数据集:Jester和MovieLens上通过实验验证了,我们的算法可以更快更好的实现矩阵补全。