一种改进的加权图信号传播重构算法

An improved propagation reconstruction algorithm for weighted graph signals

针对实际问题中图信号处理大多是基于加权图的情况,提出一种新的加权图带限信号传播重构算法。通过采样在加权图中划分局部集,在信号传播过程中考虑受到权的影响,从而在局部集中建立新的传播方式,基于此传播方式建立迭代重构算法。数值实验表明,无权图中提出的迭代最小二乘重构算法和迭代传播重构算法仍然能用于恢复加权图中的带限信号,但相比之下,改进的算法具有更快的收敛速度和较好的抗噪性,且利用单跳采样能提高算法收敛速度。

To deal with signal processing on weighted graphs frequently occurred in practical problems, a new propagation re- construction algorithm is proposed for band limited signals on a weighted graph. Local sets are divided on a weighted graph by sampling. Considering the influence of weights in the process of propagation, a new propagation mode in local sets is de fined and an iterative algorithm is established to reconstruct band-limited signals. Numerical results show that iterative least squares reconstruction algorithm and iterative propagation reconstruction algorithm on unweighted graphs can still recon struct band limited signals on a weighted graph, but the improved algorithm has faster convergence rate and better noise re- sistance relatively, and one hop sampling can improve the convergence rate.