求解矩阵补全问题的三分解方法

，(山东科技大学 数学与系统科学学院，山东 青岛 266590)

近年来，矩阵补全问题广泛应用于图像处理、计算机视觉、数据挖掘、模式识别和机器学习等领域。作为信号与图像处理技术的一个强大的新兴分支，矩阵补全已成为继压缩感知之后的又一种重要的信号获取工具[1]。

一般来说，要根据信号的部分采样元素来精确地恢复出所有元素是非常困难甚至是不可能的。但是当信号在一组基下是稀疏的且满足一定条件时，压缩感知理论证实了可以通过求解l1最小化问题来精确地恢复所有元素[2]。类似的，当信号用矩阵形式表示时，要根据其部分元素来恢复所有丢失元素也是很困难的。针对这一问题，Candès等[3]证明了当矩阵的奇异值具有稀疏性且采样数目满足一定条件时，大多数矩阵可以通过求解核范数最小化问题来精确地恢复所有元素。由矩阵的部分元素恢复所有元素这一问题称为矩阵补全问题，著名的Netflix问题便是一个典型的矩阵补全问题[4]。

给定不完整的低秩缺失矩阵W∈Rm×n，矩阵补全问题可以描述为如下优化问题：

(1)

其中A∈Rm×n为待补全的矩阵，Ω是A的p个已知元素的指标集。由于秩函数的非凸性和不连续性，上述秩函数最小化问题是NP难的，现有的算法无法有效地解决秩最小化问题。基于此，Candès等[5]证明了可用秩函数的凸包络—核范数来近似秩函数，即可将问题(1)凸松弛为如下核范数最优化问题

(2)

需要指出的是，矩阵补全模型(2)只能对缺失的元素进行恢复，而无法估计其所含的噪声。然而在某些情况下，噪声里往往会包含一些重要的信息，因此，噪声有时也是非常重要的待恢复成分。另一方面，矩阵补全模型(2)对大的稀疏噪声或野点非常敏感，为了克服上述模型的不足，Shi等[6]将矩阵补全模型(2)与鲁棒主成分分析(robust principal component analysis, RPCA)模型进行了推广，提出如下不完全RPCA(IRPCA)模型

(3)

(4)

现有的求解基于核范数的矩阵秩最小化问题的大多数算法，每一步迭代都需要进行奇异值分解，而多步奇异值分解则大大增加了算法的计算复杂度。为了降低计算复杂度，Xu等[8]将非负矩阵分解算法和矩阵补全模型相结合，提出了基于非负矩阵分解的矩阵补全模型；Zheng等[9]提出将含有噪声的低秩矩阵近似问题等价为双线性分解问题；Shang等[7]则将矩阵双分解(robust bilinear factorization，RBF)方法应用于RMC模型，得到了较好的数值结果。

基于矩阵分解在求解基于核范数的矩阵秩最小化问题中的优势，将矩阵的三分解[10]技术应用到RMC模型中，利用增广拉格朗日乘子法对模型进行求解，并将新模型应用于人脸识别的实际问题。数值实验结果显示，本研究提出的模型相较于RMC和RBF模型，计算速度更快，实验效果更好。

1 三分解技巧与模型

在高维数据分析中，矩阵分解是一个常用的技巧，也是一个非常有效的工具。常用的矩阵分解主要有QR分解、LU分解、奇异值分解、非负矩阵分解等。现有的大多数矩阵分解技巧都是将矩阵分解为两个具有某种特殊性质矩阵的乘积。本研究将利用矩阵的三分解技巧及核范数的正交不变性，尽可能地降低RMC模型的规模，以达到减少计算量的目的。

下面对所采用的矩阵三分解方法(TFM)进行介绍。设A∈Rm×n，rank(A)=r，则由参考文献[10]知，存在矩阵X∈Rm×r，Y∈Rr×r，Z∈Rr×n，使A=XYZT。其中X，Z为具有正交规范列的矩阵，即XTX=Ir，ZTZ=Ir。

上述分解称为矩阵A的三分解。本文就是基于矩阵三分解理论对RMC模型(4)进行修改。

(5)

由矩阵三分解的定义可知，当矩阵A的秩较小时，通过矩阵的三分解可将问题的规模大大降低。将主要针对上述等价模型(5)进行求解和分析。

2 模型求解与算法

本节中，将利用交替方向乘子法(alternating direction multiplier method, ADMM)对TFMC模型进行求解。

模型(5)的増广拉格朗日函数为

交替方向乘子法的基本迭代公式如下

(6-1)

(6-2)

(6-3)

(6-4)

(6-5)

2.1 收缩算子Y的更新

将变量E,X,Z固定，更新Y的最优化模型(6-1)可等价为

(7)

为了求解上述核范数最小化问题，给出以下引理：

本研究仍然使用奇异值分解的方法求解问题(7)，与未使用矩阵三分解的模型需要对m×n维的矩阵进行奇异值分解不同，只需要对r×r维的矩阵进行奇异值分解，其中r≪min(m,n)。

因此，TFM方法可以大大降低计算的复杂度。由引理知，模型(7)的最优解为

(8)

2.2 利用软阈值算子更新E

为了求解变量E，固定变量Y,X,Z，可将模型(6-2)转化为如下优化模型

为了得到Ek+1的最优解，需先确定EΩ和EΩC分别对应的两个子问题。其中，EΩ对应的子问题为

(9)

对问题(9)利用软阈值算子进行求解，可得其最优解为

(10)

另外，EΩC对应的子问题为

(11)

由问题(11)的最优性条件可得其最优解为

(12)

2.3 利用Orthogonal Procrustes更新X和Z

为了求解变量X和Z，分别将模型(6-3)和(6-4)转化为以下两个子问题

(13)

(14)

可得X和Z的最优解分别为

(15)

(16)

求解模型(5)的算法如下：

算法：求解模型(5)的增广拉格朗日方法输入：数据矩阵W∈Rm×n，λ>0；初始化：令E=E0，X=X0，Y=Y0，Z=Z0，Λ=Λ0；步骤1：根据(8)式计算Yk+1；步骤2：根据(10)式和(12)式计算Ek+1；步骤3：根据(15)式计算Xk+1；步骤4：根据(16)式计算Zk+1；步骤5：根据(6⁃5)式更新拉格朗日乘子Λk+1；直到收敛；输出：Y∗=Yk+1，E∗=Ek+1，X∗=Xk+1，Z∗=Zk+1

3 数值实验

将提出的基于矩阵三分解方法的RMC模型应用于人脸识别的实际问题中，利用Yale-B人脸数据集中的Man face数据集和Woman face数据集，与原始RMC模型和使用RBF方法的RMC模型进行迭代次数、运行时间的比较。实验运行环境为Pentium E5500 2.77 GHz双核处理器，内存2.00 GB。所有算法程序均由Matlab R2014a编写。

3.1 参数设置

3.2 实验结果

将本研究提出的TFMC模型与RMC模型和使用RBF方法的RMC模型进行对比实验，迭代次数与运行时间的比较结果见表1。可见，在不同数据集中，本研究所用算法较RMC和RBF方法的迭代次数和运行时间均有很大程度的降低。

表1 迭代次数与运行时间的比较结果Tab.1 Comparison results of iteration times and running time

考虑到矩阵补全的目的是恢复含有损失函数的数据矩阵，因此为了进一步显示本文方法的有效性，Man face数据集取秩分别为10、12、15，Woman face数据集取秩分别为6、7、8进行数值实验。由图1、图2可以看出，本研究方法均可以比较完美的恢复原有的模样。另一方面，虽然已知数据的尺寸非常大，但由于本研究采用的矩阵三分解方法对问题进行了大幅度的降阶，使得当r较小时，算法的运算时间大大减少。Man face数据集中，当r=10,12,15时，算法的运算时间分别为62.1、76.5和83.2 s. Woman face数据集中，当r=6,7,8时，算法的运算时间分别为1.884、2.081和2.020 s。

其中Input-40表示输入的第40张原始图片；Mask中红色表示闭塞像素，黄色表示饱和像素；第一行的后三列表示秩为10、12、15的恢复图片；第二行后三列表示秩为10、12、15的噪声图片。图1 Manface数据集秩分别为10、12、15时对应的恢复效果图Fig.1 The recovered images from Man face data set’s rank-10, rank-12 and rank-15 factorization

其中Input-6表示输入的第6张原始图片；Mask中红色表示闭塞像素，黄色表示饱和像素；第一行的后三列表示秩为6、7、8的恢复图片；第二行后三列表示秩为6、7、8的噪声图片。图2 Woman face数据集秩分别为6、7、8时对应的恢复效果图Fig.2 The recovered images from Woman face data set’s rank-6, rank-7 and rank-8 factorization

4 总结

针对人脸识别中的矩阵补全模型，求解过程中存在计算复杂度过大的问题提出使用三分解方法降低计算的复杂度，并应用交替方向乘子法进行求解。数值实验结果表明，设计的模型迭代次数少，计算时间短。随着数据集中数据量的不断增大，本模型和算法将有更广阔的应用前景。

参考文献：

[1]彭义刚，索津莉，戴琼海，等.从压缩传感到低秩矩阵恢复:理论与应用[J].自动化学报，2013，39(7):981-994.

PENG Yigang,SUO Jinli，DAI Qionghai，et al.From compressed sensing to low-rank Matrix recovery:Theory and applications[J].Acta Automatica Sinica，2013，39(7):981-994.

[2]马坚伟, 徐杰, 鲍跃全,等. 压缩感知及其应用:从稀疏约束到低秩约束优化[J]. 信号处理, 2012, 28(5):609-623.

MA Jianwei，XU Jie，BAO yuequan，et al.Compressive sensing and its application: From sparse to low-rank regularized optimization[J]. Signal Processing，2012, 28(5):609-623.

[4]张婷婷.基于低秩矩阵填充与恢复的图像去噪方法研究[D].天津：河北工业大学，2015.

[6]SHI J，ZHENG X，YONG L.Incomplete robust principal component analysis[J].ICIC Express Letters.Part B，Applications:An International Journal of Research and Surveys，2014，5(6):1531-1538.

[7]SHANG F，LIU Y，TONG H，et al.Robust bilinear factorization with missing and grossly corrupted observations[J].Information Sciences，2015，307:53-72.

[8]XU Y，YIN W，WEN Z，et al.An alternating direction algorithm for matrix completion with nonnegative factors[J].Frontiers of Mathematics in China，2012，7(2):365-384.

[9]ZHENG Y，LIU G，SUGIMOTO S，et al.Practical low-rank matrix approximation under robust l1-norm[C]∥IEEE Conference on Computer Vision and Pattern Recognition (CVPR)，2012:1410-1417.

[10]DING C，LI T，PENG W，et al.Orthogonal nonnegative matrix t-factorizations for clustering[C]∥Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM，2006:126-135.

[11] LIU Y, JIAO L C, SHANG F. An efficient matrix factorization based low-rank representation for subspace clustering[J]. Pattern Recognition, 2013, 46(1):284-292.

[12]CAI J F，CANDS E J，SHEN Z.A singular value thresholding algorithm for matrix completion[J].SIAM Journal on Optimization，2010,20(4):1956-1982.