A novel algorithm for computing autocorrelation of randomly sampled sequences

Random sampling is one of the methods used to achieve sub-Nyquist sampling. This paper proposes a novel algorithm to evaluate the circular autocorrelation of a randomly sampled sequence, from which its power density spectrum can be obtained. With uniform sampling, the size of each lag (the step size) for computing an autocorrelation of a sequence is the same as the sampling period. When random sampling is adopted, the step size should be chosen such that the highest-frequency component of interest contained in a sequence can be accommodated. To find overlaps between a time sequence and its shifted version, an appropriate window is opened in one of the time sequences. To speed up the process, a marker is set to limit the range of searching for overlaps. The proposed method of estimating the power spectrum via autocorrelation is comparable in terms of accuracy and signal-to-noise ratio (SNR) to the conventional point rule. The techniques introduced can also apply to other operations for randomly sampled sequences.