Abstract. We present the lifting scheme, a simple construction of second generation wavelets; these are wavelets that are not necessarily translates and dilates of one fixed function. Such wavelets can be adapted to intervals, domains, surfaces, weights, and irregular samples. We show how the lifting scheme leads to a faster, in-place calculation of the wavelet transform. Several examples are included. Key words. wavelet, multiresolution, second generation wavelet, lifting scheme AMS subject classification. 42C15 PII. S0036141095289051 1. Introduction. Wavelets form a versatile tool for representing general functions or data sets. Essentially we can think of them as data building blocks. Their fundamental property is that they allow for representations which are efficient and which can be computed fast. In other words, wavelets are capable of quickly capturing the essence of a data set with only a small set of coefficients. This is based on the fact that most data sets have correlation both in time (or space) and frequency. Because of the time-frequency localization of wavelets, efficient representations can be obtained. Indeed, building blocks which already reflect the correlation present in the data lead to more compact representations. This is the key to applications. Over the last decade wavelets have found applications in numerous areas of mathematics, engineering, computer science, statistics, physics, etc. Wavelet functions ψ j,m are traditionally defined as the dyadic translates and dilates of one particular L 2 (R) function, the mother wavelet ψ: ψ j,m (x) = ψ(2 j x−m). We refer to such wavelets as first generation wavelets. In this paper we introduce a more general setting where the wavelets are not necessarily translates and dilates of each other but still enjoy all the powerful properties of first generation wavelets. These wavelets are referred to as second generation wavelets. We present the lifting scheme, a simple, but quite powerful, tool to construct second generation wavelets. Before we consider the generalization to the second generation case, let us review the properties of first generation wavelets which we would like to preserve. P1: Wavelets form a Riesz basis for L 2 (R) and an unconditional basis for a wide variety of function spaces F, such as Lebesgue, Lipschitz, Sobolev, and Besov spaces. If we denote the wavelet basis by {ψ j,m | j, m}, we can represent a general function f in F as f = j,m γ j,m ψ j,m , with unconditional convergence in the norm of F. Simple characterizations of the F-norm of f in terms of the absolute value of its wavelet coefficients γ j,m exist. * Received by the editors July 14, 1995; accepted for publication (in revised form) January 15, 1997. While writing this paper the author was employed at the Katholieke Universiteit Leuven, Belgium and the University of South Carolina, where he was partially supported by NSF EPSCoR grant EHR 9108772 and DARPA grant AFOSR F49620-93-1-0083. He is also on leave as Senior P2: One has explicit information concerning the coordinate functionals ψ j,m where γ j,m = ψ j,m (f ). The wavelets are either orthogonal or the dual (biorthogonal) wavelets are known. P3: The wavelets and their duals are local in space and frequency. Some wavelets are even compactly supported. The frequency localization follows from the smoothness of the wavelets (decay towards high frequencies) and the fact that they have vanishing polynomial moments (decay towards low frequencies). P4: Wavelets fit into the framework of multiresolution analysis. This leads to the fast wavelet transform, which allows us to pass between the function f and its wavelet coefficients γ j,m in linear time. These properties result in the fact that, quoted from Donoho in [58] , "wavelets are optimal bases for compressing, estimating, and recovering functions in F." Roughly speaking, for a general class of functions, the essential information contained in a function is captured by a small fraction of the wavelet coefficients. Again this is the key to applications. Wavelets have proved to be useful in various application domains such as signal and image processing, data compression, data transmission, the numerical solution of differential and integral equations, and noise reduction. Many first generation wavelet families have been constructed over the last ten years. We refer to the work of (in alphabetical order) Aldroubi and Unser [2, 3, 108, 107] [87] , and many more. Except for Donoho, they all rely on the Fourier transform as a basic construction tool. The reason is that translation and dilation become algebraic operations in the Fourier domain. In fact, in the early 1980s, several years before the above developments, Strömberg discovered the first orthogonal wavelets with a technique based on spline interpolation which does not rely on the Fourier transform [103] . The construction as initiated by Daubechies and coworkers essentially consists of three stages. The algebraic stage involves constructing the filters that are used in the fast wavelet transform; more precisely, it consists of finding certain polynomials and assuring that the above property P4 is satisfied. In the analytic stage, one shows that wavelets associated with these filters exist, that they are localized (property P3), and that they form a basis for the proper function space (property P1). In the geometrical stage, one checks the smoothness of the basis functions (property P3). In this context, we mention the work of Collela and Heil [37, 38] Let us next consider applications which illustrate the need for generalizations of first generation wavelets. G1: While first generation wavelets provided bases for functions defined on R n , applications such as data segmentation and the solution of partial differential and integral equations on general domains require wavelets that are defined on arbitrary, possibly nonsmooth, domains of R n , as well as wavelets adapted to "life" on curves, surfaces, or manifolds. G2: Diagonalization of differential forms, analysis on curves and surfaces, and weighted approximation require a basis adapted to weighted measures; however, first generation wavelets typically provide bases only for spaces with translation invariant (Haar-Lebesgue) measures.
The lifting scheme REF allows us to construct critically sampled transforms whose basis functions can be adapted to the signal structure in a simple way.
The Lifting Scheme: A Construction Of Second Generation Wavelets
SIAM J. Math. Anal
Mathematics Computer Science