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

Daubechies, Ingrid; Sweldens, Wim

Klees, Roland (ed.) et al., Wavelets in the geosciences. Collection of the lecture notes of the school of wavelets in the geosciences, Delft, Netherlands, October 4-9, 1998. Berlin: Springer. Lect. Notes Earth Sci. 90, 131-157 (2000).

From the introduction: Various techniques to construct wavelet bases, or to factor existing wavelet filters into basic building blocks are known. One of these is lifting. The original motivation for developing lifting was to build second generation wavelets, i.e., wavelets adapted to situations that do not allow translation and dilation like non-Eculidean spaces. First generation wavelets are all translates and dilates of one or a few basic shapes; the Fourier transform is then the crucial tool for wavelet construction. A construction using lifting, on the contrary, is entirely spatial and therefore ideally suited for building second generation wavelets when Fourier techniques are no longer available. When restricted to the translation and dilation invariant case, or the “first generation”, lifting comes down to well-known ladder type structures and certain factoring algorithms.
In this paper we give a self-contained constructive proof of the standard factorization result and apply it to several popular wavelets. We consider the Laurent polynomial setting as opposed to the standard polynomial setting because it is more general, allows for symmetry and also poses some interesting questions concerning non-uniqueness.
This paper is organized as follows. In Section 2 we review some facts about filters and Laurent polynomials. Section 3 gives the basics behind wavelet transforms and the polyphase representation while Section 4 discusses the lifting scheme. We review the Euclidean algorithm in Section 5 before moving to the main factoring result in Section 6. Section 7 gives several examples. In Section 8 we show how lifting can reduce the computational complexity of the wavelet transform by a factor two. Finally, Section 9 contains comments.
For the entire collection see [Zbl 0948.00035].

MSC:

65T60	Numerical methods for wavelets
42C40	Nontrigonometric harmonic analysis involving wavelets and other special systems

Keywords:

wavelet bases; wavelet filters; lifting; second generation wavelets; Fourier transform; factorization; Laurent polynomials; wavelet transforms; Euclidean algorithm; computational complexity