基于矩阵恢复问题的黎曼流形上的牛顿法和改进的奇异值阈值算法

摘要

本文研究低秩矩阵的恢复问题，其在推荐系统、计算机视觉等领域得到了广泛的关注。它是通过给定矩阵的部分元素，然后求出矩阵中所有未知的元素。这本身是带约束的最优化问题，但也可以看成是黎曼流形上的无约束问题。目前，解决低秩矩阵恢复问题的方法有很多，如奇异值阈值算法(SVT)、黎曼流形上的共轭梯度算法(LRGeomCG)、APG算法等，各有各的优势以及使用的领域。当矩阵的规模不太大时，SVT算法是比较高效的，但阈值的选取仍有改进的地方;当矩阵规模很大时，LRGeomCG算法的效率很高，但它的一个缺点是事先得给出待恢复矩阵的秩或者秩的估计值。另外，对于在黎曼流形上解决低秩矩阵恢复问题的其他最优化方法也值得探讨。所以本文针对这些方面，对已有的算法进行了改进和补充。具体来说，本文的创新有以下几点:
　　1.在第三章3，针对低秩矩阵恢复问题，提出在秩为k的矩阵空间上应用牛顿法，即运用黎曼流形上的牛顿法加以解决，其中最关键的步骤是推导出目标函数的Riemannian-Hessian算子。在此基础上，我们推导出黎曼流形上其他优化方法的具体过程:梯度下降法、拟牛顿法。这样一来针对矩阵恢复问题，得出了常用的黎曼流形的最优化方法（文章中统称为LRGeom算法），我们可以根据自身的需要加以选用。
　　2.在黎曼流形上的最优化方法中，我们是在秩为k的矩阵空间中进行求解的，但问题是矩阵的秩是未知的，在第四章4中我们提出使用Opt-Space算法和黎曼流形上的最优化方法加以结合，克服这个缺点。并与SVT算法加以比较，给出了具体的实验数据，有力地说明这一算法在精度、收敛速度方面的优势。
　　3.在第五章5中，我们详细地研究了SVT算法如何过滤奇异值的问题，给出了Armijo-SVT算法和LM-SVT算法这两种改进方案，并对收敛性进行了证明。最后与SVT算法进行了对比实验分析，证明了我们的算法有着更好的精度和更强的鲁棒性。

目录

声明

摘要

第一章 引言

1．1 研究背景

1．2 问题描述

1．3 可行性分析

1．4 算法介绍

第二章 黎曼流形上的共轭梯度算法

2．1 黎曼流形

2．2 共轭梯度法的原理和一般步骤

2．3 黎曼流形上的共轭梯度算法

第三章 黎曼流形上的牛顿法和其它方法

3．1 牛顿法的原理和一般步骤

3．2 黎曼流形上的牛顿法

3．3 黎曼流形上的拟牛顿法和梯度下降法

第四章 改进后的黎曼流形上的最优化方法

4．1 Opt-Space算法估计待恢复矩阵的秩

4．2 改进后的黎曼流形上的最优化方法：Opt-Space+LRGeom算法

4．3 Opt-Space+LRGeom算法与SVT算法的比较

第五章 改进后的奇异值阈值算法

5．1 奇异值阈值算法介绍

5．2 改进后的奇异值阈值算法：Armijo-SVT算法

5．3 改进后的奇异值阈值算法：LM-SVT算法

第六章 总结与展望

6．1 总结

6．2 展望

参考文献

致谢