求解低秩矩阵填充的改进的交替最速下降法

Improved Alternating Steepest Descent Algorithms for Low Rank Matrix Completion

矩阵填充是指利用矩阵的低秩特性而由部分观测元素恢复出原矩阵,在推荐系统、信号处理、医学成像、机器学习等领域有着广泛的应用。采用精确线搜索的交替最速下降法由于每次迭代计算量小因而对大规模问题的求解非常有效。本文在其基础上采用分离地精确线搜索,可使得每次迭代下降更多但计算量相同,从而可望进一步提高计算效率。本文分析了新算法的收敛性。数值结果也表明所提出的算法更加有效。

Matrix completion is to recover a matrix from partial observed entries by utilizing the low rank property,which admits a large number of applications in recommender system,signal processing,medical imaging,machine learning,etc.Alternating steepest descent methods for matrix completion proposed recently have been shown to be efficient for large scale problems due to their low per iteration computational cost.In this paper,we use separately exact line search to improve the computational efficiency,so that the objective value obtained at the same computational cost at every iteration is smaller.A similar convergence analysis is also presented.The numerical results show that the proposed algorithms are superior to alternating steepest descent methods for low rank matrix completion.