关于矩阵的Rank-revealing分解及应用开题报告

1. 研究目的与意义

随机算法是一种使用概率和统计方法在其执行过程中对于下一计算步骤作出随机选择的算法。矩阵低秩逼近算法是近年来许多学者研究的热点问题，其在日常生活中的各方面也得到了广泛应用，例如图像识别、图像压缩等。矩阵分解是将矩阵拆解为数个矩阵的乘积，具体可分为三角分解、满秩分解、qr分解、jordan分解和svd（奇异值）分解等，矩阵分解在矩阵理论分析和矩阵计算中具有重要的作用，同时矩阵的rank-revealing分解的数值计算是在矩阵分解中一个有趣且有意义的问题，也是近年来学者们研究的热点问题。随着近年来大数据时代的发展，传统的矩阵低秩逼近算法，例如低秩矩阵恢复（鲁棒主成分分析）、奇异值分解（svd）、qr分解等算法，已经无法满足现代的发展要求，于是需要一种新的矩阵低秩逼近的随机算法来为svd算法提供一个强大有效的工具。与传统的矩阵低秩逼近分解算法相比，随机算法更加简单、鲁棒性更强并且运行效率更高，最终占用的运行内存空间更小。矩阵低秩逼近算法也可以运用在多个方面，例如人脸识别、图像压缩、图像识别等，通过提取图像的显著性特征从而实现图片识别的成功率，也可以节省一定的数据存储空间。

本课题学习了低秩矩阵恢复算法以及基于奇异值分解的矩阵低秩逼近技术，同时还学习了基于随机抽样的矩阵低秩逼近技术，并且对该方法进行程序编写。首先，可由r. a. horn和c. r. johnson的 matrix analysis[1]、李庆扬等的数值分析[2]以及r. l. burden 和 j. d. faires的数值分析[3]中了解到矩阵的分解问题；在eckarth和 young的theapproximation of one matrix by another of lower rank. psychometrika[5] 中学习了有关奇异值分解的基本原理，在m. gu 和s. c. eisenstat在 efficient algorithms forcomputing a strong rank-revealing qr factorization[6]中介绍了关于矩阵低秩逼近的有效算法，为学习矩阵低秩逼近的随机化方法提供一定的理论基础；在 n. halko, p.-g. martinsson和j. a. tropp的finding structure withrandomness: probabilistic algorithms for constructing approximate matrixdecompositions[7]中介绍了低秩矩阵近似，例如截断奇异值分解和rank-revealing的qr分解，其中随机分布为执行低秩矩阵近似提供了强大工具。而后有p. g. martinsson 和 s. voronin.在 a randomized blockedalgorithm for efficiently computing rank-revealing factorizations of matrices[8]中描述了矩阵的分解方法，并且提出了矩阵的分解与矩阵的秩有很大关系，通过对这些原理的了解再学习rokhlin, v.等在a randomized algorithm for principal componentanalysis[9]提出的矩阵低秩逼近的随机化算法是很有必要的。在学习过矩阵低秩逼近的随机化算法后进行程序编写，最终运用到实际中，以展示出我们学习的算法的有效性。

2. 研究内容和问题

基本内容：

随机算法是近年来许多学者研究的热点问题，矩阵分解在矩阵理论分析和矩阵计算中具有重要的作用，矩阵的rank-revealing分解的数值计算是一个有趣且有意义的问题。本课题拟学习矩阵列空间随机抽取技术以及如何利用矩阵列空间随机抽取技巧有效地计算矩阵的rank-revealing分解，以此对矩阵的rank-revealing分解的随机计算方法做一个细致的了解。

预计解决的难题：

3. 设计方案和技术路线

（1）查阅有关文献和资料，了解相关的基础知识；

（2）熟悉矩阵的rank-revealing分解的随机算法并给出相应的程序代码；

（3）给出相关的应用。

4. 研究的条件和基础

本课题的指导者近年来主要从事数值代数及统计计算方面的研究，对所从事的研究方向的发展有一定的了解。

统计专业的学生具备一定的概率统计以及数值优化的相关知识，并具有一定的计算机应用能力和文献检索能力；学校图书馆和校园网有比较丰富的图书资料。

综上所述，完成本课题研究的基本条件已基本具备。