Linear Algebra and its Applications 370 (2003) 269–285 www.elsevier.com/locate/laa Discrete wavelet transforms for Toeplitz matrices

In this paper, we discuss discrete wavelet transforms for Toeplitz matrices and block–Toep-litz–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