# What is the effect of aliasing on the magnitude of the autocorrelation?

I've a question about the effect of aliasing on the magnitude of autocorrelations. From a simulation in MATLAB, I don't see any effect of aliasing or any need to anti-alias filter when I take the magnitude of the autocorrelation. Which means I can undersample the data and then take the autocorrelation. There is a paper "Effects of Aliasing on Spectral Moment Estimates Derived from the Complete Autocorrelation Function" which says something like what I claim. Would anybody please let me know if I've made a mistake?

Decimating before calculating the autocorrelation, in the presence of noise, is inferior to calculating the autocorrelation using the full dataset. Assume that the signal of interest is embedded in white noise. The vector $x[n], n = 0, 1, ..., N-1$ consists of samples from a discrete random process. The autocorrelation function of the vector $x[n]$ is:

$$A_x[k] = \frac{1}{N-k} \sum_{i=0}^{N-1-k} x[i]x[i+k]$$

That is, $k$ is the lag used for the autocorrelation calculation. In your proposed scenario, you are decimating the autocorrelation function output by a factor $D$ (i.e. you are only calculating the function for lags $0, D, 2D, ...$) and comparing that result to the autocorrelation function of $x[n]$ decimated by the same factor $D$. Let $x_d[n]$ be the decimated sequence; its autocorrelation function is:

$$A_{x_d}[k] = \frac{D}{N-k} \sum_{i=0}^{\frac{N-1-k}{D}} x[iD]x[(i+k)D]$$

(for simplicity here, I have assumed that $D$ is a factor of $N$ in the above equation)

Your inquiry can be written as:

$$A_x[kD] \stackrel{?}{\approx} A_{x_d}[k]$$

$$\frac{1}{N-kD} \sum_{i=0}^{N-1-kD} x[i]x[i+kD] \stackrel{?}{\approx} \frac{D}{N-k} \sum_{i=0}^{\frac{N-1-k}{D}} x[iD]x[(i+k)D]$$

Looking at this qualitatively, the summation on the left hand side has more terms than its counterpart on the right side. If $x[n]$ is second-order stationary, then the expected value of each term in each sum is the same; the act of averaging multiple samples that have the same expected value increases the signal to noise ratio. Stated a little differently, you can think the terms in each sum as samples from a new random process:

$$y[n] = x[n]x[n+kD]$$

Since the noise present in $x[n]$ is white, the expected value of $y[n]$ is the true autocorrelation of the signal of interest at lag $kD$. Therefore, we would like to accurately estimate the expected value of $y[n]$. Our method for doing so is by calculating a sample average; it can easily be shown that the variance in the sample average estimator decreases given a larger sample size, converging to the actual expected value as the number of samples tends to $\infty$.

So, if there is white noise present in the signal (which is often the case), you're going to get a better estimate of the underlying signal's second-order statistics by using a larger sample size in the calculation (this might sound intuitively obvious). In the context of your two approaches, this is accomplished by using the full, non-decimated signal in the autocorrelation calculation and decimating afterward (i.e. only calculating the result for certain lag values).

• Thank you very much. You are right but in case of my signal it is not the dominant problem. My problem is mostly the effect of aliasing. You explained that full non-decimate signal can be better but if we are going to decrease the effect of aliasing we should take even more samples like two(3) times of number of samples and it really increases the complexity. – Hossein Sep 19 '11 at 3:14

Seems a little odd to me. The Matlab script below compares the "downsampled autocorrelation" to the "autocorrelation of the downsampled signals". For dual sine waves this actually comes pretty close (relative error of about -50dB) but for white noise it's simply wrong (relative error > +6 dB). While there may be some computational advantage it's not clear to me how useful the downsampled autocorrelations is even in the dual sine wave case. The peaks in the spectrum still show up in the wrong place.

% script to check whether autocorrelation is immune to aliasing
% create two sine waves at 18k and 21k (assuming sample rate of 444.1k)
n = 8192;
t = (0:n-1)'/44100;
x = sin(2*pi*t*21000)+sin(2*pi*t*18000);
% calculate autocorrelation of original signal and one that's downsampled
% by 4 and thus heavily aliased
y = xcorr(x,x);
y2 = xcorr(x(1:4:end),x(1:4:end));
d = y(4:4:end)-4*y2;
% calculate the error in dB
err = 10*log10(sum(d.^2)./sum(y2.^2));
fprintf('Dual sine wave relative error = %6.2f dB\n',err);

%% try the same thing for white noise
x = 2*rand(n,1)-1;
y = xcorr(x,x);
y2 = xcorr(x(1:4:end),x(1:4:end));
d = y(4:4:end)-4*y2;
err = 10*log10(sum(d.^2)./sum(y2.^2));
fprintf('White noise relative error = %6.2f dB\n',err);

• Thank you very much but the place of peaks in autocorrelation is important for me and therefore I'm not pretty sure that this code shows my problem. But as you point out while the spectrum changes, we face with small changes in time domain similar to what paper says. – Hossein Sep 17 '11 at 23:30

For specific types of inputs the effect of frequency aliasing on the magnitude of autocorrelations may be negligible. However, I don't think this will be true in general.

For instance, for a bandlimited input or for white noise the under-sampling will not impact the shape of the autocorrelation (although it might change the scaling in a predictive way). The autocorrelation of white noise is a delta and it will remain to be a delta if down-sampled.

Now, the power spectrum is related to the autocorrelation by the fourier transform. So if your claim would be true it seems that you could also claim that frequency aliasing does not change the frequency contents of the input. And this is not true. But there might be exceptions (special cases).