TY - GEN
T1 - Fast path localization on graphs via multiscale Viterbi decoding
AU - Yang, Yaoqing
AU - Chen, Siheng
AU - Ali Maddah-Ali, Mohammad
AU - Grover, Pulkit
AU - Kar, Soummya
AU - Kovacevic, Jelena
N1 - Publisher Copyright:
© 2017 IEEE.
PY - 2017/6/16
Y1 - 2017/6/16
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85023769936&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85023769936&partnerID=8YFLogxK
U2 - 10.1109/ICASSP.2017.7952930
DO - 10.1109/ICASSP.2017.7952930
M3 - Conference contribution
AN - SCOPUS:85023769936
T3 - ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
SP - 4114
EP - 4118
BT - 2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017 - Proceedings
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017
Y2 - 5 March 2017 through 9 March 2017
ER -