Fast computing position of maximum of circulant convolution

This paper proposes a fast but heuristic scheme, returning only the position of maximum of convolution instead of the whole sequence after convolution. The main idea is to alias both the signal and template into lower dimensional space with the same dimension M being smaller than N and K, respectively. Thus, the computation cost is reduced to O(N+Mlog⁡M) operations with M=Ω(N), where M is the only user-defined parameter and plays the trade-off between the computation cost and successfully returning the position of the maximum. To guide how to decide M, we show that the sufficient condition of successfully returning the position of the maximum depends on the relationship between the maximum convolution and remaining convolution results based on three different cases, i.e., K≤M, K>M with M exactly dividing N or not exactly dividing N. We further show how the probability of success can be analyzed if both the signal and template are random. Simulations validate the proposed scheme is fast and efficient, and they support the theoretical results. A case study with synchronization in global positioning system (GPS) is taken as a case study to demonstrate the applicability of our method.