research-article

Local-Set-Based Graph Signal Reconstruction

Authors:

Yuantao GuAuthors Info & Claims

IEEE Transactions on Signal Processing, Volume 63, Issue 9

Pages 2432 - 2444

https://doi.org/10.1109/TSP.2015.2411217

Published: 01 May 2015 Publication History

Abstract

Signal processing on graph is attracting more and more attentions. For a graph signal in the low-frequency subspace, the missing data associated with unsampled vertices can be reconstructed through the sampled data by exploiting the smoothness of the graph signal. In this paper, the concept of local set is introduced and two local-set-based iterative methods are proposed to reconstruct bandlimited graph signal from sampled data. In each iteration, one of the proposed methods reweights the sampled residuals for different vertices, while the other propagates the sampled residuals in their respective local sets. These algorithms are built on frame theory and the concept of local sets, based on which several frames and contraction operators are proposed. We then prove that the reconstruction methods converge to the original signal under certain conditions and demonstrate the new methods lead to a significantly faster convergence compared with the baseline method. Furthermore, the correspondence between graph signal sampling and time-domain irregular sampling is analyzed comprehensively, which may be helpful to future works on graph signals. Computer simulations are conducted. The experimental results demonstrate the effectiveness of the reconstruction methods in various sampling geometries, imprecise priori knowledge of cutoff frequency, and noisy scenarios.

References

[1]

D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega, and P. Vandergheynst, “The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains,” in IEEE Signal Process. Mag., vol. 30, no. 3, pp. 83–98, May 2013.

[2]

A. Sandryhaila and J. M. F. Moura, “Discrete signal processing on graphs,” in IEEE Trans. Signal Process., vol. 61, no. 7, pp. 1644–1656, 2013.

Digital Library

[3]

X. Zhu and M. Rabbat, “Graph spectral compressed sensing for sensor networks,” in Proc. 37th IEEE Int. Conf. Acoust., Speech, Signal Process. (ICASSP), 2012, pp. 2865–2868.

[4]

S. K. Narang, Y. H. Chao, and A. Ortega, “Graph-wavelet filterbanks for edge-aware image processing,” in Proc. IEEE Statist. Signal Process. Workshop (SSP'12), 2012, pp. 141–144.

[5]

A. Gadde, A. Anis, and A. Ortega, “Active semi-supervised learning using sampling theory for graph signals,” in Proc. 20th ACM SIGKDD Int. Conf. Knowledge Discovery Data Mining (KDD'14), 2014, pp. 492–501.

[6]

S. K. Narang, A. Gadde, and A. Ortega, “Signal processing techniques for interpolation in graph structured data,” in Proc. 38th IEEE Int. Conf. Acoust., Speech, Signal Process. (ICASSP), 2013, pp. 5445–5449.

[7]

F. Zhang and E. R. Hancock, “Graph spectral image smoothing using the heat kernel,” in Pattern Recognit., vol. 41, no. 11, pp. 3328–3342, 2008.

Digital Library

[8]

S. Chen, A. Sandryhaila, J. M. F. Moura, and J. Kovacevic, “Adaptive graph filtering: Multiresolution classification on graphs,” in Proc. 1st IEEE Global Conf. Signal Inf. Process. (GlobalSIP), 2013, pp. 427–430.

[9]

M. Crovella and E. Kolaczyk, “Graph wavelets for spatial traffic analysis,” in Proc. 22nd Annu. IEEE Int. Conf. Comput. Commun. (INFOCOM'03), 2003, vol. 3, pp. 1848–1857.

[10]

R. R. Coifman and M. Maggioni, “Diffusion wavelets,” in Appl. Comput. Harmonic Anal., vol. 21, no. 1, pp. 53–94, 2006.

[11]

D. K. Hammond, P. Vandergheynst, and R. Gribonval, “Wavelets on graphs via spectral graph theory,” in Appl. Comput. Harmonic Anal., vol. 30, no. 2, pp. 129–150, 2011.

[12]

S. K. Narang and A. Ortega, “Perfect reconstruction two-channel wavelet filter-banks for graph structured data,” in IEEE Trans. Signal Process., vol. 60, no. 6, pp. 2786–2799, Jun. 2012.

Digital Library

[13]

A. Agaskar and Y. M. Lu, “A spectral graph uncertainty principle,” in IEEE Trans. Inf. Theory, vol. 59, no. 7, pp. 4338–4356, Jul. 2013.

Digital Library

[14]

D. I. Shuman, M. J. Faraji, and P. Vandergheynst, “A Framework for Multiscale Transforms on Graphs,”, 2013,.

[15]

V. N. Ekambaram, G. C. Fanti, B. Ayazifar, and K. Ramchandran, “Multiresolution graph signal processing via circulant structures,” in Proc. IEEE Digital Signal Process., Signal Process. Educ. Meeting (DSP/SPE), 2013, pp. 112–117.

[16]

X. Zhu and M. Rabbat, “Approximating signals supported on graphs,” in Proc. 37th IEEE Int. Conf. Acoust., Speech, Signal Process. (ICASSP), 2012, pp. 3921–3924.

[17]

S. K. Narang, A. Gadde, E. Sanou, and A. Ortega, “Localized iterative methods for interpolation in graph structured data,” in Proc. 1st IEEE Global Conf. Signal Inf. Process. (GlobalSIP), 2013, pp. 491–494.

[18]

A. Anis, A. Gadde, and A. Ortega, “Towards a sampling theorem for signals on arbitrary graphs,” in Proc. 39th IEEE Int. Conf. Acoust., Speech, Signal Process. (ICASSP), 2014, pp. 3892–3896.

[19]

D. Thanou, D. I. Shuman, and P. Frossard, “Parametric dictionary learning for graph signals,” in Proc. 1st IEEE Global Conf. Signal Inf. Process. (GlobalSIP), 2013, pp. 487–490.

[20]

X. Dong, D. Thanou, P. Frossard, P, and P. Vandergheynst, “Learning Graphs from Signal Observations Under Smoothness Prior,”, 2014,.

[21]

P. Liu, X. Wang, and Y. Gu, “Coarsening graph signal with spectral invariance,” in Proc. 39th IEEE Int. Conf. Acoust., Speech, Signal Process. (ICASSP), 2014, pp. 1075–1079.

[22]

S. Chen et al., “Signal inpainting on graphs via total variation minimization,” in Proc. 39th IEEE Int. Conf. Acoust., Speech, Signal Process. (ICASSP), 2014, pp. 8267–8271.

[23]

I. Pesenson, “Sampling in Paley-Wiener spaces on combinatorial graphs,” in Trans. Amer. Math. Soc., vol. 360, no. 10, pp. 5603–5627, 2008.

[24]

I. Pesenson, “Variational splines and Paley-Wiener spaces on combinatorial graphs,” in Constructive Approx., vol. 29, pp. 1–21, 2009.

[25]

I. Z. Pesenson and M. Z. Pesenson, “Sampling, filtering and sparse approximations on combinatorial graphs,” in J. Fourier Anal. Appl., vol. 16, no. 6, pp. 921–942, 2010.

[26]

H. Führ and I. Z. Pesenson, “Poincaré and plancherel-polya inequalities in harmonic analysis on weighted combinatorial graphs,” in SIAM J. Discrete Math., vol. 27, no. 4, pp. 2007–2028, 2013.

[27]

D. I. Shuman, B. Ricaud, and P. Vandergheynst, Vertex-Frequency Analysis on Graphs, Amsterdam, The Netherlands: Elsevier, 2013, no. EPFL-ARTICLE-187669.

[28]

D. I. Shuman, C. Wiesmeyr, N. Holighaus, and P. Vandergheynst, “Spectrum-adapted tight graph wavelet and vertex-frequency frames,” in Inst. Elect. and Electron. Eng., 2013, no. EPFL-ARTICLE-190280.

[29]

F. R. K. Chung, “Spectral Graph Theory,”, 1997, Amer. Math. Soc.

[30]

O. Christensen, An Introduction to Frames and Riesz Bases, Berlin, Germany: Springer-Verlag, 2003.

[31]

X. Wang, M. Wang, and Y. Gu, “A distributed tracking algorithm for reconstruction of graph signals,” in IEEE J. Sel. Topics Signal Process., June 2015,.

[32]

H. G. Feichtinger and K. Gröchenig, “Theory and practice of irregular sampling,” in Wavelets: Math. Appl., pp. 305–363, 1994.

[33]

K. Gröchenig, “A discrete theory of irregular sampling,” in Linear Algebra Appl., vol. 193, pp. 129–150, 1993.

[34]

F. Marvasti, Nonuniform Sampling: Theory and Practice, Berlin, Germany: Springer-Verlag, 2001.

[35]

K. D. Sauer and J. P. Allebach, “Iterative reconstruction of bandlimited images from nonuniformly spaced samples,” in IEEE Trans. Circuits Syst., vol. 34, no. 12, pp. 1497–1506, Dec. 1987.

[36]

F. Marvasti, M. Analoui, and M. Gamshadzahi, “Recovery of signals from nonuniform samples using iterative methods,” in IEEE Trans. Signal Process., vol. 39, no. 4, pp. 872–878, Apr. 1991.

Digital Library

[37]

K. Gröchenig, “Reconstruction algorithms in irregular sampling,” in Math. Comput., vol. 59, no. 199, pp. 181–194, 1992.

[38]

J. J. Benedetto, “Irregular sampling and frames,” in Wavelets: A Tutorial Theory Appl., vol. 2, pp. 445–507, 1992.

[39]

I. Pesenson, “Poincaré-type inequalities and reconstruction of Paley-Wiener functions on manifolds,” in J. Geometric Anal., vol. 14, no. 1, pp. 101–121, 2004.

[40]

H. Feichtinger and I. Pesenson, “Recovery of band-limited functions on manifolds by an iterative algorithm,” in Contemporary Math., vol. 345, pp. 137–152, 2004.

[41]

D. Gleich, “The MatlabBGL Matlab Library,”, [Online]. Available: http://www.cs.purdue.edu/homes/dgleich/packages/matlab_bgl/index.html.

Cited By

Morgenstern GRouttenberg T(2024)Efficient Recovery of Sparse Graph Signals From Graph Filter OutputsIEEE Transactions on Signal Processing10.1109/TSP.2024.349522572(5550-5566)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TSP.2024.3495225
Zhang QYang LYang ZHuang C(2024)Recovery of bandlimited graph signals based on the reproducing kernel Hilbert spaceDigital Signal Processing10.1016/j.dsp.2024.104565151:COnline publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1016/j.dsp.2024.104565
Yang JShi CChu YGuo W(2024)Graph signal reconstruction based on spatio-temporal features learningDigital Signal Processing10.1016/j.dsp.2024.104414148:COnline publication date: 1-May-2024
https://dl.acm.org/doi/10.1016/j.dsp.2024.104414
Show More Cited By

Index Terms

Local-Set-Based Graph Signal Reconstruction

Index terms have been assigned to the content through auto-classification.

Recommendations

An Algebraic Formulation of the Graph Reconstruction Conjecture

The graph reconstruction conjecture asserts that every finite simple graph on at least three vertices can be reconstructed up to isomorphism from its deck-the collection of its vertex-deleted subgraphs. Kocay's Lemma is an important tool in graph ...
Graph signal reconstruction based on spatio-temporal features learning
Abstract
This paper presents a new algorithm for reconstructing time-varying graph signals using spatiotemporal feature learning. We introduce a time series analysis method to capture the temporal stationarity of graph signals and propose a reconstruction ...
Research on Graph Signal Sampling and Reconstruction Method Based on Causal Emergence
MLMI '23: Proceedings of the 6th International Conference on Machine Learning and Machine Intelligence

Graph signal sampling and reconstruction techniques effectively reduce data dimensions while preserving the information and structure contained in networks. The distortion-free reduction of data dimensions not only aids in reducing the computational ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Signal Processing

IEEE Transactions on Signal Processing Volume 63, Issue 9

May1, 2015

272 pages

ISSN:1053-587X

Issue’s Table of Contents

Copyright © 2015.

Publisher

IEEE Press

Publication History

Published: 01 May 2015

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

27
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 11 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Morgenstern GRouttenberg T(2024)Efficient Recovery of Sparse Graph Signals From Graph Filter OutputsIEEE Transactions on Signal Processing10.1109/TSP.2024.349522572(5550-5566)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TSP.2024.3495225
Zhang QYang LYang ZHuang C(2024)Recovery of bandlimited graph signals based on the reproducing kernel Hilbert spaceDigital Signal Processing10.1016/j.dsp.2024.104565151:COnline publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1016/j.dsp.2024.104565
Yang JShi CChu YGuo W(2024)Graph signal reconstruction based on spatio-temporal features learningDigital Signal Processing10.1016/j.dsp.2024.104414148:COnline publication date: 1-May-2024
https://dl.acm.org/doi/10.1016/j.dsp.2024.104414
Chakraborty RHolm JPedersen TPopovski P(2023)Finding Representative Sampling Subsets in Sensor Graphs Using Time-series SimilaritiesACM Transactions on Sensor Networks10.1145/359518119:4(1-32)Online publication date: 9-Jun-2023
https://dl.acm.org/doi/10.1145/3595181
Liu JLi DGu HLu TZhang PShang LGu N(2023)Personalized Graph Signal Processing for Collaborative FilteringProceedings of the ACM Web Conference 202310.1145/3543507.3583466(1264-1272)Online publication date: 30-Apr-2023
https://dl.acm.org/doi/10.1145/3543507.3583466
Parada-Mayorga AWang ZRibeiro A(2023)Graphon Pooling for Reducing Dimensionality of Signals and Convolutional Operators on GraphsIEEE Transactions on Signal Processing10.1109/TSP.2023.331847171(3577-3591)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1109/TSP.2023.3318471
Xiao ZFang HTomasin SMateos GWang X(2023)Joint Sampling and Reconstruction of Time-Varying Signals Over Directed GraphsIEEE Transactions on Signal Processing10.1109/TSP.2023.328436471(2204-2219)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1109/TSP.2023.3284364
Zhang QHuang CYang LYang Z(2023)Salt and pepper noise removal method based on graph signal reconstructionDigital Signal Processing10.1016/j.dsp.2023.103941135:COnline publication date: 30-Apr-2023
https://dl.acm.org/doi/10.1016/j.dsp.2023.103941
Hashemi AShafipour RVikalo HMateos G(2022)Towards accelerated greedy sampling and reconstruction of bandlimited graph signalsSignal Processing10.1016/j.sigpro.2022.108505195:COnline publication date: 1-Jun-2022
https://dl.acm.org/doi/10.1016/j.sigpro.2022.108505
Mazarguil AOudre LVayatis N(2022)Non-smooth interpolation of graph signalsSignal Processing10.1016/j.sigpro.2022.108480196:COnline publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1016/j.sigpro.2022.108480
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents