June 19, 2017

FAST PATH LOCALIZATION ON GRAPHS VIA MULTISCALE VITERBI DECODING

  • Chen S.
  • Grover P.
  • Kar S.
  • Kovacevic J.
  • Maddahali M.
  • Yang Y.

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 graph with one million nodes and one thousand time slots.

View Original Article

Recent Publications

June 19, 2017

COMBINING BELIEF PROPAGATION AND SUCCESSIVE CANCELLATION LIST DECODING OF POLAR CODES ON A GPU PLATFORM

  • Cammerer S.
  • Hoydis J.
  • Leible B.
  • Stahl M.
  • Ten Brink S.

The decoding performance of polar codes strongly depends on the decoding algorithm used, while also the decoder throughput and its latency mainly depend on the decoding algorithm. In this work, we implement the powerful successive cancellation list (SCL) decoder on a GPU and identify the bottlenecks of this algorithm with ...

June 04, 2017

A New PRACH Transmission Scheme in Unlicensed Spectrum

  • Luo Z.
  • Meng Y.
  • Tao T.

For the unlicensed spectrum, the occupied bandwidth requirement is demanded by some regulations. The legacy scheme of Physical Random Access Channel (PRACH) for Long Term Evolution (LTE) cannot satisfy it. In this paper, we propose a novel PRACH transmission scheme to satisfy the requirement of unlicensed spectrum based on preamble ...

June 01, 2017

Mutual service processes in Euclidean spaces: existence and ergodicity

  • Baccelli F.
  • Mathieu F.
  • Norros I.

Consider a set of objects, abstracted to points of a spatially stationary point process in R-d, that deliver to each other a service at a rate depending on their distance. Assume that the points arrive as a Poisson process and leave when their service requirements have been fulfilled. We show ...