Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Robust compressive shift retrieval in linear time

: Clausen, M.; Kurth, F.


Institute of Electrical and Electronics Engineers -IEEE-; European Association for Signal Processing -EURASIP-:
24th European Signal Processing Conference, EUSIPCO 2016. Proceedings : 28 August - 2 September 2016, Budapest, Hungary
Piscataway, NJ: IEEE, 2016
ISBN: 978-1-5090-1891-8 (Print)
ISBN: 978-0-9928-6265-7 (Online)
European Signal Processing Conference (EUSIPCO) <24, 2016, Budapest>
Conference Paper
Fraunhofer FKIE ()

Suppose two finite signals are related by an unknown cyclic shift. Fast algorithms for finding such a shift or variants thereof are of great importance in a number of applications, e.g., localization and target tracking using acoustic sensors. The standard solution, solving shift finding by maximizing the cross-correlation between the two signals, may be rather efficiently computed using fast Fourier transforms (FFTs). Inspired by compressive sensing, faster algorithms have been recently proposed based on sparse FFTs. In this paper, we transform the shift finding problem into the spectral domain as well. As a first contribution, by combining the Fourier Shift Theorem with the Bézout Identity from elementary number theory, we obtain explicit formulas for the unknown shift parameter. This leads to linear time algorithms for shift finding in the noise-free setting. As a second contribution, we extend this result to the fast recovery of weighted sums of two shifts. Furthermore, we introduce a novel iterative algorithm for estimation of the unknown shift parameter for the case of noisy signals and provide a sufficient criterion for exact shift recovery. A slightly relaxed criterion leads to a linear time median algorithm in the noisy setting with high recovery rates even for low SNRs.