TY - JOUR
T1 - Fast temporal path localization on graphs via multiscale viterbi decoding
AU - Yang, Yaoqing
AU - Chen, Siheng
AU - Maddah-Ali, Mohammad Ali
AU - Grover, Pulkit
AU - Kar, Soummya
AU - Kovacevic, Jelena
N1 - Funding Information:
Manuscript received October 25, 2017; revised March 4, 2018, June 20, 2018, and August 12, 2018; accepted August 21, 2018. Date of publication September 10, 2018; date of current version September 28, 2018. The associate editor coordinating the review of this manuscript and approving it for publication was Prof. Wee Peng Tay. A preliminary version of this work was presented in part at the IEEE International Conference on Acoustics, Speech and Signal Processing, 2017 [1]. This work of Pulkit Grover was supported in part by the National Science Foundation under Grants CCF-1513936, ECCS-1343324, and CCF-1350314 (NSF CAREER). This work was supported by the Systems on Nanoscale Information fabriCs (SONIC), one of the six SRC STARnet Centers, sponsored by MARCO and DARPA. (Corresponding author: Yaoqing Yang.) Y. Yang, P. Grover, and S. Kar are with the Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PA 15213 USA (e-mail:, yyaoqing@andrew.cmu.edu; pulkit@cmu.edu; soummyak@ andrew.cmu.edu).
PY - 2018/11/1
Y1 - 2018/11/1
N2 - We consider a problem of localizing a temporal path signal that evolves over time on a graph. A path signal represents the trajectory of a moving agent on a graph in a series of consecutive time stamps. Through combining dynamic programing and graph partitioning, we propose a path-localization algorithm with significantly reduced computational complexity. To analyze the localization performance, we use two evaluation metrics to quantify the localization error: The Hamming distance and the destination's distance between the ground-truth path and the estimated path. In random geometric graphs, we provide a closed-form expression for the localization error bound, and a tradeoff between localization error and the computational complexity. Finally, we compare the proposed technique with the maximum likelihood estimate in terms of computational complexity and localization error, and show significant speedup (100×) with comparable localization error (4×) on a graph from real data.
AB - We consider a problem of localizing a temporal path signal that evolves over time on a graph. A path signal represents the trajectory of a moving agent on a graph in a series of consecutive time stamps. Through combining dynamic programing and graph partitioning, we propose a path-localization algorithm with significantly reduced computational complexity. To analyze the localization performance, we use two evaluation metrics to quantify the localization error: The Hamming distance and the destination's distance between the ground-truth path and the estimated path. In random geometric graphs, we provide a closed-form expression for the localization error bound, and a tradeoff between localization error and the computational complexity. Finally, we compare the proposed technique with the maximum likelihood estimate in terms of computational complexity and localization error, and show significant speedup (100×) with comparable localization error (4×) on a graph from real data.
KW - Graph signal processing
KW - Viterbi decoding
KW - graph partitioning
UR - http://www.scopus.com/inward/record.url?scp=85053153125&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85053153125&partnerID=8YFLogxK
U2 - 10.1109/TSP.2018.2869119
DO - 10.1109/TSP.2018.2869119
M3 - Article
AN - SCOPUS:85053153125
VL - 66
SP - 5588
EP - 5603
JO - IEEE Transactions on Signal Processing
JF - IEEE Transactions on Signal Processing
SN - 1053-587X
IS - 21
M1 - 8458140
ER -