SpringerLink
Log in

A Distributed Algorithm for Reconstructing Time-Varying Graph Signals

  • Short Paper
  • Published:
Circuits, Systems, and Signal Processing Aims and scope Submit manuscript

Abstract

The reconstruction of time-varying signals on graphs is a prominent problem in graph signal processing community. By imposing the smoothness regularization over the time-vertex domain, the reconstruction problem can be formulated into an unconstrained optimization problem that minimizes the weighted sum of the data fidelity term and regularization term. In this paper, we propose an approximate Newton method to solve the problem in a distributed manner, which is applicable for spatially distributed systems consisting of agents with limited computation and communication capacity. The algorithm has low computational complexity while nearly maintains the fast convergence of the second-order methods, which is evidently better than the existing reconstruction algorithm based on the gradient descent method. The convergence of the proposed algorithm is explicitly proved. Numerical results verify the validity and fast convergence of the proposed algorithm.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Thailand)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

References

  1. S. Boyd, L. Vandenberghe, Convex Optimization (2004)

  2. J. Brooks, P. Barooah, Consumer-aware distributed demand-side contingency service in the power grid. IEEE Trans. Control Netw. Syst. 5(4), 1987–1997 (2018)

    Article  MathSciNet  Google Scholar 

  3. J. Chen, C. Richard, A.H. Sayed, Multitask diffusion adaptation over networks with common latent representations. IEEE J. Sel. Top. Signal Process. 11(3), 563–579 (2017)

    Article  Google Scholar 

  4. S. Chen, A. Sandryhaila, J.M.F. Moura, J. Kovac̆ević, Signal recovery on graphs: variation minimization. IEEE Trans. Signal Process. 63(17), 4609–4624 (2015)

    Article  MathSciNet  Google Scholar 

  5. S. Chen, R. Varma, A. Singh, J. Kovac̆ević, Representations of piecewise smooth signals on graphs, in 2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) (2016), pp. 6370–6374

  6. M. Coutino, E. Isufi, G. Leus, Advances in distributed graph filtering. IEEE Trans. Signal Process. 67(9), 2320–2333 (2019)

    Article  MathSciNet  Google Scholar 

  7. P. Di Lorenzo, P. Banelli, S. Barbarossa, S. Sardellitti, Distributed adaptive learning of graph signals. IEEE Trans. Signal Process. 65(16), 4193–4208 (2017)

    Article  MathSciNet  Google Scholar 

  8. M. Eisen, A. Mokhtari, A. Ribeiro, Decentralized quasi-Newton methods. IEEE Trans. Signal Process. 65(10), 2613–2628 (2017)

    Article  MathSciNet  Google Scholar 

  9. F. Gama, E. Isufi, A. Ribeiro, G. Leus, Controllability of bandlimited graph processes over random time varying graphs. IEEE Trans. Signal Process. 67(24), 6440–6454 (2019)

    Article  MathSciNet  Google Scholar 

  10. F. Grassi, A. Loukas, N. Perraudin, B. Ricaud, A time-vertex signal processing framework: scalable processing and meaningful representations for time-series on graphs. IEEE Trans. Signal Process. 66(3), 817–829 (2018)

    Article  MathSciNet  Google Scholar 

  11. D.K. Hammond, P. Vandergheynst, R. Gribonval, Wavelets on graphs via spectral graph theory. Appl. Comput. Harmon. Anal. 30(2), 129–150 (2011)

    Article  MathSciNet  Google Scholar 

  12. V.N. Ioannidis, Y. Shen, G.B. Giannakis, Semi-blind inference of topologies and dynamical processes over dynamic graphs. IEEE Trans. Signal Process. 67(9), 2263–2274 (2019)

    Article  MathSciNet  Google Scholar 

  13. E. Isufi, P. Banelli, P. Di Lorenzo, G. Leus, Observing and tracking bandlimited graph processes from sampled measurements. Signal Process. 177, 107749 (2020)

    Article  Google Scholar 

  14. E. Isufi, A. Loukas, N. Perraudin, G. Leus, Forecasting time series with Varma recursions on graphs. IEEE Trans. Signal Process. 67(18), 4870–4885 (2019)

    Article  MathSciNet  Google Scholar 

  15. E. Isufi, A. Loukas, A. Simonetto, G. Leus, Filtering random graph processes over random time-varying graphs. IEEE Trans. Signal Process. 65(16), 4406–4421 (2017)

    Article  MathSciNet  Google Scholar 

  16. J. Jiang, C. Cheng, Q. Sun, Nonsubsampled graph filter banks: theory and distributed algorithms. IEEE Trans. Signal Process. 67(15), 3938–3953 (2019)

    Article  MathSciNet  Google Scholar 

  17. H. Liang, X. Guo, Y. Pan, T. Huang, Event-triggered fuzzy bipartite tracking control for network systems based on distributed reduced-order observers. IEEE Trans. Fuzzy Syst. 29(6), 1601–1614 (2021)

    Article  Google Scholar 

  18. H. Liang, G. Liu, H. Zhang, T. Huang, Neural-network-based event-triggered adaptive control of nonaffine nonlinear multiagent systems with dynamic uncertainties. IEEE Trans. Neural Netw. Learn. Syst. 32(5), 2239–2250 (2021)

    Article  MathSciNet  Google Scholar 

  19. J. Liu, K. Huang, X. Yao, Common-innovation subspace pursuit for distributed compressed sensing in wireless sensor networks. IEEE Sens. J. 19(3), 1091–1103 (2019)

    Article  Google Scholar 

  20. Y. Liu, L. Yang, K. You, W. Guo, W. Wang, Graph learning based on spatiotemporal smoothness for time-varying graph signal. IEEE Access 7, 62372–62386 (2019)

    Article  Google Scholar 

  21. A. Mokhtari, Q. Ling, A. Ribeiro, Network newton distributed optimization methods. IEEE Trans. Signal Process. 65(1), 146–161 (2017)

    Article  MathSciNet  Google Scholar 

  22. J. Nocedal, S. Wright, Numerical Optimization (2006)

  23. A. Ortega, P. Frossard, J. Kovac̆ević, J.M.F. Moura, P. Vandergheynst, Graph signal processing: overview, challenges, and applications. Proc. IEEE 106(5), 808–828 (2018)

    Article  Google Scholar 

  24. N. Perraudin, J. Paratte, D. Shuman, L. Martin, V. Kalofolias, P. Vandergheynst, D.K. Hammond, GSPBOX: a toolbox for signal processing on graphs. ar**v e-prints, ar**v:1408.5781 (2014)

  25. N. Perraudin, A. Loukas, F. Grassi, P. Vandergheynst, Towards stationary time-vertex signal processing, in 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) (2017), pp. 3914–3918

  26. I. Pesenson, Sampling in Paley–Wiener spaces on combinatorial graphs. Trans. Am. Math. Soc. 360(10), 5603–5627 (2008)

    Article  MathSciNet  Google Scholar 

  27. K. Qiu, X. Mao, X. Shen, X. Wang, T. Li, G. Yuantao, Time-varying graph signal reconstruction. IEEE J. Sel. Top. Signal Process. 11(6), 870–883 (2017)

    Article  Google Scholar 

  28. D. Romero, V.N. Ioannidis, G.B. Giannakis, Kernel-based reconstruction of space-time functions on dynamic graphs. IEEE J. Sel. Top. Signal Process. 11(6), 856–869 (2017)

    Google Scholar 

  29. Sea surface temperature (sst) v2. https://www.esrl.noaa.gov/psd/data/gridded/data.noaa.oisst.v2.html (2021)

  30. A. Sandryhaila, J.M.F. Moura, Discrete signal processing on graphs. IEEE Trans. Signal Process. 61(7), 1644–1656 (2013)

    Article  MathSciNet  Google Scholar 

  31. S. Sardellitti, S. Barbarossa, P. Di Lorenzo, Graph topology inference based on sparsifying transform learning. IEEE Trans. Signal Process. 67(7), 1712–1727 (2019)

    Article  MathSciNet  Google Scholar 

  32. S. Segarra, A.G. Marques, A. Ribeiro, Optimal graph-filter design and applications to distributed linear network operators. IEEE Trans. Signal Process. 65(15), 4117–4131 (2017)

    Article  MathSciNet  Google Scholar 

  33. D.I. Shuman, S.K. Narang, P. Frossard, A. Ortega, P. Vandergheynst, The emerging field of signal processing on graphs: extending high-dimensional data analysis to networks and other irregular domains. IEEE Signal Process. Mag. 30(3), 83–98 (2013)

    Article  Google Scholar 

  34. Y. Tanaka, A. Sakiyama, \(m\)-channel oversampled graph filter banks. IEEE Trans. Signal Process. 62(14), 3578–3590 (2014)

    Article  MathSciNet  Google Scholar 

  35. D.B.H. Tay, Y. Tanaka, A. Sakiyama, Critically sampled graph filter banks with polynomial filters from regular domain filter banks. Signal Process. 131, 66–72 (2017)

    Article  Google Scholar 

  36. J. Yick, B. Mukherjee, D. Ghosal, Wireless sensor network survey. Comput. Netw. 52(12), 2292–2330 (2008)

    Article  Google Scholar 

  37. M. Zargham, A. Ribeiro, A. Ozdaglar, A. Jadbabaie, Accelerated dual descent for network flow optimization. IEEE Trans. Autom. Control 59(4), 905–920 (2014)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

This work is partially supported by the National Natural Science Foundation of China (Grant Nos. 61761011, 61871303, 62171146), Natural Science Foundation of Guangxi Province (Grant Nos. 2017GXNSFAA198173, 2017GXNSFBA198137).

Author information

Authors and Affiliations

  1. Guangxi Key Laboratory of Wireless Wideband Communication and Signal Processing, Guilin University of Electronic Technology, Guilin, 541004, China

    Yuan Chi & Junzheng Jiang

  2. School of Life and Environmental Sciences, Guilin University of Electronic Technology, Guilin, 541004, China

    Fang Zhou

  3. National Lab of Radar Signal Processing, **dian University, **’an, 710071, China

    Shuwen Xu

Authors
  1. Yuan Chi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Junzheng Jiang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Fang Zhou
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Shuwen Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Fang Zhou.

Ethics declarations

Data Availability

The data used to support the findings of this study are available in [29, 24].

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Chi, Y., Jiang, J., Zhou, F. et al. A Distributed Algorithm for Reconstructing Time-Varying Graph Signals. Circuits Syst Signal Process 41, 3624–3641 (2022). https://doi.org/10.1007/s00034-021-01930-3

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00034-021-01930-3

Keywords

Search

Navigation