低秩矩阵恢复算法及其在图像处理中的应用

Low rank matrix completion and tensor completion have recently become popular in optimization and information sciences. Their applications can now also be found in recommendation systems, image processing and computer vision. The existing algorithms in many cases cannot sufficiently play their role and advantage because of its large amount of calculation, slow speed and the bad effect for large-scale matrix. In this project, we mainly study the theory, algorithm and application in image processing of Low Rank Matrix Completion and Tensor Completion. Our research content as follows: Firstly, in theory we will further research that under which restricted isometry property (RIP) condition on the new linear transformation we can obtain the exact low-rank matrix solution by solving the nuclear norm minimization and that how to improve RIP conditions for exact low rank matrix recovery via nonconvex relaxations Mp-minimization. Secondly, we will propose the effective algorithms for the nonconvex relaxations Mp-minimization to solve efficiently the problem which the size of the matrix is large. Thirdly, we will try to maintain integrity of edge information in the process of the feature extraction by the algorithms of Mp-minimization. Forthly, we study low-rank decomposition of kernel matrix based on matrix completion, and consider feature extraction in kernel space. We propose a new feature extraction algorithm based on low-rank decomposition of kernel matrix and support vector machine.Finally, we will study tensor completion from the theory and the algorithm, and apply it efficiently to image restoration in the aspects of multi-channel image and video.

低秩矩阵恢复和张量恢复是优化领域和信息科学领域最近研究的热点，在推荐系统、图像处理和计算机视觉等方面已经找到重要的应用。现有的算法计算量大、速度慢、对于大规模问题效果不好，这使得它在很多场合不能充分发挥其作用和优势。本项目主要研究低秩矩阵恢复以及张量恢复问题的理论、算法和它在图像处理中的应用。主要包括：从理论上进一步研究在新的测量算子作用下恢复低秩矩阵的RIP条件以及Mp非凸松弛模型RIP条件的改进；针对非凸的Mp极小化模型来设计有效的算法，使得对于大规模矩阵能够得到良好的效果；应用Mp范数极小化的算法在图像背景的特征提取过程中尽量保存完整的边缘信息；研究基于矩阵恢复的低秩矩阵近似分解算法，并将其结合支持向量机应用到核空间的特征提取中；从理论和算法两方面利用已有的研究成果对张量恢复问题进行研究，并应用张量恢复的方法在多渠道图像和视频方面进行图像修复使之得到更好的试验效果。

随着压缩传感和稀疏表示问题的发展，矩阵恢复和张量恢复逐步成为人们研究的热点，在推荐系统、图像处理和计算机视觉等方面已经得到重要应用。本项目主要研究低秩矩阵恢复以及张量恢复问题的理论、算法和它在图像处理中的应用。主要研究成果是：我们建立了指示函数与核范数的极小化模型，并利用迫近映射的概念设计了求解该模型的迫近点算法（PPA-IF）。将含噪声与不含噪声的矩阵完整化问题统一为一个模型。针对非凸的极小化模型设计了有效的算法，使得对于大规模的矩阵具有良好的效果。利用极大极小化方法设计了加权软阈值算法和正则半迭代缩减算法。因为拟范数本身是非凸的，这使得直接求解是NP-难问题，因此在求解时我们考虑解该问题的一系列的近似子问题来得到原问题的解。我们提出一个介于软阈值缩减算子和硬阈值缩减算子之间的一个新的算子。该缩减算子不仅连续，而且当参数取得合适的值时，还可使奇异值向量中的某些元素保持不变。针对很多非凸模型，我们进行归纳并建立了一个非凸模型框架，在这个框架下，已有的非凸模型及我们前面所提出的一些非凸模型都可以归入其中。我们针对硬阈值类的算法进行了改进。许多硬阈值的算法都是用负梯度方向作为使函数值下降的搜索方向，但用负梯度方向会导致“之”字型路线而减慢收敛速度。我们受半迭代方法的启示设计了半迭代硬阈值算法。与其他的迭代硬阈值算法相比，改进后的算法在计算时间上有很大的提高。由于张量的内在结构比较复杂，现有解决张量完整化问题的算法远远少于矩阵完整化问题的算法。我们将加权核范数模型引入张量完整化问题中，建立了张量情况下的非凸模型。同时我们还得到半正则的优化方法来求解张量完整化问题。另外，对于求解张量完整化问题的硬阈值方法，我们也应用半迭代方法在下降方向上进行改进，并得到了很好的效果。我们研究了低秩矩阵恢复和张量恢复在图像处理领域中的应用，主要用于图像的去噪等图像处理。