Publica
Hier finden Sie wissenschaftliche Publikationen aus den FraunhoferInstituten. Robust compressive shift retrieval in linear time
 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: 9781509018918 (Print) ISBN: 9780992862657 (Online) pp.364368 
 European Signal Processing Conference (EUSIPCO) <24, 2016, Budapest> 

 English 
 Conference Paper 
 Fraunhofer FKIE () 
Abstract
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 crosscorrelation 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 noisefree 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.