Graph Signal Denoising Method Using the K-Nearest Neighbors Found by Dijkstra's Algorithm
Chien‐Cheng Tseng, Su‐Ling Lee · 2021
In this paper, graph signal denoising problem is investigated. First, conventional graph signal denoising method using graph Laplacian matrix (GLM) is described to show that a big matrix inversion is needed in this method. To reduce computational load, a modified Dijkstra's algorithm is presented to find the K-nearest neighbors (K-NN) of a given vertex in the graph and a local graph Laplacian matrix (LGLM) of the sub-graph around this vertex is constructed by using the K-NN information and graph adjacency matrix. Then, based on the local smoothness property of graph signal and LGLM, the denoised signal at the given vertex can be computed by a Cramer's rule method. Finally, real temperature data is used to show the effectiveness of the proposed denoising method and performance comparison with conventional method is made.