矩阵填充的算法研究

发布时间：2018-04-25 00:24

本文选题：矩阵填充 + Tbeplitz矩阵　；参考：《太原理工大学》2017年硕士论文

【摘要】：矩阵填充问题就是从有限的信息中重构低秩或者近似低秩矩阵的问题,是近年来国际国内在信号处理领域的研究热点之一.而在实际应用中采样矩阵有时为普通矩阵有时则具有Hankel及Toeplitz等结构的特殊矩阵,同时Toeplitz矩阵在信号和图像处理中发挥着重要的作用.故本文分别对Toeplitz矩阵和普通矩阵的矩阵填充问题进行了较深入的研究.通过对矩阵填充问题的研究总结,我们发现现有的大多数算法都需要计算矩阵的奇异值分解,同时通过数值实验我们也发现,奇异值阈值是算法中主要的耗时部分.因此,对于Toeplitz阵的填充问题,我们根据普通矩阵的奇异值分解算法复杂度为O(n3)而Toeplitz矩阵的快速奇异值分解算法的复杂度仅为O(n2logn),并通过在左奇异向量空间中对已知元素的最小二乘逼近,形成了新的可行矩阵,最后利用对角线上的均值化使得迭代后的矩阵保持Toeplitz结构,从而减少了奇异向量空间的分解时间.对于普通矩阵的填充问题,我们基于最速下降算法提出了一种两阶迭代最速下降算法:先在内层迭代中找到最佳逼近矩阵或近似最佳逼近矩阵,然后在外层迭代中找到r维最优流形.理论上,证明了在一定条件下两类新算法均是收敛的,并通过大量数值实验验证了两类新算法的合理性和优越性.通过对实验结果的比较,我们可以发现新算法降低了计算所需的CPU时间,这将有利于求解大规模的普通矩阵和Toeplitz矩阵的填充问题,在实际应用中节约了时间降低了成本.
[Abstract]:Matrix filling problem is the problem of reconstruction of low rank matrix or approximate low rank matrix from limited information. It is one of the research hotspots in the field of signal processing at home and abroad in recent years. In practical applications, the sampling matrix is sometimes a common matrix, sometimes a special matrix with Hankel and Toeplitz structure, and the Toeplitz matrix plays an important role in signal and image processing. Therefore, the matrix filling problem of Toeplitz matrix and ordinary matrix is studied in this paper. Based on the study of matrix filling problem, we find that most of the existing algorithms need to calculate the singular value decomposition of the matrix. At the same time, through numerical experiments, we also find that the singular value threshold is the main time-consuming part of the algorithm. Therefore, for the filling problem of Toeplitz arrays, According to the complexity of singular value decomposition (SVD) algorithm of ordinary matrix is ON3) and the complexity of fast SVD algorithm of Toeplitz matrix is only ON2lognan, we form a new feasible matrix by the least square approximation of known elements in the left singular vector space. Finally, the Toeplitz structure of the iterative matrix is kept by means of the mean value on the diagonal line, thus reducing the decomposition time of the singular vector space. For the filling problem of ordinary matrices, we propose a two-order iterative steepest descent algorithm based on the steepest descent algorithm: first, we find the best approximation matrix or approximate best approximation matrix in the inner iteration. Then the r-dimensional optimal manifold is found in the outer iteration. In theory, it is proved that the two new algorithms are convergent under certain conditions, and the rationality and superiority of the two new algorithms are verified by a large number of numerical experiments. By comparing the experimental results, we can find that the new algorithm reduces the CPU time required for computation, which is helpful to solve the filling problem of large scale ordinary matrix and Toeplitz matrix, and saves time and cost in practical application.
【学位授予单位】：太原理工大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O151.21

【参考文献】