×

Fast wavelet transform for Toeplitz matrices and property analysis. (English) Zbl 1106.65125

The authors propose new fast wavelet transform algorithms for Toeplitz matrices. These ones are achieved by a compactly supported wavelet that preserves the character of the Toeplitz matrix after the transform, which is quite useful in many applications involving Toeplitz matrices.
The first part is an introduction concerning Toeplitz matrices, systems and fast transform algorithms proposed in recent years.
The second part gives a brief review of the biorthogonal wavelets and theirs properties.
The third part presents the general wavelet transform algorithms together with several theorems elaborating the characteristics of transformed matrices. The first correlative transforming algorithm for Toeplitz matrices is named complete BDWT (CDBWT). The second one is called partial DBWT (PDBWT) for Toeplitz matrices, and different from the CDBWT, this one only performs DBWT on the low frequency part of the matrix instead of the whole matrix.
Then each transform is applied to a Toeplitz matrix (when the wavelet is orthogonal) or a matrix constructed by four sub-Toeplitz matrices (when the wavelet is biorthogonal).
The fourth section gives numerical results which suggest that the new algorithms have better compression performance than the widely used trigonometric transforms for Toeplitz matrices.
The new methods can preserve the Toeplitz characteristic of the original matrix and can be performed repetitiously to simplify many problems efficiently.

MSC:

65T50 Numerical methods for discrete and fast Fourier transforms
65T60 Numerical methods for wavelets
65F30 Other matrix algorithms (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arguello F., Trenas, M.A., Lopez, J., Zapata, E.L. Algorithm for cosine transform of Toeplitz matrices. IEE Electron. Lett., 34:1182–1183 (1998) · doi:10.1049/el:19980868
[2] Beylkin, G., Coifman, R., Rokhlin V. Fast wavelet transforms and numerical algorithms I. Communications on Pure and Applied Mathematics, 44:141–183 (1991) · Zbl 0722.65022 · doi:10.1002/cpa.3160440202
[3] Bozzo, E., Fiore, C.D. On the use of certain matrix algebras associated with discrete trigonometric transforms in matrix displacement decompositions. SIAM J. Matrix Anal. Appl., 16:312–326 (1995) · Zbl 0819.65017 · doi:10.1137/S0895479893245103
[4] Chan, R., Ng, M. Conjugate gradient methods for Toeplitz systems. SIAM Review, 38:472–484 (1996) · Zbl 0863.65013 · doi:10.1137/S0036144594276474
[5] Cheng, L.Z. Fast computation of discrete W transform through discrete hartley transform(DHT). Electron. Lett., 36:474–476 (2000) · doi:10.1049/el:20000371
[6] Cheng, L.Z. The unified construction and property analysis for Toeplitz preconditioners. Journal of Numerical Math. Appl., 22:49–63 (2000)
[7] Cheng, L.Z. Sine transform matrix for solving Toeplitz matrix problems. Journal of Comput. Math., 19:167–176 (2001) · Zbl 0992.65043
[8] Cheng, L.Z., Wang, H.X. The solution of ill-conditioned symmetric Toeplitz systems via two-grid and wavelet method. Computers Math. Applic., 46:793–804 (2003) · Zbl 1051.65030 · doi:10.1016/S0898-1221(03)90142-8
[9] Cohen, A., Daubechies, I., Feauveau, J.C. Biorthogonal bases of compactly supported wavelets. Commun. Pure Math. Appl., 45:485–560 (1992) · Zbl 0776.42020 · doi:10.1002/cpa.3160450502
[10] Heinig, G., Rost, K. Representations of Toeplitz-plus-Hankel matrices using trigonometric transformations with applications to fast matrix-vector multiplication. Linear Algebra Appl., 275/276:225–248 (1998) · Zbl 0935.65040 · doi:10.1016/S0024-3795(97)10024-6
[11] Kok, C.W. Fast algorithm for computing discrete cosine transform. IEEE Trans. Signal Processing, 45:757–760 (1997) · doi:10.1109/78.558495
[12] Michael, K. Ng., Sun, H.W., Jin, X.Q. Recursive-based PCG method for Topelitz systemes with honnegartive generating functions. SIAM, J. Sci. Comput, 24:1507–1529 (2003) · Zbl 1037.65036 · doi:10.1137/S1064827500378155
[13] Ohsmnn, M. Fast cosine transform of Toeplitz matrices:algorithm and applications. IEEE Trans. Signal Processing, 41:3057–3061 (1993) · Zbl 0783.65092 · doi:10.1109/78.277808
[14] Ohsmnn, M. Fast transforms of Toeplitz matrices. Linear Algebra Appl., 231:181–192 (1995) · Zbl 0838.65044 · doi:10.1016/0024-3795(95)90020-9
[15] Said, A., Pearlman, W.A. A new fast and efficient image code based on set partitioning in hierarchical trees. IEEE Trans. Circuits Syst. Video Technol., 6:243–250 (1996) · doi:10.1109/76.499834
[16] Shapiro, J.M. Embedded image coding using zerotrees of wavelet coefficients. IEEE Trans. Signal Processing, 41:3445–3462 (1993) · Zbl 0841.94020 · doi:10.1109/78.258085
[17] Sun, H., Jin, X., Chang, Q. Convergence of the multigrid method for ill-conditioned Block Toeplitz Systems. BIT, 41:179–190 (2001) · Zbl 0991.65033 · doi:10.1023/A:1021978020255
[18] Wei, D., Tian, J., Wells, O. Raymond, Burrus, S.C. A new class of biorthogonal wavelet systems for image transform coding. IEEE Trans. Image Processing, 7:1000–1013 (1998) · Zbl 0973.94005 · doi:10.1109/83.701157
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.