A real Toeplitz matrix has elements and is fully defined by the elements of for .

If this is a symmetric matrix then the signal has even symmetry . This post is going to look at two ways of generating symmetric Toeplitz matrices which are positive semi-definite.

Auto-correlation of an infinite signal

One way to generate symmetric Toeplitz matrices which are positive semi-definite is to compute the auto-covariance of an infinite signal. An easy way to obtain an infinite signal is to use the periodic extension of a finite signal. The period should be at least to avoid periodic effects. If then the matrix will be circulant Toeplitz. The Fourier transform can be used to compute the auto-correlation.

p = 100;
m = 2*p-1;
x = randn(m, 1);
a = ifft(conj(fft(x)) .* fft(x)) / m;
a = a(1:p);
A = toeplitz(a, a);

Sampled continuous function

It is possible to consider an infinite Toeplitz matrix with elements for . This matrix maps infinite sequences to infinite sequences such that implies

The infinite sequence defines a -periodic function in its discrete-time Fourier transform (DTFT)

The values that this function takes in a period are the eigenvalues of the infinite Toeplitz matrix. Therefore, an infinite Toeplitz matrix will be positive semi-definite if and only if the DTFT of its elements is a non-negative function.

It can be shown that if a continuous function has a positive Fourier transform, then sampling the function will result in a sequence with a positive DTFT. The DTFT of a sampled continuous function can be written as the continuous transform of the function multiplied by a “Dirac comb” or “impulse train”

Using the transform of a Dirac comb and the fact that multiplication in time is convolution in frequency,

Therefore if the continuous transform of is non-negative , then the sequence obtained by sampling that function will have a non-negative DTFT . This gives us many ways to construct infinite symmetric Toeplitz matrices which are positive semi-definite. For example, the elements can be sampled from a Gaussian (transform is a Gaussian), triangle (transform is a squared sinc), sinc (transform is a rectangle), squared sinc (transform is a triangle), cosine, sech, Laplacian density function, etc.

Finally, we need a way to go from infinite matrices to finite matrices. This is easily achieved using the fact that any subset of the rows and columns of a positive semi-definite matrix is itself semi-definite. If for all , then for all . Therefore we can simply take a finite section of the infinite matrix and be guaranteed that it is positive semi-definite.

p = 100;
t = 0:p-1;
a = exp(-abs(t)/10);
A = toeplitz(a, a);

This gives us two alternative methods by which to obtain symmetric positive semi-definite Toeplitz matrices.