基于并行QR分解的快速低秩矩阵补全模型与算法研究

低秩矩阵补全是一种恢复矩阵缺失信息的有效方法。该方法对含有结构化缺失信息的矩阵数据较为鲁棒，现已应用于机器学习的诸多领域。现有方法的问题是其恢复速度较慢且不能同时兼顾算法速度与收敛精度。为克服这一关键科学问题，本项目拟从以下三方面进行改进：(1)提出基于QR分解的计算矩阵前几个较大奇异值的迭代方法，以避免传统方法的计算浪费问题，称之为近似SVD；(2)在加权核范数最小化方法的基础上提出泛化模型，并使用近似SVD加速模型求解。由于传统加权核范数最小化模型是改进模型的特例，改进方法同样具有较高的收敛精度；(3)提出基于多种非核范数最小化和并行QR分解的矩阵补全方法，以进一步提高算法的收敛精度和实时处理能力。本项目将在仿真数据和实际数据集上验证改进方法的算法速度和收敛精度，并给出详细的收敛性分析。本项目的研究成果将为背景建模、张量恢复等研究领域提供重要的理论基础和算法模型。

Low-rank matrix completion is an effective method for recovering the missing entries of matrices. Duo to its robustness to structured noises, it has been widely used in many fields of machine learning. However, most popular methods are not fast and cannot provide both convergence accuracy and convergence speed. In this project, several fast low-rank matrix completion methods based on approximate Singular Value Decomposition (SVD) will be proposed to overcome the above problems. At first, an iterative method based on QR decomposition will be proposed to calculate the largest r (r>0) singular values of a matrix for reducing the computational waste in the traditional methods, which can be called an approximate SVD. Secondly, several generalized methods of weighted nuclear norm minimization will be proposed. These methods will be very fast because of using the approximate SVD for acceleration. The proposed methods will also be as accurate as the methods based on weighted nuclear norm minimization, because the latters are the special cases of the formers. Finally, several low-rank matrix completion methods based on non-nuclear norm minimization and parallel QR decomposition will be proposed to improve their convergence accuracies and real-time data processing abilities. The speeds, accuracies and convergence analyses of the proposed methods will be verified by using some simulation datasets and real visual datasets. The results of this project will provide necessary algorithms, models and theoretical bases for many related fields, such as video background modelling, tensor recovery and so on.