追踪与广义近似消息传递

发布时间：2018-07-26 19:39

【摘要】：随着大数据时代的到来,人们对于高维数据处理技术的需求快速增长,有力推动了稀疏信号处理领域和压缩感知领域的研究进展,尤其是高效稀疏重构算法的开发。本文顺应这种需求,对传统的?0范数优化算法和近几年来受到越来越多重视的(广义)近似消息传递算法进行了研究,针对近似消息传递类型的算法对于非零均值小方差的高斯字典矩阵容易发散的问题,提出了三种改进的广义近似消息传递算法。其中,为了提出第二种改进的广义近似消息传递算法,前置提出了两种新型?0范数优化匹配追踪算法。第三种改进的广义近似消息传递算法则引入了利用稀疏向量各分量的边缘后验概率变化寻找非零元素下标的新型追踪过程,该追踪过程区别于匹配追踪所使用的残差与字典矩阵列计算相关的方式。本文主要创新点包括四个部分:1.提出了匹配追踪的广义近似消息传递算法,该方法通过标准的匹配追踪过程序贯地找出稀疏向量的非零位置,使用固定支撑集的广义近似消息传递算法估计非零位置的幅度。这种方法可以显著提高广义近似消息传递算法的稳健性。随后从构造树结构因子图的角度分析了该算法的收敛性。2.为了克服正交匹配追踪过程不能去除支撑集中找错的非零元素位置这个缺点,本文提出了两种随机扰乱和更新支撑集元素的新型匹配追踪算法,分别称为随机分裂支撑集正交匹配追踪和随机正则化匹配追踪,后者是对前者的改进。随后从理论上证明了随机正则化匹配追踪算法的收敛性,给出了收敛条件。3.根据前面两部分工作,将随机正则化匹配追踪算法与固定支撑集的广义近似消息传递算法结合起来,得到了随机正则化匹配追踪的广义近似消息传递算法。随后使用replica方法从理论上分析了固定支撑集的广义近似消息传递算法的收敛性和收敛条件。4.利用Bernoulli-Gaussian先验分布的广义近似消息传递算法在迭代过程中所估计的稀疏向量各个元素的边缘后验概率变化来找出支撑集,可以解释为一种追踪过程,再使用固定支撑集的广义近似消息传递算法进一步估计支撑集上的幅度。对于上述算法,本文使用了仿真数据和真实世界的数据作为算法的输入,考察和验证了这些算法的特性。实验结果表明,对于压缩感知问题,上述算法在更一般的字典矩阵条件下也能很好地恢复稀疏向量。
[Abstract]:With the arrival of big data era, the demand for high-dimensional data processing technology has increased rapidly, which has promoted the research progress of sparse signal processing and compression sensing, especially the development of efficient sparse reconstruction algorithm. In this paper, the traditional 0-norm optimization algorithm and the (generalized) approximate messaging algorithm, which have been paid more and more attention in recent years, are studied. Aiming at the problem that the approximate message passing type algorithm is easy to diverge for the Gao Si dictionary matrix with non-zero mean and small variance, three improved generalized approximate message passing algorithms are proposed. In order to propose a second improved generalized approximate messaging algorithm, two new matching and tracking algorithms with 0-norm optimization are proposed. The third improved generalized approximate messaging algorithm introduces a new tracking process which uses the edge posteriori probability change of each component of sparse vector to find non-zero element subscript. The tracking process is different from the way in which the residual errors used in matching tracing are related to the calculation of dictionary matrix columns. The main innovation of this paper includes four parts: 1. A generalized approximate message passing algorithm for matching tracing is proposed. By using the standard matching tracing program, the nonzero position of the sparse vector is found consistently, and the amplitude of the non-zero position is estimated by using the generalized approximate message passing algorithm with fixed support set. This method can significantly improve the robustness of generalized approximate messaging algorithm. Then the convergence of the algorithm is analyzed from the point of constructing the tree structure factor graph. In order to overcome the shortcoming that the orthogonal matching tracing process can not remove the position of non-zero elements in the support set, two new matching tracking algorithms are proposed to randomly disrupt and update the support set elements. They are called random split support set orthogonal matching tracing and random regularized matching tracing respectively. The latter is an improvement on the former. Then the convergence of the stochastic regularized matching tracking algorithm is proved theoretically, and the convergence condition is given. According to the previous two parts, the random regularization matching tracking algorithm is combined with the fixed support set generalized approximate message passing algorithm, and the generalized approximate message passing algorithm of random regularized matching tracking is obtained. Then the convergence and convergence conditions of the generalized approximate messaging algorithm with fixed support set are analyzed theoretically by using replica method. The generalized approximate message passing algorithm with Bernoulli-Gaussian prior distribution can be interpreted as a tracing process by using the edge posteriori probability variation of each element of the sparse vector estimated in the iterative process. Then the generalized approximate messaging algorithm of fixed support set is used to estimate the amplitude of the support set. For the above algorithms, the simulation data and the real world data are used as the input of the algorithms, and the characteristics of these algorithms are investigated and verified. The experimental results show that the proposed algorithm can recover the sparse vector well under the condition of more general dictionary matrix for the compressed perception problem.
【学位授予单位】：电子科技大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：TN911.7

【相似文献】