Fast path localization on graphs via multiscale Viterbi decoding
Yaoqing Yang, Siheng Chen, Mohammad Ali Maddah-Ali, Pulkit Grover, Soummya Kar, Jelena Kovacevic
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.
BibTeX
@inproceedings{icassp2017_fastpathlocaliza,
title = {Fast path localization on graphs via multiscale Viterbi decoding},
author = {Yaoqing Yang and Siheng Chen and Mohammad Ali Maddah-Ali and Pulkit Grover and Soummya Kar and Jelena Kovacevic},
booktitle = {ICASSP 2017},
year = {2017}
}