陈勇勇，王永丽，于慧慧

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



基于增广拉格朗日交替方向法的矩阵秩最小化算法研究

陈勇勇，王永丽，于慧慧

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

摘要：针对含有较大奇异值的矩阵秩最小化问题，采用对数行列式函数代替核范数作为秩函数的非凸近似，应用增广拉格朗日交替方向法求解矩阵秩最小化问题。当罚参数β>1时，证明此算法产生的迭代序列收敛到原问题的稳定点。最后利用实际数据和随机数据，通过数值实验验证所提出的算法较现有的求解核范数矩阵秩最小化问题的算法更高效。

关键词：对数行列式函数；核范数；增广拉格朗日交替方向法；低秩矩阵表示

1引言

考虑矩阵秩最小化问题

(1)

其中，X∈Rm×n，A∈Rp×m,B∈Rp×n是数据矩阵。

矩阵秩最小化问题在机器学习、数据挖掘、计算机视觉、图像处理、控制、生物信息学等领域有广泛的应用，由于求解此问题是NP-hard问题，学者们往往使用核范数作为矩阵秩函数的凸近似[15 ]，即通过求解如下核范数最小化问题来得到问题(1)的近似解：

(2)

(3)

求解核范数无约束最小化问题常用的算法有加速近似梯度法(accelerated proximal gradient method with line-search,APGL)[1]、增广拉格朗日法(augmented lagrangian method， ALM)[2]、交替方向乘子法(alternating direction method of multiplier,ADMM)[3,4]、坐标下降法(coordinate descent)[5]等。当矩阵的某些奇异值较大时，彭冲等[7]求解子空间聚类问题时发现，利用对数行列式函数对矩阵秩函数进行近似的效果较好，而核范数的近似效果较差。基于此，本文用对数行列式函数代替核范数作为矩阵秩函数的近似，同时考虑到对数行列式函数的非凸性，应用增广拉格朗日交替方向法求解问题(3)，提出一个新的算法，在适当条件下证明了算法的收敛性，并通过实例验证了算法的有效性。