基于随机算法的矩阵低秩逼近及应用开题报告

1. 研究目的与意义

目前，低秩逼近已经成为在数据中提取信息的最热门的方法之一，在信号处理、生物工程、心理学等领域有广泛的应用，成为机器学习、模式识别等领域的研究热点。然而，如何从结构复杂的数据中挖掘所需要的关键信息，并将其应用在解决实际问题上检验其有效性，进而改进现有算法或设计新型算法，仍是面临的极大挑战。因此，低秩逼近问题受到越来越多学者的关注，研究如何快速有效的计算矩阵的低秩逼近也具有十分重要的研究意义和实际的应用价值，从总体来看，这仍是一个开放的领域，期待更广泛的应用研究。

目前，对于矩阵低秩逼近问题研究中基于随机算法的内容越来越多，当然依旧存在很多传统方法来研究矩阵低秩逼近问题和应用。王淑琴2019年在《低秩矩阵逼近模型的改进及应用研究》中研究了低秩矩阵逼近模型在高光谱图像去噪、背景前景分割、及彩色图像重建等领域中的应用。通过矩阵分解实现低秩约束,大大降低了计算成本,同时分别采用两个非凸函数代替核范数逼近原始秩函数,提高了模型的鲁棒性和灵活性。米合拉衣·阿地勒在2020年发表的《稳定广义低秩逼近算法》从另一个数学角度出发,提出了一种基于新概念的广义低秩逼近算法。文中分别系统地论述和研究了一种广义低秩矩阵的逼近算法和鲁棒广义低秩矩阵的逼近理论模型。为了进一步增强对一个广义的低秩矩阵进行逼近求解后计算得到的鲁棒性与稳定性,提出了一种稳定的广义低秩矩阵的逼近理论模型与逼近算法。任意一个数据矩阵都能被他提出的理论模型分解成三个成分之和，三个成分分别是低秩成分、稀疏噪声、稠密高斯噪声。为了进一步恢复低秩矩阵,建立了最小化矩阵 quote 范数与frobenious范数的优化问题。王朦2018年在《整数矩阵低秩逼近及其应用》中做了一些大数据挖掘实验,包括如何对随机过程产生的整数矩阵进行逼近,对关联规则挖掘、聚类分析、模型的提取方法等相关问题上的实证研究。喻丁玲2021年在《复杂场景中的运动目标检测算法研究》提出了一种改进的在线随机张量分解应用在多光谱视频序列的框架,在张量模式上迭代更新基矩阵和稀疏部分系数,实现在线实时优化。陈帅、赵明、郭栋、林京2021年在《基于svd-kdr算法的工业监测数据插补技术》提出一种基于svd-kdr的高精度、高鲁棒性缺失数据插补算法。该方法将一维工业数据转换为高维矩阵,弥补了传统方法直接从低维空间插补工业监测数据的维度局限。通过发掘插补过程中非缺失数据的低秩特性,借助奇异值分解理论建立了鲁棒性更强的svd-kdr算法模型,有效减弱了缺失数据对参数估计精度的不利影响。李德志在2020年首次提出了基于多单秩矩阵逼近的低秩矩阵分解模型,并且专门针对多单秩矩阵数量r的估计提出了迭代差分峰值检测法,最后将提出的算法成功应用到实际项目的钢轨缺陷检测中。基于以上研究，我们了解了许多矩阵低秩逼近的相关应用，为了克服传统确定性方法的高计算复杂度，我们可以将随机算法应用到计算矩阵低秩逼近问题中。郭雄伟、王川龙2021年在《低秩张量填充的随机算法》中提出了一种新的高精度低秩张量填充随机算法，简称lrtcr。该算法在原有的算法的基础上，引入随机的思想，有效地降低了算法在每次迭代过程中的计算花费。lebedeva o. s.，osinsky a. i.，petrov s. v.在《low-rank approximation algorithms for matrix completion with randomsampling》中用快速逼近算法取代frobenius范数中的最佳逼近程序。考虑了两种近似计算方法:(a)投影到随机子空间 (b)交叉近似方法。证明了具有近似投影算法的几何收敛性定理。per-gunnar martinsson，sergey voronin在《a randomized blockedalgorithm for efficiently computing rank-revealing factorizations of matrices》中描述了一种秩揭示的分解方法，例如部分qr因子分解或部分奇异值分解。该方法以误差e和m × n矩阵a作为输入，并返回a的近似低秩分解，该分解精确到frobenius范数(或其他一些容易计算的范数)精度e以内。计算的秩k因子分解(这是算法的输出)都非常接近理论上的最优解。该方法受gram-schmidt算法的启发，具有o(mnk) ftop数。该方法依赖于随机抽样，通过减少访问a来加速实际计算。 halko n , martinsson p g , tropp j a 在2011年提出了一个模块化框架来构造计算部分矩阵分解的随机算法。这些方法使用随机抽样来捕获矩阵值域空间。然后，将矩阵压缩后，通过对低维矩阵进行操作，以获得所需的低秩分解。tropp j a , yurtsever a ,udell m , et al 2017年在《practicalsketching algorithms for low-rank matrix approximation》描述了一套算法，通过对矩阵的随机抽样构造该矩阵的低秩近似，称为一个sketching。这些方法可以保留输入矩阵的结构属性，如半正定，并且可以产生用户指定秩的近似。boutsidis,christos, gittens, et al 2013年在《improvedmatrix algorithms via the subsampled randomized hadamard transform》中讨论了基于srht的低秩矩阵逼近技术的功效。建立了一个比目前可用的略好一些的frobenius范数误差界，以及一个更清晰的谱范数误差界(在存在合理的奇异值衰减的情况下)。

本文基于随机算法的矩阵低秩逼近以及相关的应用，学习子抽样随机傅里叶变换，给出基于子抽样随机傅里叶变换的矩阵低秩逼近程序并且讨论其相关的应用。

2. 研究内容和问题

基本内容：

矩阵的低秩逼近在图像处理、机器学习、数据分析以及数值优化等领域有着广泛的应用，因此研究如何快速有效的计算矩阵的低秩逼近具有十分重要的研究意义和实际的应用价值。随机算法是近年来学者研究的热点，为了克服传统确定性方法的高计算复杂度，我们可以将随机算法应用到计算矩阵低秩逼近问题中。本课题拟学习基于随机算法的矩阵低秩逼近以及相关的应用，以此对矩阵低秩逼近问题做一个比较细致的了解。

研究目标：学习子抽样随机傅里叶变换，给出基于子抽样随机傅里叶变换的矩阵低秩逼近算法程序并且讨论相关的应用。

3. 设计方案和技术路线

(1)查阅有关文献和资料，了解相关的基础知识；(2)熟悉子抽样随机傅里叶变换并给出基于此抽样方法计算矩阵低秩逼近的相应程序代码；(3)给出相关的应用。

4. 研究的条件和基础

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

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

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