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.
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.
This gives us two alternative methods by which to obtain symmetric positive semi-definite Toeplitz matrices.