一类低秩矩阵填充问题的快速优化算法*

郑伟东，李声豪，涂志辉，胡文玉，喻高航

(赣南师范大学 数学与计算机科学学院，江西 赣州 341000)

1 引言

矩阵填充(Matrix Completion, MC)问题主要解决得到数据矩阵的某一小部分的数据，填充那些未知或缺失的数据.为了解决这个问题，通常假设这个矩阵存在信息冗余，例如数据矩阵是低秩的，即其数据分布在一个低维的线性子空间上.目前，矩阵填充问题在推荐系统、图像恢复、数据分析以及机器学习等领域中有着广泛的应用.许多学者[1-8]在矩阵填充中做了大量的工作，这些工作主要围绕如下优化问题实现矩阵填充：

(1)

其中，X∈Rm×n是存在元素缺失的观测矩阵，A∶Rm×n→Rn是一个线性算子，b∈Rn.由于矩阵的秩函数是一个非凸且不连续的函数，因此，问题(1)是一个NP难问题.Candès和Recht[1]证明了问题(1)可以通过核范数近似矩阵的秩进行求解：

(2)

(3)

其中，δ≥0是噪声水平.另一方面，问题(3)还可以转化为如下的无约束的最小二乘问题：

(4)

Micchelli等人[13]提出了基于临近算子的不动点算法，该算法在理论上可以解决两个凸函数相加的优化问题. 基于这种动机, 本文将问题(2)、(3)和(4)统一的归纳为两个凸函数相加的模型，使得求解该类矩阵填充问题时更加通用简洁.考虑如下模型：

(5)

(6)

2 算法

为了进一步提高算法的效率，本节使用了临近算子并结合了临近算子和次微分之间的关系，提出了一类不动点算法来解决问题(5).

2.1 相关理论

首先给出临近算子和次微分的定义，并给出它们之间的联系和后续需要使用的一些性质.

定义1[13](临近算子……