摘要翻译：
我们考虑了一个在图上对随时间演化的路径信号进行局部化的问题。路径信号可以看作是一个运动的agent在图上连续几个时间点上的轨迹。将动态规划和图划分相结合，提出了一种计算复杂度显著降低的路径定位算法。利用数值界分析了该方法在Hamming距离和目标距离两个方面的定位误差。与通常的仅适用于受限图模型的理论界不同，所得到的数值界适用于所有图和所有非重叠图划分方案。在随机几何图中，我们可以导出定位误差界的闭式表达式，以及定位误差与计算复杂度之间的折衷。最后，在路径约束条件下，我们将该方法与最大似然估计方法在计算复杂度和定位误差方面进行了比较，并在实际数据的图上显示了显著的加速比（100倍）和可比定位误差（4倍）。该技术的变体可以应用于跟踪、道路拥堵监测和大脑信号处理。
---
英文标题：
《Fast Path Localization on Graphs via Multiscale Viterbi Decoding》
---
作者：
Yaoqing Yang, Siheng Chen, Mohammad Ali Maddah-Ali, Pulkit Grover,
  Soummya Kar, Jelena Kova\v{c}evi\'c
---
最新提交年份：
2017
---
分类信息：

一级分类：Electrical Engineering and Systems Science        电气工程与系统科学
二级分类：Signal Processing        信号处理
分类描述：Theory, algorithms, performance analysis and applications of signal and data analysis, including physical modeling, processing, detection and parameter estimation, learning, mining, retrieval, and information extraction. The term "signal" includes speech, audio, sonar, radar, geophysical, physiological, (bio-) medical, image, video, and multimodal natural and man-made signals, including communication signals and data. Topics of interest include: statistical signal processing, spectral estimation and system identification; filter design, adaptive filtering / stochastic learning; (compressive) sampling, sensing, and transform-domain methods including fast algorithms; signal processing for machine learning and machine learning for signal processing applications; in-network and graph signal processing; convex and nonconvex optimization methods for signal processing applications; radar, sonar, and sensor array beamforming and direction finding; communications signal processing; low power, multi-core and system-on-chip signal processing; sensing, communication, analysis and optimization for cyber-physical systems such as power grids and the Internet of Things.
信号和数据分析的理论、算法、性能分析和应用，包括物理建模、处理、检测和参数估计、学习、挖掘、检索和信息提取。“信号”一词包括语音、音频、声纳、雷达、地球物理、生理、（生物）医学、图像、视频和多模态自然和人为信号，包括通信信号和数据。感兴趣的主题包括：统计信号处理、谱估计和系统辨识；滤波器设计；自适应滤波/随机学习；（压缩）采样、传感和变换域方法，包括快速算法；用于机器学习的信号处理和用于信号处理应用的机器学习；网络与图形信号处理；信号处理中的凸和非凸优化方法；雷达、声纳和传感器阵列波束形成和测向；通信信号处理；低功耗、多核、片上系统信号处理；信息物理系统的传感、通信、分析和优化，如电网和物联网。
--

---
英文摘要：
  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 non-overlapping 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 times) with comparable localization error (4 times) on a graph from real data. Variants of the proposed technique can be applied to tracking, road congestion monitoring, and brain signal processing.
---
PDF链接：
https://arxiv.org/pdf/1711.01329