1A New Algorithm for the Nearest Singular Toeplitz Matrix to a Given Toeplitz Matrix

Abstract—Several signal processing applications can be formulated as the computation of the null vector of a Hermitian Toeplitz matrix. These include ar-ray processing, spectral estimation, and beamform-ing algorithms applied directly to data rather than to its autocorrelation, and some blind deconvolution algorithms. When the data are noisy, the matrix is nonsingular, and the closest singular Toeplitz matrix (in the mean square norm) to the given matrix must be computed. Two major approaches have been used for this problem: (1) alternatingly subtracting off the outer product of minimum singular vectors and aver-aging along diagonals; and (2) structured total least squares. Both require many iterations of computa-tionally intensive singular value decompositions. We present a new algorithm that is: (1) non-iterative; and (2) requires only solution of a Toeplitz system of equa-tions. Several interesting linear algebra issues arise. Numerical examples illustrate the new algorithm. Keywords—Toeplitz matrices, spectral estimation