Wavelets, Approximation,and CompressionMartin VetterliOver the last decade or so, wavelets have had agrowing impact on signal processing theoryand practice, both because of their unifyingrole and their successes in applications (seealso [42] and [38] in this issue). Filter banks, which lie atthe heart of wavelet-based algorithms, have become stan-dard signal processing operators, used routinely in appli-cations ranging from compression to modems. Thecontributions of wavelets have often been in the subtle in-terplay between discrete-time and continuous-time signalprocessing. The purpose of this article is to look at recentwavelet advances from a signal processing perspective. Inparticular, approximation results are reviewed, and theimplication on compression algorithms is discussed. Newconstructions and open problems are also addressed.Bases, Approximation, andCompressionFinding a good basis to solve a problemdates at least back to Fourier and his in-vestigation of the heat equation [18].The series proposed by Fourier has sev-eral distinguishing features:▲The series is able to represent any fi-nite energy function on an interval.▲The basis functions are eigenfunctionsof linear shift invariant systems or, inother words, Fourier series diagonalizelinear, shift invariant operators.Similarly, the sinc basis used in thesampling theorem is able to representany bandlimited function, and process-ing can be done on samples instead ofthe function itself. In short, a basis ischosen both for its ability to represent an object of interest(for example, good approximation with few coefficients)and for its operational value (for example, diagonalizationof certain operators).To be more formal, assume we have a space of func-tionsSand we wish to represent an elementfS∈. ThespaceScan be, for example, integrable functions on the in-terval[,]01with finite square integralft dt()201∫<∞,(1)which we denoteL201(,). The first question is then to find abasis forS, that is a set of basis functions{}ϕiiI∈inSsuch thatany elementfS∈can be written as a linear combinationfiIii=∈∑αϕ. (2)The example closest to the heart of signal processingpeople is certainly the expansion of bandlimited functionsin terms of the sinc function. Assume the space of realfunctions bandlimited to[,]−π πin Fourier domain andhaving a finite square integral. We denote this space byBL2(,)−π π. Then the Shannon sampling theorem saysthat any function in that space can be written as [36], [28]ft t nnn() ( )=−=−∞∞∑α sinc,(3)whereαnfn= ()are the samples offt()at the integers, andsinc( )sin( )ttt=ππ(4)and its integer shifts are the basis func-tions.A question of immediate concern isin what sense (3) is actually true. Con-sider()ftNas the approximation usingNterms, withNan odd integer() ( )()/()/ft tnNnNNn=−=− −−∑1212α sincand a norm to measure the approxima-tion error. In this paper, we are solely concerned with theL2norm of the errorft ft ft ftdtNN()() ()()/−= −−∞∞∫2212.(5)Then we say that (3) is true in the sense thatSEPTEMBER 2001 IEEE SIGNAL PROCESSING MAGAZINE 591053-5888/01/$10.00©2001IEEE© 2001 IMAGESTATEAuthorized licensed use limited to: Univ of Calif Berkeley. Downloaded on March 29,2010 at 16:22:04 EDT from IEEE Xplore. Restrictions apply.lim ( )()NNft f t→∞−=20.(6)If we have a set of functions{}ϕiiI∈such that all func-tions inScan be approximated arbitrarily precisely as in(6), then we say that the set is complete inS. If further-more the elements are linearly independent, then we saythat{}ϕiiI∈is a basis forS. Among all possible bases, or-thogonal bases are particularly desirable. In that case, thebasis functions or basis vectors are all mutually orthogo-nal. Normalizing their norm to 1, orϕiiI21=∈,,anorthonormal set of vectors satisfiesϕϕ δij ij, =, (7)where the inner product.,.is defined asϕϕ ϕ ϕij i jttdt,()()*=−∞∞∫(8)in continuous time, and asϕϕ ϕ ϕij injnn,[][]*=∈∑⺪(9)in discrete time. (For discrete-time signals, we will con-sider the space of square summable sequences denoted bylZ2().) For orthonormal bases, the expansion formula (2)becomesffiiIi=∈∑ϕϕ,. (10)This is a representation formula forfin the orthonormalbasis{}ϕiiI∈.(More general formulas, for example inbiorthogonal bases or in frames, are also possible, but arenot needed for our discussion.) Given the representationoffin an orthonormal basis as in (10), its orthogonalprojection into a fixed subspace of dimensionNspannedby{}ϕnnN=−01…is denoted()ftN,ffNnnNn==−∑ϕϕ01.(11)This is the linear approximation offby a projectiononto a fixed subspace of dimensionN. It is linear be-cause the approximation ofαβfg+is equal to theweighted sum of approximations,αβfg+, as can bereadily verified. But this is only one of many possibleN-term approximations off. Thus, we are led to the ap-proximation problem: Given objects of interest andspaces in which they are embedded, we wish to know howfast anN-term approximation convergesft f t NN() () ~ ( )−2fct, (12)whereftN()stands for an approximation offt()whichinvolvesNelements, to be chosen appropriately.This immediately raises a number of questions. Differ-ent bases can give very different rates of approximation.Then, there are various ways to choose theNterms used inthe approximation. A fixed subset (e.g., the firstNterms)leads to a linear, subspace approximation as in (11).Adaptive schemes, to be discussed later, are nonlinear.Will different choices of the subset lead to different ratesof approximation? Such questions are at the heart of ap-proximation theory and are relevant when choosing a ba-sis and an approximation method for a given signalprocessing problem. For example, denoising in waveletbases has led to interesting results for piecewise smoothsignals precisely because of the superior approximationproperties of wavelets for such signals.We are now ready to address the last problem we shallconsider, namely the compression problem. This involvesnot only approximation quality, but also descriptioncomplexity. There is a cost associated with describingfN,and this cost depends on the approximation method.Typically, the coefficient values and their locations needto be described, which involves quantization of the coeffi-cients and indexing their locations.CallingRthe number of bits used in the description,we can define a function()DRas()DR f