Fast Path Localization on Graphs via Multiscale Viterbi Decoding

  • Authors:
    Pulkit Grover (Carnegie Mellon Univ.), Yaoqing Yang (Carnegie Mellon Univ.), Soummya Kar (Carnegie Mellon Univ.), Mohammad Maddah-Ali (Nokia), Jelena Kovacevic (Carnegie Mellon Univ.), Siheng Chen (Carnegie Mellon Univ.)
    Publication ID:
    Publication Type:
    Received Date:
    Last Edit Date:
    2385.001 (University of Illinois/Urbana-Champaign)


We consider a problem of localizing a path-signal that evolves over time on a graph. A path-signal can be viewed as the trajectory of a moving agent on a graph in several consecutive time points. Combining dynamic programming and graph partitioning, we propose a path-localization algorithm with significantly reduced computational complexity. We analyze the localization error for the proposed approach both in the Hamming distance and the destination’s distance between the path estimate and the true path using numerical bounds. Unlike usual theoretical bounds that only apply to restricted graph models, the obtained numerical bounds apply to all graphs and all nonoverlapping graph-partitioning schemes. In random geometric graphs, we are able to derive 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 under the path constraint in terms of computational complexity and localization error, and show significant speedup (100 ×) with comparable localization error (4 ×) on a graph from real data. Variants of the proposed technique can be applied to tracking, road congestion monitoring, and brain signal processing

4819 Emperor Blvd, Suite 300 Durham, NC 27703 Voice: (919) 941-9400 Fax: (919) 941-9450

Important Information for the SRC website. This site uses cookies to store information on your computer. By continuing to use our site, you consent to our cookies. If you are not happy with the use of these cookies, please review our Cookie Policy to learn how they can be disabled. By disabling cookies, some features of the site will not work.