图像复原问题是图像处理领域的核心课题,在求解图像复原问题的方法中,非局部方法近年来得到了广泛的研究,其中有一类方法将矩阵的低秩性作为先验信息进行正则化建模,在多种图像处理实际应用的问题当中取得了良好的效果。非局部方法有着共同的缺点,即计算规模大,算法的计算效率较低。2016年Osher等人提出的低维流形（Lowdimensional Manifold Model,LDMM）图像处理方法引起了广泛的关注,该方法能够有效地保持图像结构信息,但是其计算复杂度较大。矩阵与张量分解的快速算法有着多种类别,其中计算低秩逼近问题的随机化算法近年来有着长足的发展。本文基于随机方法对此方法提出改进,具体研究内容如下:（1）LDMM方法中的关键一步是求解一个大型线性方程组,且其条件阵是一个难以计算的大规模图像块相似性矩阵,导致算法的时间复杂度较大。针对这一问题,本文基于随机化方法对LDMM算法进行改进。首先,对于迭代算法中更新图像块集合矩阵所需要求解的线性方程组,将其近似为一个通过矩阵点积就可以直接计算图像块集合矩阵的公式;其次,对于每个像素,将与其计算相似度的图像块的范围缩小在一个局部邻域内,从而减小相似度矩阵的规模;最后,通过一种随机采样方法进一步地减小相似度矩阵的计算成本,从而加速算法。数值实验表明,相较于原本的LDMM方法,本文所提出方法的计算速度大幅提升,并能达到和原方法相近的图像恢复效果。（2）LDMM方法中用点积分法对Laplace-Beltrami方程进行了近似,所得到的线性方程组将含有离散误差。对于这个问题,一方面,本文将此方程组求解问题转化为最小二乘问题从而减小误差,并利用图像的非局部自相似性,将图像块集合矩阵的低秩性作为先验约束,对问题进行正则化建模,并使用交替方向乘子法来迭代求解。对于迭代算法中的所需求解的核范数最小化问题,采用奇异值收缩方法求解,并利用随机化奇异值分解来加速算法。另一方面,本文不将图像块向量化,而是将其作为矩阵来处理,则图像块集合被表示为一个三阶张量,从而将上述低秩正则化模型转化为张量低秩模型。本文通过高阶奇异值分解来求解张量的低秩逼近问题,并利用随机化算法对张量分解进行加速。