低秩矩阵恢复主要研究的问题是,在当矩阵中的某些元素被破坏后,自动地去识别出被损坏的元素,从而恢复出原矩阵。这个问题在信号图像处理、数据分析、计算机视觉等很多领域都有重要的应用。在实际的应用中,对高维数据的处理不可避免。数据信号之间的相关度和冗余度以及对数据信号进行分析和处理时的困难会随着数据信号维度的升高而变多。所以,这就需要更加准确合理地利用好高维度数据之间的稀疏性和低秩性,这对于高效地采集、分析和处理这些大规模的数据十分的重要。交替方向法常用来求解低秩矩阵恢复的凸优化问题,每个子问题的迭代,求解过程中都会涉及到核范数极小化的优化求解,即对大规模矩阵的奇异值分解。如果直接进行分解操作,那么计算的代价将十分巨大。本文采用随机矩阵技术来求解核范数的优化问题。随机矩阵计算算法相比传统的对矩阵的直接计算具有相当大的优势。主要思想是将原矩阵的主要特征压缩到一个低维的近似矩阵中,再对近似矩阵进行矩阵计算,这个近似矩阵的维度是远远小于原矩阵的,但是它却保留了一些原矩阵的重要性质。从而极大的提高了计算效率,并且精度也相当可观,很好的降低算法的复杂度。首先提出了基于核范数极小化的改进算法,分别是标准CUR分解和快速CUR分解算法。CUR分解算法是将矩阵分解成三个部分,分别为C,U,R,其中矩阵C和R是通过列选择算法采样得到,再进行矩阵逆和矩阵乘法计算得到交叉矩阵U。矩阵C(9)U(9)R是原矩阵的一个近似。仿真实验表明,通过对近似矩阵的计算,可以很大程度上的提高奇异值分解的计算效率。接着,针对奇异值算法的改进提出了两种随机算法,分别是标准随机k-SVD算法和快速随机k-SVD算法。主要思想是对原有的大规模数据矩阵进行降维随机采样,使用随机投影算法得到原数据矩阵的一个近似,对于这个近似矩阵再进行相应的矩阵运算,最后可以得到与原矩阵计算相似的结果。通过仿真实验表明,计算效率大大提升,内存存储空间也得到很大的改善,同时还拥有良好的精度。最后,基于GPU加速实现的随机奇异值分解算法,这样可以提升在实际应用中对大规模数据矩阵的计算效率。通过仿真实验,分析了CPU和GPU的计算特点,并对原随机算法又进行了改进,使其能够更好的适应GPU计算架构。这个改进可以很大程度上提高核范数极小化的计算效率。