Abstract：Signal processing on graphs extends signal processing concepts and methodologies from the classical signal processing theory to data indexed by general graphs. For a band-limited graph signal, the unsampled data can be reconstructed from the sampled data by exploiting the relationship of the graph signals. This paper proposes a concept of graph diffusion operator for signal processing on graphs, and uses the operator to reconstruct band-limited graph signals from the sampled data. In each iteration, the residuals of the sampled vertices are propagated to all the unsampled vertices, and the known information and initial estimated results are further exploited via weighted process, aiming at accelerating the convergence. An analysis framework is proposed for the unsampled graph signals. The simulation results of synthetic data and real-world data demonstrate the wonderful effectiveness of the proposed reconstruction strategy.
SHUMAN D I, NARANG S K, and FROSSARD P. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains[J]. IEEE Signal Processing Magazine, 2013, 30(3): 83-98. doi: 10.1109/MSP.2012.2235192.
[2]
SANDRYHAILA A and MOURA J M F. Big data analysis with signal processing on graphs: Representation and processing of massive data sets with irregular structure[J]. IEEE Signal Processing Magazine, 2014, 31(5): 80-90. doi: 10.1109/MSP.2014.2329213.
[3]
CHEN Siheng, VARMA R, SANDRYHAILA A, et al. Discrete signal processing on graphs: Sampling theory[J]. IEEE Transactions on Signal Processing, 2015, 63(24): 6510-6523. doi: 10.1109/ TSP.2015.2469645.
[4]
MARQUES A G, SEGARRA S, LEUS G, et al. Sampling of graph signals with successive local aggregations[J]. IEEE Transactions on Signal Processing, 2016, 64(7): 1832-1843. doi: 10.1109/TSP.2015.2507546.
[5]
PESENSON I. Sampling in Paley-Wiener spaces on combinatorial graphs[J]. Transactions of the American Mathematical Society, 2008, 360(10): 5603-5627. doi: 10.1090 /S0002-9947-08-04511-X.
[6]
PAPOULIS A. A new algorithm in spectral analysis and band-limited extrapolation[J]. IEEE Transactions on Circuits and Systems, 1975, 22(9): 735-742. doi: 10.1109/TCS.1975. 1084118.
[7]
GERCHBERG R W. Super-resolution through error energy reduction[J]. Journal of Modern Optics, 1974, 21(9): 709-720. doi: 10.1080/713818946.
[8]
NARANG S K, GADDE A, and SANOU E. Localized iterative methods for interpolation in graph structured data[C]. IEEE Global Conference on Signal and Information Processing, Texas, USA, 2013: 491-494. doi: 10.1109/ GlobalSIP.2013.6736922.
[9]
ANIS A, GADDE A, and ORTEGA A. Towards a sampling theorem for signals on arbitrary graphs[C]. IEEE International Conference on Acoustics, Speech and Signal Processing, Florence, Italy, 2014: 3864-3868. doi: 10.1109/ ICASSP.2014.6854325.
[10]
WANG X, LIU P, and GU Y. Local-set-based graph signal reconstruction[J]. IEEE Transactions on Signal Processing, 2015, 63(9): 2432-2444. doi: 10.1109/TSP.2015.2411217.
[11]
WANG X, CHEN J, and GU Y. Generalized graph signal sampling and reconstruction[C]. IEEE Global Conference on Signal and Information Processing, Orlando, USA, 2015: 567-571. doi: 10.1109 /GlobalSIP.2015.7418259.
[12]
GLEICH D. The MatlabBGL Matlab Library[OL]. http://www.cs.purdue.edu/homes/dgleich/packages/matlab -bgl/index.html.2016.9.
[13]
SANDRYHAILA A and MOURA J. Discrete signal processing on graphs: Frequency analysis[J]. IEEE Transactions on Signal Processing, 2014, 62(12): 3042-3054. doi: 10.1109/TSP.2014.2321121.
[14]
SANDRYHAILA A and MOURA J. Discrete signal processing on graphs: graph Fourier transform[C]. IEEE International Conference on Acoustics, Speech and Signal Processing, Vancouver, Canada, 2013: 6167-6170. doi: 10.1109/ICASSP.2013.6638850.
[15]
WATTS D J and STROGATZ S H. Collective dynamics of ‘small-world’ networks[J]. Nature, 1998, 393(6684): 440-442. doi: 10.1038/30918.
[16]
BARABASI A L and ALBERT R. Emergence of scaling in random networks[J]. Science, 1999, 286(5439): 509-512. doi: 10.1126/science.286.5439.509.
[17]
SHANDONG BUREAU OF STATSTICS. Shandong Statistical Yearbook (2015)[OL]. http://www.stats-sd.gov. cn.2016.8.
