A Note on Shift Retrieval Problems

In this paper, we discuss several shift retrieval problems, both classical and compressed, and provide connections between them using the general framework of circulant matrices. We review the properties of circulant matrices necessary for our calculations and then show how circular shifts can be recovered from as few measurements as possible in different scenarios. We treat several cases: circular shifts between two signals and between multiple pairs of signals, and linear combinations of circular shifts. In all these cases, we provide conditions under which the shift recovery is successful, we give explicit formulas, and we state convex optimization problems for the practical recovery of the shifts for both the noiseless and noisy measurement scenarios. Our goal is to accurately and robustly recover shift information from as few linear measurements as possible. Experimental results then validate the findings through simulation, where we compare the classic cross-correlation result with the proposed approaches.