Spectral Estimation for Graph Signals Using Reed-Solomon Decoding

Spectral estimation, coding theory and compressed sensing are three important sub-fields of signal processing and information theory. Although these fields developed fairly independently, several important connections between them have been identified. One notable connection between Reed-Solomon(RS) decoding, spectral estimation, and Prony's method of curve fitting was observed by Wolf in 1967. With the recent developments in the area of Graph Signal Processing(GSP), where the signals of interest have high dimensional and irregular structure, a natural and important question to consider is can these connections be extended to spectral estimation for graph signals? Recently, Marques et al, have shown that a bandlimited graph signal that is k-sparse in the Graph Fourier Transform (GFT) domain can be reconstructed from 2k measurements obtained using a dynamic sampling strategy. Inspired by this work, we establish a connection between coding theory and GSP to propose a sparse recovery algorithm for graph signals using methods similar to Berlekamp-Massey algorithm and Forney's algorithm for decoding RS codes. In other words, we develop an equivalent of RS decoding for graph signals. The time complexity of the recovery algorithm is O(k^2) which is independent of the number of nodes N in the graph. The proposed framework has applications in infrastructure networks like communication networks, power grids etc., which involves maximization of the power efficiency of a multiple access communication channel and anomaly detection in sensor networks