Discrete wavelet transforms for Toeplitz matrices

In this paper, we discuss discrete wavelet transforms for Toeplitz matrices and block–Toeplitz–Toeplitz–block matrices. The main contribution of this paper is to give the Toeplitz-like structure of the wavelet transformed Toeplitz matrices, and show that the computational cost for such structure is O(k3ln) where n is the size of the Toeplitz matrix, k is the order of the wavelet and l is the level used in the wavelet transform. The comparison between the wavelet transformed Toeplitz matrices and the Fourier transformed Toeplitz matrices is also given.