Factoring wavelet transforms into lifting steps. (English) Zbl 0913.42027

Given a signal \((x_k)_{k \in Z}\), we may split it into even \(x_e = (x_{2k})\) and odd \(x_o = (x_{2k+1})\) components. A lifting step is defined to be a transformation of the form \(x \mapsto (x_o, x_e - P(x_o))\), where \(P(x_o)\) is a linear predictor for the even component based on the odd component. (For instance, one could take \(P(x_o)_{2k} = (x_{2k-1} + x_{2k+1})/2\)). A dual lifting step is a transformation of the form \((x_o,d) \mapsto (x_o + U(d), d)\), where \(U(d)\) is an update operator to the odd components based upon the detail \(d = x_e - P(x_o)\). (For instance, one can take \(U(d)_{2k} = (d_{2k-1} + d_{2k+1})/4)\). In this paper the authors show that any finite impulse response (FIR) filter bank or wavelet transform can be factored into a sequence of lifting steps and dual lifting steps, each of which is also given by an FIR filter. The method of proof relies upon the z-transform and then a factorization of a Laurent polynomial-valued matrix into elementary matrices by means of the Euclidean algorithm.


42C40 Nontrigonometric harmonic analysis involving wavelets and other special systems
Full Text: DOI EuDML


[1] Aldroubi, A. and Unser, M. (1993). Families of multiresolution and wavelet spaces with optimal properties.Numer. Funct. Anal. Optim.,14, 417–446. · Zbl 0798.94007
[2] Bass, H. (1968).Algebraic K-Theory, W. A. Benjamin, New York. · Zbl 0174.30302
[3] Bellanger, M.G. and Daguet, J.L. (1974). TDM-FDM transmultiplexer: Digital polyphase and FFT.IEEE Trans. Commun.,22(9), 1199–1204.
[4] Blahut, R.E. (1984).Fast Algorithms for Digital Signal Processing. Addison-Wesley, Reading, MA. · Zbl 0579.94001
[5] Bruekens, A.A.M.L. and van den Enden, A.W.M. (1992). New networks for perfect inversion and perfect reconstruction.IEEE J. Selected Areas Commun.,10(1).
[6] Calderbank, R., Daubechies, I., Sweldens, W., and Yeo, B.-L. Wavelet transforms that map integers to integers.Appl. Comput. Harmon. Anal., (to appear). · Zbl 0941.42017
[7] Carnicer, J.M., Dahmen, W., and Peña, J.M. (1996). Local decompositions of refinable spaces.Appl. Comput. Harmon. Anal.,3, 127–153. · Zbl 0859.42025
[8] Chui, C.K. (1992).An Introduction to Wavelets. Academic Press, San Diego, CA. · Zbl 0925.42016
[9] Chui, C.K., Montefusco, L., and Puccio, L., Eds. (1994).Conference on Wavelets: Theory, Algorithms, and Applications. Academic Press, San Diego, CA. · Zbl 0816.00025
[10] Chui, C.K. and Wang, J.Z. (1991). A cardinal spline approach to wavelets.Proc. Amer. Math. Soc.,113, 785–793. · Zbl 0755.41008
[11] Chui, C.K. and Wang, J.Z. (1992). A general framework of compactly supported splines and wavelets.J. Approx. Theory,71(3), 263–304. · Zbl 0774.41013
[12] Cohen, A., Daubechies, I., and Feauveau, J. (1992). Bi-orthogonal bases of compactly supported wavelets.Comm. Pure Appl. Math.,45, 485–560. · Zbl 0776.42020
[13] Combes, J.M., Grossmann, A., and Tchamitchian, Ph. Eds. (1989).Wavelets: Time-Frequency Methods and Phase Space. Inverse problems and Theoretical Imaging. Springer-Verlag, New York. · Zbl 0718.00009
[14] Dahmen, W. and Micchelli, C.A. (1993). Banded matrices with banded inverses II: Locally finite decompositions of spline spaces.Constr. Approx.,9(2–3), 263–281. · Zbl 0784.15005
[15] Dahmen, W., Prössdorf, S., and Schneider, R. (1994). Multiscale methods for pseudo-differential equations on smooth manifolds. In [9], 385–424. · Zbl 0847.65081
[16] Daubechies, I. (1988). Orthonormal bases of compactly supported wavelets.Comm. Pure Appl. Math.,41, 909–996. · Zbl 0644.42026
[17] Daubechies, I. (1992).Ten Lectures on Wavelet. CBMS-NSF Regional Conf. Series in Appl. Math., vol. 61. Society for Industrial and Applied Mathematics, Philadelphia, PA.
[18] Daubechies, I., Grossmann, A., and Meyer, Y. (1986). Painless nonorthogonal expansions.J. Math. Phys.,27(5), 1271–1283. · Zbl 0608.46014
[19] Donoho, D.L. (1992). Interpolating wavelet transforms. Preprint, Department of Statistics, Stanford University.
[20] Van Dyck, R.E., Marshall, T.G., Chine, M. and Moayeri, N. (1996). Wavelet video coding with ladder structures and entropy-constrained quantization.IEEE Trans. Circuits Systems Video Tech.,6(5), 483–495.
[21] Frazier, M. and Jawerth, B. (1985). Decomposition of Besov spaces.Indiana Univ. Math. J.,34 (4), 777–799. · Zbl 0551.46018
[22] Grossmann, A. and Morlet, J. (1984). Decomposition of Hardy functions into square integrable wavelets of constant shape.SIAM J. Math. Anal.,15(4), 723–736. · Zbl 0578.42007
[23] Harten, A. (1996). Multiresolution representation of data: A general framework.SIAM J. Numer. Anal.,33 (3), 1205–1256. · Zbl 0861.65130
[24] Hartley, B. and Hawkes, T.O. (1983).Rings, Modules and Linear Algebra. Chapman and Hall, New York. · Zbl 0527.20001
[25] Herley, C. and Vetterli, M. (1993). Wavelets and recursive filter banks.IEEE Trans. Signal Process.,41(8), 2536–2556. · Zbl 0825.93871
[26] Jain, A.K. (1989).Fundamentals of Digital Image Processing. Prentice Hall, Englewood Cliffs, NJ. · Zbl 0744.68134
[27] Jayanat, N.S. and Noll, P. (1984).Digital Coding of Waveforms. Prentice Hall, Englewood Cliffs, NJ.
[28] Kalker, T.A.C.M. and Shah, I. (1992). Ladder Structures for multidimensional linear phase perfect reconstruction filter banks and wavelets. InProceedings of the SPIE Conference on Visual Communications and Image Processing (Boston), 12–20.
[29] Lounsbery, M., DeRose, T.D., and Warren, J. (1997). Multiresolution surfaces of arbitrary topological type.ACM Trans. on Graphics,16(1), 34–73. · Zbl 05468665
[30] Mallat, S.G. (1989). Multifrequency channel decompositions of images and wavelet models.IEEE Trans. Acoust. Speech Signal Process.,37(12), 2091–2110.
[31] Mallat, S.G. (1989). Multiresolution approximations and wavelet orthonormal bases of L2 (R).Trans. Amer. Math. Soc.,315(1), 69–87. · Zbl 0686.42018
[32] Marshall, T.G. (1993). A fast wavelet transform based upon the Euclidean algorithm. InConference on Information Science and Systems, Johns Hopkins, Maryland.
[33] Marshall, T.G. (1993). U-L block-triangular matrix and ladder realizations of subband coders. InProc. IEEE ICASSP, III: 177–180.
[34] Meyer, Y. (1990).Ondelettes et Opérateurs, I:Ondelettes, II:Opérateurs de Calderón-Zygmund, III: (with R. Coifman),Opérateurs multilinéaires. Hermann, Paris. English translation of first volume,Wavelets and Operators, is published by Cambridge University Press, 1993.
[35] Mintzer, F. (1985). Filters for distortion-free two-band multirate filter banks.IEEE Trans. Acoust. Speech Signal Process.,33, 626–630.
[36] Nguyen, T.Q. and Vaidyanathan, P.P. (1989). Two-channel perfect-reconstruction FIR QMF structures which yield linear-phase analysis and synthesis filters.IEEE Trans. Acoust. Speech Signal Process.,37, 676–690.
[37] Park, H.-J..A computational theory of Laurent polynomial rings and multidimensional FIR systems. PhD thesis, University of California, Berkeley, May 1995.
[38] Reissell, L.-M. (1996). Wavelet multiresolution representation of curves and surfaces.CVGIP: Graphical Models and Image Processing,58(2), 198–217. · Zbl 05473569
[39] Rioul, O. and Duhamel, P. (1992). Fast algorithms for discrete and continuous wavelet transforms.IEEE Trans. Inform. Theory,38(2), 569–586. · Zbl 0745.65086
[40] Schröder, P. and Sweldens, W. (1995). Spherical wavelets: Efficiently representing functions on the sphere.Computer Graphics Proceedings, (SIGGRAPH 95), 161–172. · Zbl 0970.42024
[41] Shah, I. and Kalker, T.A.C.M. (1994). On Ladder Structures and Linear Phase Conditions for Bi-Orthogonal Filter Banks. InProceedings of ICASSP-94,3, 181–184.
[42] Smith, M.J.T. and Barnwell, T.P. (1986). Exact reconstruction techniques for tree-structured subband coders.IEEE Trans. Acoust. Speech Signal Process.,34(3), 434–441.
[43] Strang, G. and Nguyen, T. (1996).Wavelets and Filter Banks. Wellesley, Cambridge, MA. · Zbl 1254.94002
[44] Sweldens, W. (1996). The lifting scheme: A custom-design construction of biorthogonal wavelets.Appl. Comput. Harmon. Anal.,3(2), 186–200. · Zbl 0874.65104
[45] Sweldens, W. (1997). The lifting scheme: A construction of second generation wavelets.SIAM J. Math. Anal.,29(2), 511–546. · Zbl 0911.42016
[46] Sweldens, W. and Schröder, P. (1996). Building your own wavelets at home. InWavelets in Computer Graphics, 15–87. ACM SIGGRAPH Course notes.
[47] Tian, J. and Wells, R.O. (1996). Vanishing moments and biorthogonal wavelets systems. InMathematics in Signal Processing IV. Institute of Mathematics and Its Applications Conference Series, Oxford University Press.
[48] Tolhuizen, L.M.G., Hollmann, H.D.L., and Kalker, T.A.C.M. (1995). On the realizability of bi-orthogonal M-dimensional 2-band filter banks.IEEE Trans. Signal Process.
[49] Unser, M., Aldroubi, A., and Eden, M. (1993). A family of polynomial spline wavelet transforms.Signal Process.,30, 141–162. · Zbl 0768.41012
[50] Vaidyanathan, P.P. (1987). Theory and design of M-channel maximally decimated quadrature mirror filters with arbitrary M, having perfect reconstruction property.IEEE Trans. Acoust. Speech Signal Process.,35(2), 476–492. · Zbl 0641.94002
[51] Vaidyanathan, P.P. and Hoang, P.-Q. (1988). Lattice structures for optimal design and robust implementation of two-band perfect reconstruction QMF banks.IEEE Trans. Acoust. Speech Signal Process.,36, 81–94.
[52] Vaidyanathan, P.P., Nguyen, T.Q., Doĝanata, Z., and Saramäki, T. (1989). Improved technique for design of perfect reconstruction FIR QMF banks with lossless polyphase matrices.IEEE Trans. Acoust. Speech Signal Process.,37(7), 1042–1055.
[53] Vetterli, M. (1986). Filter banks allowing perfect reconstruction.Signal Process.,10, 219–244.
[54] Vetterli, M. (1988) Running FIR and IIR filtering using multirate filter banks.IEEE Trans. Signal Process.,36, 730–738. · Zbl 0709.94566
[55] Vetterli, M. and Le Gall, D. (1989). Perfect reconstruction FIR filter banks: Some properties and factorizations.IEEE Trans. Acoust. Speech Signal Process.,37, 1057–1071.
[56] Vetterli, M. and Herley, C. (1992). Wavelets and filter banks: Theory and design.IEEE Trans. Acoust. Speech Signal Process.,40(9), 2207–2232. · Zbl 0825.94059
[57] Vetterli, M. and Kovačević, J. (1995).Wavelets and Subband Coding. Prentice Hall, Englewood Cliffs, NJ. · Zbl 0885.94002
[58] Wang, Y., M. Orchard, M., Reibman, A., and Vaishampayan, V. (1997). Redundancy rate-distortion analysis of multiple description coding using pairwise correlation transforms. InProc. IEEE ICIP, I, 608–611.
[59] Woods, J.W. and O’Neil, S.D. (1986). Subband coding of images.IEEE Trans. Acoust. Speech Signal Process. 34(5), 1278–1288.
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.