高维低秩矩阵填充问题相关算法及应用研究

发布时间：2020-06-09 17:07

【摘要】：矩阵填充的目标是利用矩阵中少量的已知元素准确地恢复出其它未知的元素,在推荐系统、计算机视觉等领域都有着非常普遍且重要的应用。随着数据规模的增大,许多经典的矩阵填充算法已经无法适应于大数据时代的高维矩阵填充问题,因此迫切地需要更加高效以及能够进行分布式计算的矩阵填充算法。一方面可以对经典的算法进行改进,以使其具有更高的效率,从而能够处理规模更大的矩阵。另一方面可以寻求能够将大数据问题划分为多个小的子问题的方法,从而使得经典的算法可以直接用于求解这些子问题,最终再合并得到原问题的解。本文分别从这两个角度进行深入研究,提出能够高效地求解高维矩阵填充问题的算法。利用求解主成分分析的期望最大化方法,本文在经典的奇异值投影算法的基础上提出一种更加高效的矩阵填充算法。期望最大化算法使用一种交替下降的优化方法求解矩阵的主成分空间,从而避免了耗时的奇异值分解,同时也可以较容易地实现并行计算。利用矩阵填充问题中矩阵稀疏加低秩的结构特点,期望最大化算法的时间复杂度与矩阵中的已知元素的个数呈线性关系。另外,经典的奇异值投影算法需要指定矩阵的秩,本文提出一种改进的奇异值边缘分布算法,该方法能够有效地从很少的已知元素恢复出矩阵的秩。上述改进策略显著地提升了经典的奇异值投影算法的性能,从而可以更好地适应于高维的矩阵填充问题。在大部分的真实数据中,已知元素在矩阵中的位置是不均匀分布的,但是大部分的矩阵填充算法却建立在元素均匀分布的假设之上。帕累托原理指出,少部分的因素决定了大部分的结果。本文受到这一原理的启发,使用矩阵中最重要的一些行和列的因子近似代表整个矩阵的行和列的因子,从而提出一种分布式的矩阵填充算法。该算法首先从原始矩阵中选择一个最重要的子矩阵,然后使用经典的矩阵填充算法求解该子矩阵,最后利用子矩阵的解得到原矩阵的解。本文根据自然语言处理中的词频-逆文档频率概念,提出一种用于衡量矩阵行和列的重要性的方法。使用该方法选择出的子矩阵能够非常准确地保留原矩阵的特征,从而有效地解决了矩阵中元素分布不均匀的问题。另外,由于该算法的分治特点,使得其可以高效地用于求解高维矩阵填充问题。最后,本文将上面提到的分布式矩阵填充算法应用于视频背景建模问题中,提出一种基于矩阵填充的背景建模方法。该方法首先利用背景总是最经常被观测到的假设,将视频图像中可能为前景物体的像素点进行删除,从而得到一个包含缺失像素的图像序列。然后使用分布式的矩阵填充算法对去除前景物体之后的图像进行填充,从而完成背景的重建。在填充步骤中,本文针对背景建模问题的特点提出一种衡量像素和图像重要性的方法,通过这些最重要的像素和图像可以更加准确地恢复视频的背景。从大量实验中可以得出,本文提出的背景建模算法能够有效地处理各种极端情况下的视频场景。此外,该算法的效率很高,非常适合于处理高分辨率的视频背景建模问题。
【图文】：

视频,帧图像,像素点,样本方差

为像素点的灰度值均值。一个像素点的样本方差越小，，则其灰度值就越稳定，该点就越有可能一直处于背景状态。当某个像素点始终处于固定背景状态时，该点的灰度值样本方差为 0，例如 Hall 视频中的背景墙壁（图5 1(b)中的蓝色位置）— 74 —

示意图,视频,帧图像,像素

为像素点的灰度值均值。一个像素点的样本方差越小，则其灰度值就越稳定，该点就越有可能一直处于背景状态。当某个像素点始终处于固定背景状态时，该点的灰度值样本方差为 0，例如 Hall 视频中的背景墙壁（图5 1(b)中的蓝色位置）— 74 —
【学位授予单位】：上海交通大学
【学位级别】：博士
【学位授予年份】：2018
【分类号】：TP391.3;TP181

【相似文献】