Fast path localization on graphs via multiscale Viterbi decoding

Yaoqing Yang, Siheng Chen, Mohammad Ali Maddah-Ali, Pulkit Grover, Soummya Kar, Jelena Kovacevic

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider a problem of localizing the destination of an activated path signal supported on a graph. An "activated path signal" is a graph signal that evolves over time that can be viewed as the trajectory of a moving agent. We show that by combining dynamic programming and graph partitioning, the computational complexity of destination localization can be significantly reduced. Then, we show that the destination localization error can be upper-bounded using methods based on large-deviation. Using simulation results, we show a tradeoff between the destination localization error and the computation time. We compare the dynamic programming algorithm with and without graph partitioning and show that the computation time can be significantly reduced by using graph partitioning. The proposed technique can scale to the problem of destination localization on a large graph with one million nodes and one thousand time slots.

Original languageEnglish (US)
Title of host publication2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages4114-4118
Number of pages5
ISBN (Electronic)9781509041176
DOIs
StatePublished - Jun 16 2017
Event2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017 - New Orleans, United States
Duration: Mar 5 2017Mar 9 2017

Publication series

NameICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
ISSN (Print)1520-6149

Other

Other2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017
CountryUnited States
CityNew Orleans
Period3/5/173/9/17

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Fast path localization on graphs via multiscale Viterbi decoding'. Together they form a unique fingerprint.

  • Cite this

    Yang, Y., Chen, S., Ali Maddah-Ali, M., Grover, P., Kar, S., & Kovacevic, J. (2017). Fast path localization on graphs via multiscale Viterbi decoding. In 2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017 - Proceedings (pp. 4114-4118). [7952930] (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICASSP.2017.7952930