0.7 Generalizations of the basic multiresolution wavelet system  (Page 20/28)

Recent results indicate this nondecimated DWT, together with thresholding, may be the best denoising strategy [link] , [link] , [link] , [link] , [link] , [link] , [link] , [link] . The nondecimated DWT is shift invariant, is less affected by noise,quantization, and error, and has order $Nlog\left(N\right)$ storage and arithmetic complexity. It combines with thresholding to give denoising andcompression superior to the classical Donoho method for many examples. Further discussion of use of the RDWT can be found in Section: Nonlinear Filtering or Denoising with the DWT .

Adaptive construction of frames and bases

In the case of the redundant discrete wavelet transform just described, an overcomplete expansion system was constructed in such a way as to be atight frame. This allowed a single linear shift-invariant system to describe a very wide set of signals, however, the description was adaptedto the characteristics of the signal. Recent research has been quite successful in constructing expansion systems adaptively soas to give high sparsity and superresolution but at a cost of added computation and being nonlinear. This section will look at some of therecent results in this area [link] , [link] , [link] , [link] .

While use of an adaptive paradigm results in a shift-invariant orthogonal transform, it is nonlinear. It has the property of $DWT\left\{af\right(x\left)\right\}=aDWT\left\{f\right(x\left)\right\}$ , but it does not satisfy superposition, i.e. $DWT\left\{f\right(x)+g(x\left)\right\}\ne DWT\left\{f\right(x\left)\right\}+DWT\left\{g\right(x\left)\right\}$ . That can sometimes be a problem.

Since these finite dimensional overcomplete systems are a frame, a subset of the expansion vectors can be chosen to be a basis while keepingmost of the desirable properties of the frame. This is described well by Chen and Donoho in [link] , [link] . Several of these methods are outlined as follows:

• The method of frames (MOF) was first described by Daubechies [link] , [link] , [link] and uses the rather straightforward idea of solving the overcomplete frame (underdetermined set of equations) in [link] by minimizing the $L^2$ norm of $\alpha$ . Indeed, this is one of the classical definitions of solving the normal equations or use of apseudo-inverse. That can easily be done in Matlab by a = pinv(X)*y . This gives a frame solution, but it is usually not sparse.
• The best orthogonal basis method (BOB) was proposed by Coifman and Wickerhauser [link] , [link] to adaptively choose a best basis from a large collection. The method is fast (order $NlogN$ ) but not necessarily sparse.
• Mallat and Zhang [link] proposed a sequential selection scheme called matching pursuit (MP) which builds a basis, vector by vector. Theefficiency of the algorithm depends on the order in which vectors are added. If poor choices are made early, it takes many terms to correct them. Typicallythis method also does not give sparse representations.
• A method called basis pursuit (BP) was proposed by Chen and Donoho [link] , [link] which solves [link] while minimizing the $L^1$ norm of $\alpha$ . This is done by linear programming and results in a globally optimal solution. It is similar in philosophy to the MOFs butuses an $L^1$ norm rather than an $L^2$ norm and uses linear programming to obtain the optimization. Using interior point methods, it is reasonablyefficient and usually gives a fairly sparse solution.
• Krim et al. describe a best basis method in [link] . Tewfik et al. propose a method called optimal subset selection in [link] and others are [link] , [link] .