Fast Wavelet Transform for Toeplitz Matrices and Property Analysis

Abstract Fast wavelet transform algorithms for Toeplitz matrices are proposed in this paper. Distinctive from the well known discrete trigonometric transforms, such as the discrete cosine transform (DCT) and the discrete Fourier transform (DFT) for Toeplitz matrices, the new algorithms are achieved by compactly supported wavelet that preserve the character of a Toeplitz matrix after transform, which is quite useful in many applications involving a Toeplitz matrix. Results of numerical experiments show that the proposed method has good compression performance similar to using wavelet in the digital image coding. Since the proposed algorithms turn a dense Toeplitz matrix into a band-limited form, the arithmetic operations required by the new algorithms are O(N) that are reduced greatly compared with O(N log N) by the classical trigonometric transforms. Supported by the National Natural Science Foundation under Grants (No.10171109)