Time-Varying Graph Signal Reconstruction

Signal processing on graphs is an emerging research field dealing with signals living on an irregular domain that is captured by a graph, and has been applied to sensor networks, machine learning, climate analysis, etc. Existing works on sampling and reconstruction of graph signals mainly studied static bandlimited signals. However, many real-world graph signals are time-varying, and they evolve smoothly, so instead of the signals themselves being bandlimited or smooth on graph, it is more reasonable that their temporal differences are smooth on graph. In this paper, a new batch reconstruction method of time-varying graph signals is proposed by exploiting the smoothness of the temporal difference signals, and the uniqueness of the solution to the corresponding optimization problem is theoretically analyzed. Furthermore, driven by practical applications faced with real-time requirements, huge size of data, lack of computing center, or communication difficulties between two nonneighboring vertices, an online distributed method is proposed by applying local properties of the temporal difference operator and the graph Laplacian matrix. Experiments on a variety of synthetic and real-world datasets demonstrate the excellent performance of the proposed methods.

I. Introduction

Graph signal processing is a new research direction that has received extensive attention in recent years [1]–[3]. It mainly analyzes signals living on an irregular domain that is captured by a graph, and has found wide applications in sensor networks [4], [5], machine learning [6]–[8], image processing [9], [10], biomedical fields [11]–[13], climate analysis [14]–[16], et cetera. Existing research topics of graph signal processing include graph filtering [17], [18], graph signal compression [19], [20], graph signal coarsening [21], [22], stationary graph signal processing [23]–[25], graph signal sampling and reconstruction [26]– [28], et cetera.