Essential Wavelets for Statistical Applications and Data Analysis

[~((1

-

a) 1/d +

1)] }

2

(8.3)

The recursive method for choosing a threshold at each level consists of the following steps: 1. Compare the largest Xl with the critical point x d. 2. If the Xl is larger, this indicates that there is still significant signal among the coefficients. Remove the Xi with the largest absolute value from consideration, set d to d - 1, and return to Step 1. 3. If Xl < x d' then there is no strong evidence of strong signal among the (remaining) coefficients. The threshold for the current level is set equal to the largest remaining Xi in absolute value. By following this algorithm, we are throwing out "large" coefficients from the data set Xl, ... , X d until everything left (the set of "small" coefficients) is not distinguishable from pure noise. By setting the threshold equal to the maximum absolute value of the "small" coefficients, we are ensuring that they will all be shrunk to zero, and that each "large" coefficient will be included in the reconstruction, but shrunk toward zero by the same amount. Ogden and Parzen (1996a) point out that existing thresholding techniques (including the one just described) take into account only the relative magnitudes of the wavelet coefficients, but that there is also some information to be gained (as to whether signal is present in a particular set of coefficients) by the relative position of large coefficients. Figure 8.4 illustrates this point: It is a plot of the "true" wavelet coefficients at level j = 5 from a function with jumps at 0.25 and 0.75. Notice that while there is only one "very large"

Data Adaptive Wavelet Thresholding

153

• o ,....

•

lnU')

0>

.

.20 ell > .... c 0.

• .................................. ~ •. ¥ ..•••.••••.-

~ •....•••••••....•••, ••.•..••••..•

•

0>0

'0

•

:e0> o

•

•

t)

q

,....,

• 0.0

0.2

0.4

0.6

0.8

1.0

Figure 8.4: Coefficients at level 5 of a function (no noise added) with jumps at 0.25 and 0.75 coefficient per jump, they are flanked on both sides by other "large" coefficients. The approach of Ogden and Parzen (1996a) adapts standard change-point methods (which are closely related to classical goodness-of-fit techniques) to test the hypotheses given in (8.2). In the change-point problem with data Xl, ... , X d, nonparametric test statistics for the general hypotheses

H o : E[X 1] = E[X2 ] = ... = E[Xd ] H a : E[X 1] = ... = E[Xm ] "I E[Xm + l ] = ... = E[Xd] are based on the mean-corrected cumulative sum (CUSUM) process (see Csorgo and Horvath (1988) for a review of nonparametric change-point procedures). Typical functionals of this cumulative sum process are the maximum of the absolute value (Kolmogorov-Smirnov), the integral of the square (Cramer-von Mises), and a weighted integral of the squared process (Anderson-Darling). These test statistics in the change-point problem are the same as those used in goodness-of-fit situations. These tests are examples of omnibus tests that can be used to test the null hypothesis of equal means vs. a very wide variety of possible alternatives. The generality of the alternative hypothesis in this wavelet thresholding situation suggests that such an omnibus test would be appropriate. Thus, the approach of Ogden and Parzen (1996a) is to base the test for the hypotheses in (8.2) on the following process, which depends on the choice of a univariate function g: ~

< u < 1, o
154 where

THRESHOLD SELECTION BY HYPOTHESIS TESTING

(7(9)

i:

represents the standard deviation of the random variable g(Xi ):

"l9) =

g2(X)q,(X)

dx - {I: g(x)q,(x) dx}

2

Under the null hypothesis, the process (8.4) converges in distribution to a Brownian bridge stochastic process {B (t), 0 < t < I}, a continuous Gaussian process with B(O) = B(I) = 0, mean zero, and Cov[B(s) , B(t)] = min(s, t) -st (see Ross (1983) or Karlin and Taylor (1975) for more discussion on Gaussian stochastic processes). The heuristic of this approach is that one or more groups of large coefficients clustered together would cause B 1t) to exhibit an appreciable divergence from the typical behavior of a Brownian bridge process. It would be hoped that this atypical behavior would be detected by any of the omnibus test statistics mentioned previously. Though a wide range of choices for g(.) and for the Brownian bridge-based test statistic is possible, the paper by Ogden and Parzen (1996a) focuses on using g( x) = x 2 and the KolmogorovSmimov test statistic sUPO
Minimizing False Discovery

The approach to the threshold selection problem taken by Abramovich and Benjamini (1995), representing an interesting .application of concepts developed by Benjamini and Hochberg (1995), has as its goal the control of the

Data Adaptive Wavelet Thresholding

155

false discovery rate (FDR). This approach does not distinguish between coefficients at different levels, so it represents a data-dependent method for selecting a global threshold with which to shrink the empirical wavelet coefficients. Considering all n - 1 wavelet coefficients, there are n - 1 null hypotheses H o : Bj,k = 0 to be considered in such an approach. As stated before, in most applications, it is assumed that most of these null hypotheses are true (or, to be more precise, most of these hypotheses are "approximately true," in the sense that most coefficients are only negligibly different from zero, and thus are not needed in the reconstruction of f). The aim of this procedure is to limit the possibility of a coefficient being included in the reconstruction erroneously. In this context (in which each null hypothesis has a two-tailed counterpart as its alternative), a coefficient is said to be erroneously included if either H 0 is true (or approximately true) and the corresponding coefficients is included in the reconstruction, or if H o is false and the corresponding coefficient is included, but with the wrong sign. For any data dependent global thresholding scheme, define the random variable R to be the number of coefficients that are not shrunk to zero, or, equivalently, the number of coefficients that are included in the reconstruction. These included coefficients consist of two types: those included correctly, and those included erroneously, as defined in the previous paragraph. If Q is defined to be the number of coefficients incorrectly kept, then Abramovich and Benjamini (1995) attempt to control the proportion of erroneous conclusions Q/ R, which is defined to be zero whenever Q = R = o. The aim of this approach is to include as many coefficients as possible, provided that the expected value of Q/ R is kept below a user-specified value q. The authors point out that when the data are pure white noise (all "true" wavelet coefficients are identically zero), this approach amounts to controlling the probability of even one coefficient being kept in the reconstruction. Thus, in their examples and simulations, Abramovich and Benjamini (1995) use values for q that are commonly used for the Type I error probability in usual testing situations: 0.05 and 0.01. In view of this, one might consider using Q to denote this criterion value rather than q. The Abramovich-Benjamini method for choosing a data-dependent global threshold A consists of the following four steps: 1. Compute the usual p-value associated with each of the n - 1 sets of hypotheses:

2. Place the n - 1 Pj,k'S in increasing order:

156

CROSS-VALIDATION METHODS

3. Stepping through these ordered p-values beginning with i

= 1, let m

be the largest i for which ~

P(i)

< -q. m

4. Set

which is equal to p-value P(m).

Vii times the coefficient that corresponds with the

This procedure differs fundamentally from the other hypothesis testing-based approaches in that the Abramovich-Benjamini approach seeks to include as many coefficients as possible subject to a constraint. By contrast, the OgdenParzen procedures include a coefficient only when there is strong evidence that it is needed in the reconstruction. Abramovich and Benjamini (1995) report on a simulation study that compares their method (with both q = 0.05 and q = 0.01) with the VisuShrink algorithm of Donoho and Johnstone (1994) (with three different choices of the low-level cutoff jo) for a variety of functions. They conclude that this FDR approach works well (in terms of MSE) in comparison with the VisuShrink methods when the function of interest has several abrupt local changes; as might be expected given its nature, VisuShrink performs better when the underlying function is relatively smooth. As in the previous section, the user retains some control over the amount of smoothing that will be done by choosing the parameter q-a small value for q will allow only few coefficients to be included, giving a relatively smooth result. Conversely, large values for q will give a smoother estimate.

8.3

Cross-Validation Methods

The notion of cross-validation has emerged as a very useful data-driven method to choose smoothing parameters in a wide variety of estimation procedures. The main idea of cross-validation is to choose the smoothing parameter that gives the best estimator for predicting new observations. In practice, we often have only a single data set to use, with no immediate expectation of new data, so the data is reused to simulate new data being observed. A typical way to apply this principle is the standard "leave one out" crossvalidation algorithm. For each value of a general smoothing parameter ,\ (which can be regarded as a bandwidth in kernel smoothing), single data values are left out in turn, and the remaining n - 1 data points are used to obtain an estimate of f and then a "prediction" of the left out data point. A measure

Data Adaptive Wavelet Thresholding

157

of this success in prediction is given by 1

CV(A)

n

= -n.L

~

2

(Yi - Yi) ,

l=l

Yi

where Yi denotes the "prediction" of using only the other n -1 data points. The smaller the cross-validation function, the closer the predictions are to the actual observed data values. In practice, CV( A) is computed for a grid of possible A values, and the final smoothing parameter value ACV is chosen to be the minimizer of the CV function. More details can be found in Stone (1978), who reviews cross-validation techniques in practice. These ideas are extended to generalized cross-validation by Craven and Wahba (1979). Lately, a good deal of attention has been focused on applying general crossvalidation ideas to wavelet regression. Early approaches include those by Weyrich and Warhola (1994) and Nason (1994). Following Nason (1994), we are interested in choosing a global threshold to minimize the £2 risk in recovering the unknown function I. Thus, the objective function is given by

M(t) = E [ [

(it(X) - !(x)f dX] ,

(8.5)

~

where It is the wavelet estimator that results from applying a threshold t globally to all wavelet coefficients. In practice, this can never be computed (as I is unknown), so M(t) must be estimated in some way. In the model considered in this chapter, we are content to consider only the discretized version of (8.5):

By the wavelet version of Parseval's identity (4.32), this can be expressed in the wavelet domain:

m(t) = E [n

y~ (0;,. -

OJ,'

)2] ,

where OJ,k represents the estimate of the "true" coefficient Bj,k computed from the soft thresholding function with threshold t:

158

CROSS-VALIDATION METHODS

The first question of interest in this approach involves the behavior of the objective function m(t): In particular, given knowledge of f (equivalently, given knowledge of the ()j,k'S), is it possible to minimize the function m(t)? Standard calculus concepts would suggest taking the first derivative of m(t), solving for the to which gives m'(to) = 0, then verifying that to is indeed a minimum by checking the sign of the second derivative of m at to. Unfortunately, this cannot be used, as the soft thresholding function bt applied to data values is not everywhere differentiable with respect to t. Nason (1994) examines this question at length, noting that the derivative m' (t) is piecewise linear with discontinuities at each IvnwJ~21. With high probability, however, the jumps at these points are small in the area where the minimum is likely to occur. By this and additional arguments about the behavior of m (t) for t = 0, Nason concludes that the function m(t) is "almost convex" and can thus be effectively minimized. The usual method of cross-validation cannot be applied directly to estimation with wavelets because efficient algorithms are not yet available for computing the discrete wavelet transform using an orthogonal wavelet with non-uniform designs. Nason (1994) suggests breaking the original data set YI , ... ,Yn into two subsets of equal size: one containing only the evenindexed data, and the other, the odd-indexed data. The odd data will be used to "predict" the even data, and vice versa. To be more specific, we must introduce some notation. Let YIO , Y? , ... 'Y;;2 represent the (re-ordered) odd data points and y IE , ••• , Y;/2 the similarly renumbered even data values. The usual wavelet estimator based on the even-indexed points, denoted jE, consists of estimates of the function f at the points 2/n, 4/n, , (n - 2)/n, 1; that using the odd data points jo estimates f at I/n, 3/n, , (n - I)/n. To compare these estimated points directly with original data values, we employ "wrapped around" interpolated versions of each subset:

t(Y2i -

I

z(Yn -

I

+ Y2i + I ), + YI ),

i=I, ... i -- !!2'

,~-I,

for the odd data, and

+ Y2 ), z(Y2i - 2 + Y2i ), t(Yn

,; -1 - , .~ = 2 ,... , 2' n ~

for the even data. Note that the indices on these interpolated versions of the data coincide with the indexing of the subsets of the data, and hence, of the estimators resulting from the subsets. Also, note that the interpolation scheme described above wraps the data around the interval [0, 1], which corresponds to periodic boundary handling. The cross-validation approach will

Data Adaptive Wavelet Thresholding

159

minimize the following estimate ofm(t):

(8.6)

The Parseval relation can be applied to this expression as well. Defining for the moment {WJ,k} and {W7,k} to be the wavelet coefficients for the evenand odd-indexed data respectively, with {WJ,k} and {W7,k} representing the wavelet coefficients resulting from the respective interpolated sequences, the expression (8.6) can be rewritten

This function can then be minimized over t, giving the "best" threshold for half-sample prediction: . (t) . = arg ffi1ll t 2:0 m

\ n/2 Acv

A

(8.7)

This minimum must be computed numerically, and though any of a number of algorithms could be applied to find the minimum, Nason recommends the simple golden section search given in Press, et al. (1992). The selected threshold (8. 7) is not the best to apply to the full data set, however. Note the dependence of the universal threshold of Donoho and Johnstone (1994) on the sample size n:

Au = V2log n . Since

AV

2

= y'2Iog(n/2), the relationship between the two thresholds is \n

_

AU -

(

log 2 1 - - -) logn

-1/2 \n

AU'

(8.8)

The final threshold to use with the full data set results from applying the correction (8.8) to the cross-validation threshold for the half-samples. Nason (1996) describes an alternative scheme that uses the more traditionalleave-one-out cross-validation idea, which can be applied to a data set of any size (not necessarily a power of two). As mentioned before, efficient algorithms do not exist for computing the discrete wavelet transform for unequally spaced data, or when n is not a power of two. Nason gets around this restriction by applying two of the methods described in Section 6.4: reflection and padding. The basic idea behind this approach, described in more

160

CROSS-VALIDATION METHODS

detail presently, is that, for each data value Yi, the data set is broken into two pieces around it, and each piece is used separately to predict Yi. To predict Yi, break the data set into a left half and a right half:

= {Y1 , ... , Yi-d R = {Yi+l"'" Yn }.

L

The sets L and R are reflected completely at the left and right ends respectively (giving 2i - 2 points in the reflected left set and 2n - 2i points in the reflected right set). These are each extended to the next larger power of two by repeating the extreme values to obtain

= {Yi-l,'"

Yi-l' Yi-2, ... , Y2, Y1, Y1, Y2,... ,Yi-2' Yi-d R* = {Yi+l, Yi+2, ... , Yn - l , Yn , Yn , Yn - l , ... , Yi z , Yi+l, ... , Yi+d· L*

The usual wavelet threshold estimators are formed for each half of the data using the global threshold value t, giving jf and R , respectively. The prediction of the left-out point Yi is the average of the right-most value of jf and the left-most value of R . Denoting this prediction value the estimate of m ( t) in this case is given by

it

lt

Yi,

n-l

m(t)

=

2: (Yi - Yi)2 i=2

The leave-one-out cross-validation threshold is simply the minimizer of m(t) (no adjustment needed). Nason (1995) points out that these cross-validation methods work well when the assumption of Gaussian and independent noise holds. In cases for which this does not hold (if the error distribution has heavier tails and/or correlated noise), these wavelet cross-validation techniques do not work well. It is well documented (see, for example, Altman (1990) and Hart (1994)) that usual cross-validation for other smoothing methods have problems when the errors are correlated, so it is perhaps no surprise to find this holds in the wavelet shrinkage situation as well. Wang (1996) studies the problem with correlated errors in depth, proposing cross-validation methods for use with long-memory data, and laying the theoretical framework of such methods. It is generally agreed (see Nason (1995) and Johnstone and Silverman (1995)) that threshold selection should be done level-by-level for correlated data. Thus, Wang (1996) proposes two such methods: a level-specific universal-type threshold resulting from multiplying -}2 log n by a correction factor to account for the level and the noise

Data Adaptive Wavelet Thresholding

161

correlation structure; and a level-dependent cross-validation method that represents an extension of Nason's methods involving removing more than half the data each time. More details are given in the paper by Wang and in Nason (1995).

8.4 Bayesian Methods Recently, methods have been proposed in wavelet function estimation that involve Bayesian principles. These offer an interesting and useful alternative to the methods presented in earlier sections. It should be noted that Bayesian methods for function estimation with wavelets involve a more involved problem than simple threshold selection, in the sense that new shrinkage functions result from the Bayesian approach, different from either the soft or hard thresholding functions discussed previously. Vidakovic (1994) describes two related Bayesian approaches for "thresholding" the empirical coefficients. The first is based on Bayesian estimation using each wJ~2 to estimate the corresponding OJ,k' This approach results in a Bayes rule for the estimation. The second, a true threshold selection scheme for the hard thresholding operator, involves Bayesian testing of each hypothesis H o : OJ,k = 0 vs. a two-sided alternative for each j and k similar in spirit to the methods of Section 8.2. These two methods will be summarized here briefly. For simplification of notation, we drop the subscripts, considering the estimation or testing of each coefficient separately. The distribution of the empirical coefficient w is

(Note that in terms of our earlier notation, ry2 = distribution is placed on ry2,

(J2 In.)

An exponential prior

and to focus attention on 0, we integrate out ry2 to give that the marginal distribution of w conditioned on 0 is double exponential:

Applying a symmetric prior distribution on 0: 0 ,...., 7r(O) where

7r( 0) = 7r( -0), 0

E

JR,

162

BAYESIAN METHODS

allows estimation of the "true" coefficient 0 using the empirical coefficient w according to the following Bayes rule, based on squared error loss:

where III and II 2 are the Laplace transforms of 7r( 0 + w) and 7r( 0 - w) respectively:

and similarly for II 2 . There are many possibilities for the choice of 7r(O). Vidakovic recommends using the Student t distribution rather than the normal:

where 7 is a scaling hyperparameter and v is the degree of freedom index. The Bayes rules thus derived are simply smooth shrinkage functions and can be thought of as competitors to the soft and hard thresholding shrinkage functions discussed earlier. The behavior of these functions depends upon the hyperparameters used in describing the distributions of ry2 and O. For any choice of these hyperparameters, a commonality of these shrinkage functions and the hard and soft thresholding functions is that

t5(w)

~

0, for w near zero

and

t5(w) ~ w for Iwllarge. This only makes sense-in general "small" coefficients should be shrunk to near zero, and "large" coefficients should be retained more or less intact. An advantage of Vidakovic's Bayes rules is that these shrinkage functions can be fine-tuned by the choice of hyperparameter values. In particular, , is related to the precision of the original data: E[ry2] = 1/,. Increasing, is analogous to decreasing the threshold. The hyperparameter 7 controls the shrinking for small values of w: small values of 7 yield estimators very close to zero for small w. Vidakovic (1994) gives several illustrations of the Bayes rules that correspond to various choices of these hyperparameters. As mentioned earlier, the second method proposed by Vidakovic (1994) is a Bayesian method for selecting the threshold value for use with the usual hard thresholding operator. This involves testing the precise hypothesis H o :

Data Adaptive Wavelet Thresholding

B=

163

°vs. a two-sided alternative according to the Bayesian framework, which

requires that point mass of the distribution of B be placed on zero. Thus, the prior on B becomes

B rv 7r(B)

= p~(B) + (1 -

p){(B),

where ~ is the Dirac delta function introduced in Section 2.1. Note that P[B = 0] = p and the density ~ describes the behavior of B when B is non-zero (which occurs with probability 1 - p). As before, using the double exponential distribution of w conditioned on B and applying the usual Bayes methods for hypothesis testing dictates that the empirical coefficient will be "thresholded" if

where III (.) and Il 2 ( .) are as before. As might be expected, increasing p has the effect of increasing the threshold value, as it corresponds to increasing surety about the sparsity of the wavelet representation of the data. In practice, it is believed that most of the Bj,k'S are zero, so the hyperparameter p should be chosen to be close to one to represent this. Vidakovic suggests using the Student's t distribution for { in the Bayes factor setting as well. In either of these two schemes, the hyperparameter 'Y can be estimated from the data, giving an empirical Bayes procedure: 'Y n / a- 2 for some estimator of (J2 • Another approach to Bayesian estimation of wavelet coefficients is due to Chipman, Kolaczyk, and McCulloch (1995). Their approach, which gives level-dependent Bayes rules for shrinking coefficients, has an advantage over Vidakovic's method in that their shrinkage functions are in closed form. Their approach assumes the noise level (J to be a known constant, and they apply a normal mixture distribution to each coefficient Bj,k:

=

The mixing parameters are assumed to have independent Bernoulli(pj) distributions with Pbj,k

= 1] = Pj = 1 -

Pbj,k

= 0].

Note that the prior distributions are identical for all coefficients in any resolution level j. The hyperparameter Tj is taken to be small, so that the N(O, TJ) portion of the prior on Bj,k represented concentrating mass near zero, which

164

BAYESIAN METHODS

corresponds to a coefficient being "negligible." Then Cj is taken to be substantially larger, so that the N(O, CJ7]) component allows "significant" coefficients. The Bernoulli probability Pj plays essentially the same role here as it did in the model of Vidakovic (1994), corresponding to the a priori knowledge about the degree of sparsity in the wavelet representation. More will be said on particular choices of the hyperparameters later. Again, the distribution of the empirical coefficient w)~2 conditional on the "true" coefficient Bj,k is

where ry2 = (J2 / n as before. Again, dropping coefficients to simplify notation, Chipman, et al., use W to estimate B by means of the posterior mean of B:

EBw -

[ I ]-

{

I}

2

P 7 ._-+ ·-_·w ry2 + (C7) 2 P + 1 ry2 + 7 2 P + 1 ' ( C7) 2

(8.9)

where p

P7r(wh' = 1) = ----'--'--:----'-(1 - p)7r(wh' = 0)

and

7r(Wh' = 1)

rv

7r(wh' = 0)

rv

+ C2 7 2 ) N(O, ry2 + 7 2). N(O, ry2

Note that (8.9) looks like a simple multiplication of the coefficient factor

s=

(C7)2

P

7

2

W

by the

1

.--+ .-ry2 + (C7) 2 P + 1 ry2 + 7 2 P + 1 '

where lsi < 1, but, in fact, s is itself a function of w, so (8.9) is indeed a nonlinear shrinkage function of w. As in the Bayesian approach described earlier in this chapter, this method depends heavily upon the choice of values used for the hyperparameters 7j, Cj, and Pj. These must be chosen to quantify the notions of "small," "large," and "most," respectively, in order to correspond with the sparsity of representation belief that "most of the coefficients are small (negligible); the others are large." Thus 7j must be chosen small enough that a coefficient B j,k E (-37j, 37j) is negligible. At the same time, Cj must be chosen large enough to model plausible values of Bj,k reasonably. The probability Pj rep' resents the expectation of the proportion of significant coefficients at level

Data Adaptive Wavelet Thresholding

165

j. Chipman, et al., suggest that the sequence Pi be chosen to decrease as j increases, since, at high levels, relatively fewer coefficients are needed to represent the function well. Automatic rules depending on the wavelet used and the data are given in their paper for use as default values for these hyperparameters. An advantage to this approach is that Bayesian confidence bands can be derived by considering the variance (as well as the mean) of the posterior distribution of the OJ ,k 'So If the vector 0 represents the discrete wavelet transformation of the sequence 1 = (1(1/n), . .. , 1((n - l)/n, 1(1))':

0=

W1,

then the Bayesian estimate of the sequence 1 will be

j

=

W'E[Olw].

Now the variance-covariance matrix of the resulting estimator is given by Var(j) = ~ = W'diag{Var(Olw)}W, and Bayesian posterior intervals for

1 are given by

1 ± 3Jdiag(~).

CHAPTER

NINE

Generalizations and Extensions

Previous chapters have given the hows and whys of wavelets, and have discussed wavelet applications in statistics. The one-dimensional wavelet transform that has been the primary focus is only a small portion of all waveletbased methods available. In this chapter, we give an overview of some of the important extensions of standard wavelet methods, and briefly consider their uses in statistics.

9.1

Two-Dimensional Wavelets

This book has dealt only with unidimensional wavelet methods, but most of these methods have multidimensional counterparts. This section describes the construction of two-dimensional wavelets. The extension to more than two dimensions can be accomplished by similar means. Here, we consider analYZing two-dimensional signals f (x, y) which are square integrable over the real plane: f(x, y) E L 2(JR2). The simplest way of constructing a wavelet basis for L 2(JR) is to take the simple product of unidimensional wavelets:

It is straightforward to show that the 'li's as defined above are indeed wavelets

and that they form an orthonormal basis for L 2(JR2).

168

TWO-DIMENSIONAL WAVELETS

But this approach is too simplistic to retain the nice features of the multiresolution analysis. Let us begin extending our one-dimensional MRA by defining the two-dimensional space V 0 as the tensor product of two onedimensional spaces:

V o = Vo 0 Vo = span{1(x)g(y), 1,g E Vol· For any j, define V j = Vj 0 Vj, and then this set of subspaces inherits the two-dimensional versions of the MRA properties listed in Section 1.2:

1.

... C V

2.

njEZV j = {(O,O)}, UjEZV j = £2(JR2);

3. 4.

1 E V j if and only if 1(2',2·) E V j + 1 ; 1 E V o implies 1(' - k 1 ,' - k 2 ) E V o for all k 1 , k 2

-2

C V-I C V o C VI C V 2 C ... ;

E 7L

Also, defining (x, y) = ¢(x)¢(y) and

(9.1)

we have that

5.

The set {cI>j,k 1 ,k2' j, k 1, k 2 E 7Z} constitutes an orthonormal basis for Yo.

Notice that this setup differs from the previously mentioned one by allowing only a single dilation index. To continue this extension into two-dimensions, we would next like to find complimentary spaces that represent the "detail signal" between successive approximations. As in the one-dimensional case, define W j to be the orthogonal complement of V j in V j+l. Breaking down this MRA gives more insight into the nature of the space W j :

V j +1

VJ+l 0 VJ+l

(Vj EB Wj) 0 (Vj EB Wj) Vj 0 Vj EB ((Vj 0 Wj) EB (Wj 0 Vj) EB (Wj 0 Wj)) V j EB Wj.

Generalizations and Extensions It can be seen that the "detail space" W

169

is itself made up of three orthogonal subspaces. Bases for these three sub-detail spaces are the corresponding tensor products of their components, so define the following twodimensional wavelets: j

\lJI(X,y)

¢(x)'ljJ(y);

\lJZ(x, y)

'ljJ(x)¢(y);

\lJ3(x, y)

'ljJ(x )'ljJ(y).

Dilating and translating as in (9.1), it is clear that an orthonormal basis for W is

j

where

It follows that an orthonormal basis for £Z(JRZ) is

{\lJJ"!"k k ,m , 1, 2

= 1,2,3, j, k l , k z E Z}.

Mallat (l989a) notes that the three sets of wavelets correspond to specific spatial orientations. The "detail image" associated with each of these three orientations will give emphasis to edges in the image in the indicated direction. Specifically, the wavelet \lJ 1 corresponds to the horizontal direction, the wavelet \lJz with the vertical direction, and \lJ3 with the diagonal. Naturally, the decomposition and reconstruction algorithms for the two dimensional case are closely related to the corresponding one-dimensional algorithms. By applying the two-scale relationship (4.7) twice to the twodimensional wavelet in (9.1), we arrive at the two dimensional two-scale relationship: iP j ,k 1 ,k2(X,y) =

2: 2: hfl-Zklhf2-zk2iPj+l,fl,f2(X,y). f 1 EZf 2 EZ

Applying the result in (4.13) twice gives an analogous result in two dimensions, relating a scaling function at any level to scaling functions and wavelets at a coarser level:

170

Cj

TWO-DIMENSIONAL WAVELETS

~

H----'O-..-_"--(rows)

"

H (columns)

::---------"----~--~

C j-I

D~J- 1

H (columns)

2 .. D.J1

::--------~-----"--- ~

Figure 9.1: Schematic diagram of the two-dimensional wavelet decomposition

2: 2: {au1-kl aU 2-k2

cI>j-I'£I'£2 (x,

y)

£IEZ£2EZ

+ aU1-k l bU2-k2WJ-I'£l ,£2 (x, y) + bU1-k l aU 2-k2W~-I'£l ,£2 (x, y) + bUl-klbu2-k2WJ-I,£I,£2(X,y)}. Naturally, analogous versions of these formulas are applied to give the decomposition and reconstruction algorithms for coefficients, which again can be represented in terms of the high pass and low pass filters discussed in Section 4.2. The decomposition is the result of a two-step process, which is represented schematically in Figure 9.1. To begin with, we regard the matrix of scaling function coefficients as a two-dimensional signal, each row being thought of as a separate (one-dimensional) signal. The first step consists of applying filters H and G to each row of the matrix, the intermediate results being two matrices with the same number of rows but half as many columns as the original matrix. Regarding each of these matrices as consisting of columns of (one-dimensional) signals, the filters H and G are applied to the columns, giving four final square matrices, each with half as many rows and half as many columns as the original matrix. The four resultant matrices correspond to the scaling function and the three wavelets described earlier. The matrix C j - I is a "smoothing" of the higher-level scaling coefficients, and the matrices D} - I '

Generalizations and Extensions

Dj+3

Dj+2

171

D]+3

D]+2 D;+3

Dj+1 0J+I D;+2 C·J D;+I

Figure 9.2: Two-dimensional signal decomposition

DJ

DJ

represent the horizontal, vertical, and diagonal detail components, respectively. A very common example of a two-dimensional signal is a digital image, consisting of a matrix of pixel values, to be plotted on the grey-scale. The wavelet decomposition of an image can begin by regarding the original matrix elements as the top-level scaling function coeffiCients, as was done in the onedimensional case in Section 6.2. The matrix of scaling function coefficients that result from a one-level decomposition is a "smoothing" of the original image. The other three matrices represent "detail images," each according to its directional orientation. The results of the two-dimensional wavelet decomposition are conveniently stored in the format displayed in Figure 9.2, similar to that of Mallat (l989b). If the decomposition were to proceed further, the square in the lower left-hand corner of the figure would be replaced by four equally sized squares, the lower left-hand square in turn containing the matrix of scaling function coefficients at level j - 1. An example of the 2D wavelet decomposition, displayed as in Figure 9.2, is given for the "Lena" image in Figure 9.3. Note that the vertical details (side of arm, side of face) are represented in the lower right-hand portion of the -I'

-I'

172

TWO-DIMENSIONAL WAVELETS

Figure 9.3: Wavelet decomposition of the Lena image

plot, the horizontal details (top of shoulder, mouth) can be seen in the upper left-hand corner, and the diagonal details (hat brim, diagonal part of shoulder) are in the top right-hand corner. Figure 9.4 shows the original Lena image and its projection onto three V j approximation spaces. Note that reducing the resolution level by one results in a smoothed image that requires only 1/4 the number of coefficients to be stored. The general ideas behind extending wavelets from one to two dimensions could be employed to produce scaling functions, wavelets, and decomposition/reconstruction sequences for any number of dimensions, although the algorithms and interpretations get a little messy. Again, the focus of this book has been entirely upon one-dimensional procedures, but it is important

Generalizations and Extensions

173

Figure 9.4: Image multiresolution example with the Lena image: original image (upper left); reconstruction with J = 6 (upper right); reconstruction with J = 5 (lower left); reconstruction with J = 4 (lower right)

to keep in mind that analogous techniques could be developed for higherdimensional problems.

9.2

Wavelet Packets

The usual wavelet bases based on dilations and translations as described in Chapter 1 and used in various applications throughout this text provide an extremely useful tool for describing non-smooth functions (or signals). But these bases represent only one possibility. In this section, we discuss the notion of waveletpackets, and how they can be used to enhance the usual wavelet analysis.

174

WAVELET PACKETS

Wavelet Packet Functions Wavelet packets, a generalization of wavelets bases, are alternative bases that are formed by taking linear combinations of usual wavelet functions. These bases inherit properties such as orthonormality and smoothness from their corresponding wavelet functions. The basic idea is that by using wavelet packets, a large class of possible bases can be constructed (of which the usual wavelet basis is only one), and that for any particular application, the "best basis" can be chosen from this "library" of basis functions. Comparing one basis to another is done according to some user-defined criterion function, and a best basis algorithm exists for doing the automatic basis selection. Wavelet packets were originally constructed by Coifman and Meyer. Early references include Coifman, et al. (1994), Coifman, Meyer, and Wickerhauser (1992), Coifman and Meyer (1991). A wavelet packet function is a function with three indices: (t). Just as with usual wavelets, integers j and k index dilation and translation operations respectively:

wrk

where w m (no subscripts) is understood to have j = k = O. The extra index m = 0, 1, ... is called the modulation parameter or the oscillation parameter. The first two wavelet packet functions are known to us as the usual scaling function (father wavelet) and the mother wavelet respectively:

¢(x)

wO(x)

'ljJ(x)

w 1 (x).

Wavelet packet functions for m tionships w

2m

= 2,3, ... are defined by the recursive rela-

(x) =

L hkW~k(X)

(9.2)

k

and

W2m +1 (X)

= :~:::)-I)kh_k+lW~k(X)

(9.3)

k

for an appropriately chosen square-summable sequence {h k }. This is exactly the sequence used to express the two-scale relationships of wavelets and scaling functions in Section 4.1. In fact, note that for m = 0, equation (9.2) is just the two-scale relationship (4.1); for m = 1, the expression (9.3) is just the formula (4.4) expressing the mother wavelet in terms of the father wavelet.

Generalizations and Extensions

175

It is instructive to pause here and consider the wavelet packet functions

associated with the Haar basis. Recall that for the Haar system, the only nonzero coefficients in the {h k} sequence are ho = hI = 1/ V2. The Haar-based wavelet packet functions for m = 0, ... ,7 are plotted in Figure 9.5. The primary purpose of constructing such packets is to provide alternative bases for the same spaces that were spanned by dilated and translated scaling functions and wavelets. The first important obsenTation to make is that the set {wEr'k' , k E Z, m = 0, 1, ...} forms an orthonormal basis for 2 L (IR). In this representation, the dilation index is not needed at all. Alternative bases can be constructed for other subspaces of interest as well. Note in Figure 9.5 that as m increases (j = k = 0 for all the packet functions in the plot), the number of oscillations increases, too. This is the reason behind constructing a basis for L 2 (IR) without adjusting the dilation index, which might seem to imply that higher resolution can be attained without using the j dilation index. This is in fact the case. We saw in Chapter 1 that if Vi C L 2 (IR) is the space of functions that are piecewise constant with jumps at k2- j , k E Z, then an orthonormal basis for this space is the set of scaling functions {cPj,k, k E Z}. Another possible orthonormal basis for Vi is the set of wavelet packet functions

Since Vi+l = space" Wj is

Vi + Wj, it can be seen that an orthonormal basis for the "detail m (x) , 2 j { w O,k

j 1 < - m < 2 + k

E Z}.

The orthonormal bases we are familiar with for these spaces are written in terms of this new notation as {WJ,k' k E Z} for Vi and {W},k' k E Z} for Wj. In addition to these two examples of possible orthonormal bases, there are many others that can be used, the elements of which result from the appropriate choice of various combinations of the indices m, j, and k. To be more precise, a baSis for L 2 (IR) can be formed by allowing k to range over Z, and choosing an index set I = {(mo,jo), (ml,i!), ...} such that the intervals [2jimi, 2 ji (mi + 1)) are disjoint and "cover" the entire interval [0, 00): 00

U[2jimi, 2 ji (mi

+ 1)) =

[0,00).

(9.4)

i=l

This can be thought of as covering the entire time-frequency plane with windows of various shapes. It is easily shown that the usual wavelet basis forms such a cover: let (mo, jo) = (0,0), and then set ml = m2 = ... = 1 and let ji = i, for i = 1, 2, .. "

176

WAVELET PACKETS

Haar scaling function (m=O)

o

Haar mother wavelet (m=1)

..... co

o

U")

o o

o o

o

0

e...,.-----,-----,--.,....--...,---,-J

0.0

0.2

0.4

0.6

0.8

1.0

Packet function (m=2)

0r;::====:;--------''---;::====::;J ..... U")

I

0.0

0.8

1.0

Packet function (m=3)

~r;:::====:;-----;:==::::::::::::;---'---,

.....

o

~ L.---.,..--=::::::::;::==::::::::;;::::::::=--~--,J 0.0

0.2

0.4

0.6

0.8

1.0

~ L.,......----,-=::::;:::=---.-~;::::::::==~ I

0.0

Packet function (m=4) ..--

0.2

0.4

0.6

0.8

1.0

Packet function (m=5) ..--

..--

..--

U")

U")

o

o

o

o

o o

.....

.....

0.0

-

0.2

0.4

0.6

0.8

1.0

I

0.0

,..-

-

0.2

0.4

'----

0.6

0.8

1.0

Packet function (m=7)

Packet function (m=6) ,....--

,....--

...---

r--

...---

U")

U")

o

o

o

~

o

I

0.6

o

o

.....

0.4

o

o

I

0.2

U")

o

I

..... L.,.----,-----.-=:;::::==::;===~

o

'---

'----

0.0

0.2

0.4

0.6

0.8

1.0

..... I

'---

0.0

0.2

'---

0.4

~

0.6

~

0.8

1.0

Figure 9.5: Wavelet packet functions corresponding to the Haar system

Generalizations and Extensions

177

Though the previous discussion was given in terms of the Haar basis, the same results hold for all sets of wavelet packet functions and their associated subspaces Vi and Wj for j E 7L The collection of all wavelet packet functions {wrk' j, k E Z, m = 0, 1, ...} contains far too many elements to form an orthonormal basis. Care must be taken in choosing a subset of this collection in order to obtain a proper basis. Denoting by I a suitably chosen set of indices, decomposition of an L 2 (IR) function f into its wavelet packet components is given by

f(x)

= LL

LaJ:kWrk(X),

(m,j)EI kEZ

where the coefficients are computed via

Thus, wavelet packets offer an enormous amount of flexibility in possible sets of basis functions. The grouping of all possible bases is called a library of bases. For the idea of wavelet packets to be really useful in practical situations, there must be some good adaptive way to choose the most appropriate set of basis functions with which to represent a particular function. This is the aim of the best basis algorithm.

The Best Basis Algorithm As we moved from the discussion of the wavelet decomposition of continuous functions to the decomposition of discrete data earlier in this text, we do so now as well in our discussion of wavelet packets. This is perhaps a more natural way to describe the main conceptual points of wavelet packets and the associated best basis algorithm. Recall from Section 4.1 that a decomposition algorithm exists to compute scaling function and wavelet coefficients at level j from the scaling function coefficients at level j + 1, specifically Cj,k

= 2: hf-2k Cj+l,f, f

dj,k

= L(-I)fh_f+2k+l

Cj+l,k·

fEZ

Recall also from Section 6.2 that this algorithm was begun by regarding the data values Y1 , ... , Y n as the highest level scaling function coefficients from which all lower-level coefficients are ultimately computed. In Section 4.2, we

178

WAVELET PACKETS

noted that such a decomposition algorithm is a pair of filtering operations, and thus the two decomposition expressions above can be expressed Cj,.

= H Cj+l,.

d j ,. =

GCj+I,.,

where H and G represent the low-pass and high-pass filters associated with the respective decomposition formulas. Thus, if the data points are regarded as the scaling function coefficients at level J, then all scaling function coefficients are obtained by repeated application of the filter H:

where Y = (Y1 , ... , Y n )'. Similarly, wavelet coefficients are computed by applying the filter G after successive applications of H:

By recalling the usual wavelet decomposition of data, we are better equipped to describe the organization structure inherent in the wavelet packet decomposition.

HY HGY

Y

GY

G3y

Figure 9.6: Tree diagram of the usual wavelet decomposition algorithm

Generalizations and Extensions

179

The usual wavelet decomposition is displayed in a tree diagram in Figure 9.6. This idea is generalized to describe the wavelet packet decomposition. Each set of coefficients is subject to either of the filters H and G. Computing the full wavelet packet decomposition involves applying both filters to the Yi values and then recursively to each intermediate signal, giving the tree diagram in Figure 9.7. The decomposition of each signal at each node of the tree by applying the two filters is known as the splitting algorithm. By computing the full wavelet packet decomposition on a data vector Y with n = 2 J points depicted in Figure 9.7 for r resolution levels, the result is a group of 2 + 4 + 8 +... + 2 T = 2 T + 1 - 2 sets of coefficients. At each level, note that the downsampling inherent in the filtering ensures that there are n total coefficients among all the sets at that level. The total number of coefficients (including the original data values) is thus n(r+ 1), which is obviously a highly redundant way to represent n data values. Choosing a particular basis of wavelet packet functions amounts to "pruning" the decomposition tree. In the usual wavelet decomposition algorithm shown in Figure 9.6, each right-hand node is "pruned," meaning that lowerlevel decompositions are not computed from the right-hand branches. The best basis algorithm, developed by Coifman and Wickerhauser (1992), consists of traveling down the tree structure, making a data-based decision at each node as to whether or not to split. The result (when all nodes are split as far

H3y HZY GHzy HY HGHY GHY GZHY Y HZGY HGY GHGY GY HGzy GZY G3y

Figure 9.7: Tree diagram of the full wavelet packet decomposition algorithm

180

TRANSLATION INVARIANT WAVELET SMOOTHING

1\I~---' 1\

9S?

••

.~ ~~

0.0

0.2

0.4

0.6

0.8

1.0

Figure 9.8: Schematic design of the result of the best basis algorithm

as they will be split) represents the "best" basis (according to the criterion in use) for representing the particular set of data in question. This tree-based algorithm will automatically ensure that the resulting index set {(mo, io), (mI' iI), ...} will "cover" the interval [0, 00) in the best possible way (see (9.4)), guaranteeing an orthonormal basis for L 2 (JR). This tree-based approach is illustrated in two figures, Figure 9.8 denoting an arbitrary wavelet packet basis, and Figure 9.9 representing the usual wavelet basis. Note that the shaded boxes taken together should "cover" the entire width of the figure. In these figures, an unshaded box indicates that the box was split, so that it does not correspond directly to any element of the final basis. Of course, choosing a best basis begs the question as to what "best" means: the criterion function. Coifman and Wickerhauser (1992) focus primarily on the Shannon entropy measure. Other possibilities include counting the number of coefficients greater in absolute value than a given threshold.

9.3

Translation Invariant Wavelet Smoothing

One problem that wavelet bases have is the lack of translation invariance. To illustrate this point by example, consider the Haar basis decomposition of

Generalizations and Extensions

0.0

0.2

0.4

0.6

0.8

181

1.0

Figure 9.9: Schematic design of the usual wavelet decomposition

the function f(x) = 'ljJ(x) (the Haar wavelet). It is clear that do,o = 1 and all the other wavelet coefficients are identically zero. Now consider translating f to the right by a small amount 8: f(x) = 'ljJ(x - 8). This new function is of course still in LZ(JR) and thus can still be decomposed into its wavelet components, but it is clear to see that the nice coefficient structure of the original decomposition is lost. For the shifted function, there are two non-zero coefficients at level 0: (do,o, do, I) = (1 - 28,8), three non-zero coefficients at level 1: (dI,o, dI,I, dI,z) = V2( -8,8,8) and so on. If the shift 8 is taken to be an integer, then the nice structure is preserved: Now do,6 = 1 and all the other coefficients are zero, so the Haar wavelet decomposition is translation invariant under integral shifts, but not in general. No matter how an £z function f(x) is shifted, it is still in LZ(JR), and it can be written in terms of its wavelet components. Furthermore, the wavelet Parseval identity guarantees that the energy in the function is preserved in the total set of wavelet coefficients, regardless of how the energy is distributed among coefficients. It is true that the lack of translation invariance is not a real problem in this sense. It is a significant weakness, though, when applying wavelet methods to finite data sets, especially those with small or moderate sample sizes.

182

TRANSLATION INVARIANT WAVELET SMOOTHING

0.0

0.2

0.4

0.6

0.8

1.0

0.0

0.2

0.4

0.6

0.8

1.0

0.0

0.2

0.4

0.6

0.8

1.0

Figure 9.10: Wavelet reconstructions of translated versions of a data set

A simulated example of how this can affect a statistical estimator in practice is shown in Figure 9.10. The first data set consists of 64 N(2, 1) randomvariablesfollowedby64N(-2, 1) observations (f(x) = 2'l/J(x), theHaar wavelet, with a signal-to-noise ratio of 2). The other two sets of data are just translated versions of the first: Zi = Y(Hh)modn for h = 42 (corresponding to a leftward shift of 1/3) and h = 32 (corresponding to a shift of 1/4). These versions of the original data are actually "wrapped-around" translations of the original data, as if we were applying periodic boundary handling. For all three data sets, the universal threshold was applied to all levels of coefficients using the hard thresholding operator. The resulting wavelet estimator is shown along with each data set. The errors (l/n) 'E~=1 (j(i/n) - f(i/n))2 were computed for the three estimates, giving 0.031,0.045, and 2.157, respectively. It should come as no

Generalizations and Extensions

0.0

0.2

0.4

0.6

0.8

183

1.0

Figure 9.11: Translation-invariant wavelet estimator of simulated data uSing the Haar function, hard thresholding, and the universal threshold across all levels

surprise that the first estimate is quite good - the abrupt jump at 1/2 lines up exactly with the middle jump of the Haar wavelet 'l/Jo,o. The second estimate is not quite as good as the first, but is still quite good, since the pair of jumps at 1/4 and 3/4 line up exactly with the jumps in the wavelets 'l/JI,O and 'l/J 1,1. The third estimate illustrates what can go wrong in general. Shifting by 1/3 ensures that none of the wavelets will line up exactly. The estimation procedure does the best it can, but fails miserably. For general wavelet bases, the same phenomenon holds. Though it is not disastrous in every case, the wavelet thresholding estimator does not perform well for arbitrary translations. Coifman and Donoho (1995) make note of this problem, and also that the lack of translation invariance causes various spurious artifacts in the reconstruction of functions, such as Gibbs-type phenomena (rapid oscillations of high amplitude which are typical in Fourier reconstructions near jumps) near jump discontinuities. They propose an ingenious, yet simple solution, which is described in this section. One possibility, of course, would be to impose a shift on the data set before the decomposition takes place (in order to align apparent features of the data to avoid the problem seen in the third plot in the example), then decompose, shrink, reconstruct, and inverse-shift. In practice, however, it would be quite difficult to know the exact amount to shift the data (if at all). Instead, Coifman and Donoho propose to compute the wavelet estimator for all possible shifts, then inverse-shift them and take as a final estimate the average of the estimates resulting from all shift values. By "all possible shifts," we mean all n shifts of the data - conSidered on the unit interval, this will be shifts of j-by amounts i/n, for i = 1, ... , n. Though, as in the example,

184

TRANSLATION INVARIANT WAVELET SMOOTHING

0.0

0.2

0.4

0.6

0.8

1.0

Figure 9.12: Translation-invariant wavelet estimator of simulated data using Daubechies' N = 5 wavelet, soft thresholding, and the SURE thresholding scheme some shifts will likely give poor results, these can reasonably be expected to average themselves out over all possible shifts. This "Spin Cycle" algorithm is demonstrated in Figure 9.11 for the example data set from Figure 9.10. Note that since the second two data sets are just translated versions of the first, in this translation-invariance scheme, all three versions will give the same estimate. The estimation scheme used to produce Figure 9.11 was the same as that used in Figure 9.10: using the Haar wavelet basis with the universal threshold applied to all levels. The error for this example was 0.411, much worse than the 0.031 and 0.045 for the first two plots of Figure 9.10, but a great deal better than the third plot. Note that even though the Haar wavelet was used, averaging over 128 different estimators gave a fairly smooth final estimate. Figure 9.12 is a plot of the same data set, smoothed by applying the Spin Cycle algorithm with a smoother wavelet, soft thresholding, and the SURE threshold selection scheme. This estimator does a good job of picking up the jump at the middle (and the jump at the edges which is induced by periodic boundary handling), but is a little wavy through the "flat" parts of the data. The error for this estimate is 0.273.

Appendix

This book is concerned with £2 function space, and while the notion of function spaces may not be familiar to the reader at first, it can be readily understood by relating it to vector spaces in linear algebra. (It is presupposed that the reader has had some exposure to linear algebra.) Most of the specific material on £2 function space needed for this book is introduced as it is needed in Chapter 1. The following pages, while certainly not intended to be a complete discussion of vector spaces and functions spaces, are devoted to briefly reviewing some basic concepts from linear algebra and then extending them to general Hilbert spaces. In linear algebra, a vector in JRk is an ordered k-tuple of real numbers x = (XI,X2, ... ,Xk) which is viewed as a directed line segment from 0 = (0, ... ,0) to x. Two vectors x and yare said to be equal if Xi = Yi for each i = 1, ... , k. Two fundamental algebraic operations may be applied to vectors. Vector addition is the elementwise sum of two k-tuples:

while the scalar multiplication of a vector x and a scalar a E JR is

Note that both of these operations result in a new k-tuple. From these two basic properties, it is easily shown that addition of k-tuples is commutative and associative, and that various other algebraic properties hold. With these basic ideas, we turn next to the idea of vector spaces. The set of all ordered k-tuples is said to form the vector space JRk. The space JR2 is often represented by the usual X-Y plane. Three dimensional space corresponds with JR3, but higher-order vector spaces are difficult to visualize. Formally, a vector space is any set of vectors V which is closed under vector addition and scalar multiplication, i.e., for all x, y E V, a E JR,

x

+Y

E V and ax E V.

186

APPENDIX

These two operations must also satisfy a set of standard postulates, including commutativity, associativity, existence of a zero vector, etc. These postulates are listed in any basic linear algebra book. A subspace of a vector space V is a subset of vectors in V which is itself closed under addition and scalar multiplication. A subspace is also a vector space, so it must also include the zero vector and satisfy the other necessary postulates. In the vector space IR3 some examples of subspaces are the set consisting only of the zero vector; all vectors of the form (c, 0, 2c) for c E IR; and in fact any plane or any line which passes through the origin. To discuss a basis for a vector space, we need a few preliminary definitions. A vector y is a linear combination of the vectors x I, X2, ... , X m if it can be expressed

A set of vectors {Xl, X2, ... , X m } is said to be linearly dependent if the zero vector is a non-trivial linear combination ofthe Xi'S (non-trivial means that not all the ai's can be zero). Thus, if a set of non-zero vectors is linearly dependent, then at least one of the vectors can be written as a linear combination of the others. If a set of vectors is not linearly dependent, then it is linearly independent, which means that none of the vectors in the set can be written as a linear combination of the others. If every vector in a vector space V can be written as a linear combination of a set of vectors {X I, X2, ... , X n }, then it is said that these vectors span V. A set ofvectors { X I , X2, ... , x m } is said to be a basis for a vector space V if the vectors are linearly independent and span V. The concept of a basis is essential to a discussion of linear algebra. For a particular basis X I, X2, ... , X m , each vector in the space can be written in terms of the Xi'S:

and furthermore, the representation is unique. There are many possible bases (infinitely many, in fact) for each non-trivial vector space. A simple example of a basis for IRk is the standard basis: X I = (1,0,0, ... ,0)', X2 = (0,1,0, ... ,0)', ... , Xk = (0,0,0, ... , I)'. In fact, any set of k linearly independent vectors in IRk constitute a basis for IRk, and every possible basis for IRk will have exactly k vectors. The number of basis vectors for any vector space is known as the dimension of the space, with the dimension of the space {O} defined to be zero. A basis can be thought of geometrically as a set of coordinate axes. The standard basis is represented by the usual Euclidean axes. Any vector in the space has a unique representation in terms of these axes or bases. In Euclidean geometry, the well-known formula for the squared length of

Appendix

187

a vector x, a generalization of the Pythagorean theorem, is given by

Using the usual notation for the dot product (or scalarproduct between two vectors x and y: x .y =

XIYI

+ xzYz + ... + XkYk,

the angle between the vectors x and y can be computed according to

x·y cos f)

(9.5)

= IIxlllIyll'

To allow ready extension to other types of vector spaces, we will use the term inner product in place of dot product and write, for example, for k-tuples x andy, (x, y)

= XIYI + xzYz + ... + XkYk·

In terms of the inner product, the length of a vector x, which we will henceforth refer to as the norm of the vector, is given by

IIxll = (X,X)I/Z =

JXI +x~ + ... +x~.

From (9.5) it is seen that if two vectors have an inner product of zero, the angle between them is 90 degrees (rr /2 radians), and the vectors are said to be perpendicular, or orthogonal. Orthogonality may be difficult to visualize in more than three dimensions, but it is a key concept for this book. A set of vectors {XI, xz, ... , x m } forms an orthogonal basis for a vector space V if the vectors are a basis for V and if each pair of basis vectors is orthogonal. If each vector of an orthogonal basis for V is normalized to have length (norm) one: i = 1, ...

,m,

then the resulting set of vectors {y I' Yz, ... , Y m} constitutes an orthonormal basis for V. The notion of orthogonality extends to subspaces as well. Two subspaces V and W (both in the same vector space) are said to be orthogonal if every vector in V is orthogonal to every vector in W. If each vector of a basis for V is orthogonal to each vector of a basis for W, then this implies that the subspaces V and W are orthogonal.

188

APPENDIX

Every subspace W of a vector space V has an orthogonal complement in V, which consists of the set of all vectors in V which are orthogonal to W. It is straightforward to show that the orthogonal complement of a subspace is also a subspace. Given a vector x and a subspace W, the projection of x onto W is a vector y such that yEW and x - y is in the orthogonal complement of W in V. The projection operation is denoted y = P w x. The projection of a vector x onto a subspace W is the vector in W that is the "closest" to x, in the sense that the magnitude of the "error" Ilx - yll is minimized when y = Pwx. From the vector space JRk, we can extend to the infinite-dimensional space JR oo , which contains all infinite-length vectors x = (x 1 , X2, X3, •.. ) I with finite norm: IIxll = L:~l < 00. Though infinite-dimensional vector space might be hard to conceptualize, JRoo defined this way does form a bona fide vector space, since adding any two vectors with finite norm or multiplying by a finite scalar will result in another with finite norm. It is possible now to move from the countably infinite-dimensional vector space to uncountably infinite-dimensional vector spaces, which are simply spaces of functions. An element of this function space is a function f (x) defined on a continuous set of the real line. The notions of inner product and norm extend to function space as well, where the summation in vector space is replaced by its continuous counterpart, the integral. The inner product of two functions is given by

x;

(f,g) =

J

f(x)g(x) dx,

(9.6)

the range of the integration determined by the definition of the particular space. The treatment of vector spaces and function spaces can be unified by considering the more general framework of Hilbert spaces. A Hilbert space is simply a complete l vector space (finite- or infinite-dimensional) which has an inner product defined. This book is primarily concerned with the particular Hilbert space known as L2 function space. With the inner product defined as in (9.6) (integration taking place over some specified interval I C JR), this function space consists of all functions that are square-integrable:

Clearly, this space is closed under addition and scalar multiplication, so it is indeed a valid Hilbert space since it is also complete. 1 Completeness is a closure condition on the space, requiring that all Cauchy sequences converge to a limit that is also in the space.

Appendix

189

All the concepts discussed earlier in terms of usual k-tuple vector space extend to L 2 function space as well. The norm of a vector in L 2 space is defined to be

IIfl1 2 = (f, f) =

J

f2(X) dx.

We can also speak of subspaces in L 2 function space. For example, the span of a set of L 2 (JR) functions {f I, ... , f m} is a subspace of L 2 , defined to be 2

{f E L 2(IR) : f(x) =

m

L

aiJi(x), for some constants al,···, am}

(9.7)

i=1

Other concepts that extend immediately to L 2 function space are orthogonality, bases, orthonormal bases, projections, etc.

2To be precise, the representation (9.7) of a function I in terms of a linear combination of other functions needs hold only "almost everywhere" (a.e.), Le. III adi II = o.

L:

References

Abramovich, F., and Benjamini, Y: (995). Thresholding of wavelet coefficients as multiple hypotheses testing procedure. In Wavelets and Statistics. Antoniadis, A., and Oppenheim, G. (eds.). New York: SpringerVerlag. pp. 5-14. Akaike, H. (973). Information theory and an extension of the maximum likelihood principle. In Proceedings of the 2nd International SympOSium on Information Theory. Petrov, B. N., and Csaki, F. (eds.). Akademiai Kiado: Budapest. Altman, N. S. (990). Kernel smoothing of data with correlated errors. Journal of the American Statistical Association 85: 749-759. Anderson, T. W. (971). The Statistical Analysis of Time Series. Wiley: New York. Anderson, 1., Hall, N., ]awerth, B., and Peters, G. (993). Wavelets on closed subsets of the real line. In RecentAdvances in WaveletAnalysis. Schumaker, 1. 1., and Webb, G. (eds.). Academic Press: New York. Antoniadis, A., Gregoire, G., and McKeague, I. W. (994). Wavelet methods for curve estimation. Journal ofthe American Statistical Association

89: 1340-1353. Arino, M. A., and Vidakovic, B. (995). On wavelet scalograms and their applications in economic time series. Discussion Paper 95-21, ISDS, Duke University, Durham, North Carolina. Auscher, P. (989). Ondelettes fractales et applications. Ph.D. Thesis, Universite Paris, Dauphine, Paris. Bartlett, M. S. (963). Statistical estimation of density functions. Sankhya Series A 25: 245-254. Battle, G. (987). A block spin construction of ondelettes. part I: Lemarie functions. Communications in Mathematical Physics 100: 601-615.

192

REFERENCES

Benjamini, Y, and Hochberg, Y (1995). Controlling the false discovery rate: A practical and powerful approach to multiple testing. Journal of the Royal Statistical Society, Series B 57: 289-300. Bloomfield, P. (1976). Fourier Analysis of Time Series: An Introduction. Wiley: New York. Bock, M. E. (1992). Estimating functions with wavelets. Statistical Computing and Statistical Graphics Newsletter 4-8. Bock, M. E., and Pliego, G.]. (1992). Estimating functions with wavelets Part II: Using a Daubechies wavelet in nonparametric regression. Statistical Computing and Statistical Graphics Newsletter 27-34. Brigham, E. O. (1988). The Fast Fourier Transform and Its Applications. Prentice-Hall: Englewood Cliffs, New Jersey. Cencov, N. N. (1962). Evaluation of an unknown distribution density from observations. Soviet Mathematics 3: 1559-1562. Chambers,]. M., Cleveland, w: S., Kleiner, B., and Thkey, P. A. (1983). Graphical Methods for Data Analysis. Wadsworth: Belmont, California. Cheng, K. F., and Lin, P. E. (1981). Nonparametric estimation of a regression function. Zeitschrift fur Wahrscheinlichkeitstheorie und Verwandte Gebiete 57: 223-233. Chipman, H. A., Kolaczyk, E. D., and McCulloch, R E. (1995). Adaptive Bayesian wavelet shrinkage. Technical Report, University of Chicago, Chicago, Illinois. Chui, C. K. (1992). An Introduction to Wavelets. Academic Press: New York. Chui, C. K., and Wang,]. Z. (1991). A cardinal spline approach to wavelets. Proceedings of the American Mathematical Society 113: 785-793. Cohen, A., Daubechies, I., and Feauveau, ]. C. (1992). Biorthogonal bases of compactly supported wavelets. Communications in Pure and Applied Mathematics 45: 485-560. Cohen, A., Daubechies, I., and Vial, P. (1993). Wavelets on the interval and fast wavelet transforms. Applied and Computational Harmonic Analysis 1: 54-81. Cohen, A., Daubechies, I., Jawerth, B., and Vial, P. (1993). Multiresolution analysis, wavelets and fast algorithms on an interval. Comptes Rendus des Seances de l'Academie des Sciences, Serie 1316: 417-421. Coifman, R. R., and Donoho, D. 1. (1995). Translation-invariant de-noising. In Wavelets and Statistics. Antoniadis, A., and Oppenheim, G. (eds.). New York: Springer-Verlag. pp. 125-150. Coifman, R R, and Meyer, Y (1991). Remarques sur l'analyse de Fourier fenetre. Comptes Rendus des Seances de l'Academie des Sciences, Serie I 312: 259-261. Coifman, R. R., and Wickerhauser, M. w: (1992). Entropy-based algorithms for best basis selection. IEEE Transactions on Information Theory 38: 713-718. Coifman, R, Meyer, Y, and Wickerhauser, M. v: (1994).Wavelet analysis and

a

References

193

signal processing. In Wavelets and Their Applications, Ruskai, M. B., Beylkin, G., Coifman, R., Daubechies, I., Mallat, S., Meyer, Y, and Raphael, L. (eds.). Jones and Bartlett: Boston. Coifman, R. R., Meyer, Y, Quake, S., and Wickerhauser, M. W (1994). Signal processing and compression with wavelet packets. In Wavelets and Their Applications, Byrnes, J. S., Byrnes, J. L., Hargreaves, K. A., and Berry, K. (eds.). Kluwer Academic Publications: Dordrecht, The Netherlands. Collineau, S. (1994). Some remarks about the scalograms of wavelet transform coefficients. In Wavelets and Their Applications, Byrnes, J. S., Byrnes, J. L., Hargreaves, K. A., and Berry, K. (eds.). Kluwer Academic Publications: Dordrecht, The Netherlands. Cooley, J. W, and Thkey, J. W (1965). An algorithm for the machine calculation of complex Fourier seriew. Mathematics of Computation 19: 297-301. Craven, P., and Wahba, G. (1979). Smoothing noisy data with spline functions. Numerische Mathematik 31: 377-403. Csorgo, M., and Horvath, 1. (1988). Nonparametric methods for changepoint problems. In Handbook ofStatistics, Volume 7. Krishnaiah, P. R., and Rao, C. R. (eds.). Elsevier: Amsterdam. Daniel, C. (1959). Use of half-normal plots in interpreting factorial two-level experiments. Technometrics 1: 311-341. Daubechies, I. (1988). Orthonormal bases of compactly supported wavelets. Communications in Pure and Applied Mathematics 41: 909-996. Daubechies, I. (1992). Ten Lectures on Wavelets. SIAM: Philadelphia. Daubechies, I. (1993). Orthonormal bases of compactly supported wavelets II. Variations on a theme. SIAMJournal on Mathematical A nalysis 24: 499-519. Daubechies, I., and Lagarias, J. (1991). Two-scale difference equations I. Existence and global regularity of solutions. SIAMJournal on Mathematical Analysis 22: 1388-1410. Daubechies, I., and Lagarias, J. (1992). Two-scale difference equations II. L0cal regularity, infinite products of matrices and fractals. SIAMJournal on Mathematical Analysis 23: 1031-1079. Delacroix, M. (1983). Histogrammes et Estimation de la Densite Que saisje? # 2055. Presses Universitaires de France: Paris. de Boor, C. (1978). A Practical Guide to Splines. Applied Mathematical Sciences, Volume 27. Springer-Verlag: London. DeVore, R. A., and Lucier, B. J. (1992). Fast wavelet techniques for nearoptimal processing. In Proceedings of the IEEE Military Communications Conference 48.3.1-48.3.7. New York. Donoho, D. 1. (1993). Nonlinear wavelet methods for recovery of signals, densities, and spectra from indirect and noisy data. Proceedings of Symposia in Applied Mathematics 47: 173-205.

194

REFERENCES

Donoho, D. 1., and Johnstone, I. M. (1992). Nonlinear solution for linearinverse problems by wavelet-vaguelet decomposition. Technical Report 403. Stanford University Department of Statistics, Stanford, California. Donoho, D. L., and Johnstone, I. M. (1994). Ideal spatial adaptation via wavelet shrinkage. Biometrika 81: 425-455. Donoho, D. L., and Johnstone, I. M. (1995). Adapting to unknown smoothness via wavelet shrinkage. Journal of the American Statistical Association 90: 1200-1224. Donoho, D. 1., Johnstone, I. M., Kerkyacharian, G., and Picard, D. (1993). Density estimation by wavelet thresholding. Technical report, Stanford University Department of Statistics, Stanford, California. Donoho, D. L., Johnstone, I. M., Kerkyacharian, G., and Picard, D. (1995). Wavelet shrinkage: Asymptopia? Journal of the Royal Statistical Society, Series B 57: 301-369. Doukhan, P., and Leon, J. (1990). Deviation quadratique d'estimateur de densite par projection orthogonale. Comptes Rendus des Seances de l'Academie des Sciences, Serie I 310: 424-430. Dutilleux, P. (1989). An implementation of the "algorithme trous" to compute the wavelet transform. In Wavelets: Time-Frequency Methods and Phase Space. Combes, J. M, Grossman, A., and Tchamitchian, Ph. (eds.). Springer-Verlag: New York. Dym, H., and McKean, H. P. (1972). Fourier Sums and Integrals. Academic Press: New York. Engel, J. (1990). Density estimation with Haar series. Statistics and Probability Letters 9: 111-117. Eubank, R. L. (1988). Spline Smoothing and Nonparametric Regression. Marcel Dekker: New York. Fan, J., Hall, P., Martin, M., and PatH, P. (1996). On local smoothing of nonparametric curve estimators. Journal of the American Statistical Association 91: 258-266. Gabor, D. (1946). Theory of communications. Journal of the Institute of Electrical Engineering, London III 93: 429-457. Gao, H.-Y: (1993). Choice of threshold for wavelet estimation of the log spectrum. Technical Report 438. Stanford University Department of Statistics, Stanford, California. Gasser, Th., and Miiller, H. G. (1979). Kernel estimation of regression functions. In Smoothing Techniques for Curve Estimation. Gasser, Th. and Rosenblatt, M. (eds.). Heidelberg: Springer. Gasser, Th., Miiller, H. G., and Mammitzsch, v: (1985). Kernels for nonparametric curve estimation. Journal ofthe Royal Statistical Society B 47: 238-252. Good, I. J. (1958). The interaction algorithm and practical Fourier analysis. Journal of the Royal Statistical Society, Series B 20: 361-372.

a

References

195

Graps, A. (1995). An introduction to wavelets. IEEE Computational Science and Engineering 2. Haar, A. (1910). Zur Theorie der orthoganalen Funktionen-Systeme. Annals ofMathematics 69: 331-371. Hart, J. D. (1994). Automated kernel smoothing of dependent data by using time series cross-validation. Journal of the Royal Statistical Society, Series B 56: 529-542. Hu, Y-S. (1994). Wavelet approach to change-point detection with application to density estimation. Ph.D. thesis, Texas A&M University, College Station, Texas. Janssen, A. J. E. M. (1992). The Smith-Barnwell condition and non-negative scaling functions. IEEE Transactions in Information Theory 38: 884886. Jawerth, B., and Sweldens, W. (1994). An overview of wavelet based multiresolution analysis. SIAM Review 36: 377-412. Johnstone, I. M., Kerkyacharian, G., and Picard, D. (1992). Estimation d'une densite de probabilite par methode d'ondellettes. Comptes Rendus des Seances de l'Academie des Sciences, Serie 1315: 211-216. Johnstone, I. M., and Silverman, B. W. (1995). Wavelet threshold estimators for data with correlated noise. Technical report, Stanford University Department of Statistics, Stanford, California. Kaiser, G. (1994). A Friendly Guide to Wavelets. Birkhauser: Boston. Karlin, S., and Taylor, H. (1975). A First Course in Stochastic Processes, 2nd Edition. Academic Press: New York. Kerkyacharian, G., and Picard, D. (1992). Density estimation in Besov spaces. Statistics and Probability Letters 13: 14-24. Kerkyacharian, G., and Picard, D. (1993). Density estimation by kernel and wavelets methods: Optimality of Besov spaces. Statistics and Probability Letters 18: 327-336. Lemarie, P. G. (1988). Dne nouvelle base d'ondelettes de L2(IRn ). Journal de Mathematiques Pures et Appliquees 67: 227-236. Li, K. C. (1985). From Stein's unbiased risk estimates to the method of generalized cross-validation. Annals of Statistics 13: 1352-1377. Li, K. C. and Hwang, J. (1984). The data-smoothing aspect of Stein estimates. Annals of Statistics 12: 887-897. Lombard, E (1988). Detecting change points by Fourier analysis. Technometrics 30: 305-310. Mallat, S. G. (1989a). A theory for multiresolution signal decomposition: The wavelet representation. IEEE Transactions on Pattern Analysis and Machine Intelligence 11: 674-693. Mallat, S. G. (1989b). Multifrequency channel decomposition of images and wavelet models. IEEE Transactions on Acoustics, Speech, and Signal Processing 37: 2091-2110. Messiah, A. (1961). Quantum Mechanics. North-Holland: Amsterdam.

196

REFERENCES

Meyer, Y (1985). Principe d'incertitude, bases hilbertiennes et algebres d'operateurs, Seminaire Bourbaki, 1985-1986, No. 662. Meyer, Y (1990). Ondelettes et Operateurs l' Ondelettes. Hermann: Paris. Meyer, Y (1992). Ondelettes sur l'intervalle. Revista Matematica Iberoamericana 7: 115-133. Meyer, Y (1993). Wavelets: Algorithms and Applications. SIAM: Philadelphia. Moulin, P. (1993a). A wavelet regularization method for diffuse radar-target imaging and speckle-noise reduction. Journal ofMathematical Imaging and Vision, Special Issue on Wavelets 3: 123-134. Moulin, P. (1993b). Wavelet thresholding techniques for power spectrum estimation. IEEE Transactions on Signal Processing 42: 3126-3136. Miiller, H.-G., and Stadtmuller, U. (1987). Variable bandwidth kernel estimators of regression curves. Annals ofStatistics 15: 182-201. Nason, G. (1994). Wavelet regression by cross-validation. Technical Report 447, Department of Statistics, Stanford University, Stanford California. Nason, G. P. (1995). Choice of the threshold parameter in wavelet function estimation. In Wavelets and Statistics. Antoniadis, A., and Oppenheim, G. (eds.). New York: Springer-Verlag. pp. 261-280. Nason, G. (1996). Wavelet shrinkage using cross-validation. Journal of the Royal Statistical Society, Series B 58: 463-479. Ogden, R. T. (1994). Wavelet thresholding in nonparametric regression with change-point applications. Ph.D. thesis, TexasA&M University, College Station, Texas. Ogden, R. T (1997). On preconditioning for the discrete wavelet transform when the sample size is not a power of two. Communications in Statistics B: Simulation and Computation, to appear. Ogden, R. T, and Parzen, E. (1996a). Change-point approach to data analytic wavelet thresholding. Statistics and Computing 6: 93-99. Ogden, R. T., and Parzen, E. (1996b). Data dependent wavelet thresholding in nonparametric regression with change-point applications. Computational Statistics and Data Analysis 22: 53-70. Ogden, R. T, and Richwine,]. (1996). Wavelets in Bayesian change-point analysis. Technical report, University of South Carolina, Columbia, South Carolina. Page, E. S. (1954). Continuous inspection schemes. Biometrika 41: 100115. Page, E. S. (1955). A test for a change in a parameter occurring at an unknown point. Biometrika 42: 523-526. Parzen, E. (1962). On estimation of a probability density function. Annals of Mathematical Statistics 31: 1065-1076. Parzen, E. (1974). Some recent advances in time series modelling. IEEE Transactions on Automatic Control 19: 723-729. Prakasa Rao, B. L. S. (1983). Nonparametric Functional Estimation. Academic Press: New York.

References

197

Press, W. H., Teukolsky, S. A., Vetterling, W. T., and Flannery, B. P. (1992). Numerical Recipes in C, the Art of Scientific Computing, 2nd edition. Cambridge University Press: Cambridge. Priestley, M. B. (1981). Spectral Analysis and Time Series. Academic Press: New York. Richwine, J. (1996). Bayesian estimation of change-points using Haar wavelets. Master's thesis, University of South Carolina Department of Statistics, Columbia, South Carolina. Rioul, 0., and Vetterli, M. (1991). Wavelets and signal processing. IEEE Signal Processing Magazine 14-38. Ross, S. (1983). Stochastic Processes. Wiley: New York. Rudemo, H. (1982). Empirical choice of histograms and kernel density estimators. ScandinavianJournal ofStatistics 9: 65-78. Schumaker, L. 1. (1981). Spline Functions: Basic Theory. Wiley-Interscience: New York. Shensa, M. J. (1992). The discrete wavelet transform: Wedding the trous and Mallat algorithms. IEEE Transactions on Signal Processing 40: 24642482. Silverman, B. W. (1986). Density Estimation for Statistics and Data Analysis. Chapman and Hall: London. Stein, C. (1981). Estimation of the mean of a multivariate normal distribution. Annals of Statistics 10: 1135-1151. Stone, M. (1978). Cross-validation: A review. Statistics 9: 127-140. Strang, G., and Nguyen, T. (1996). Wavelets and Filter Banks. WellesleyCambridge Press: Wellesley, MA. Stromberg, J. O. (1982). A modified Franklin system and higher order spline systems on lR n as unconditional bases for Hardy spaces. In Conference in Honor ofA. Zygmund, Vol. II. Beckner, A. et al. (eds.). Wadsworth Mathematics Series, pp. 475-493. Taniguchi, M. (1979). On estimation of parameters of Gaussian stationary processes. Journal ofApplied Probability 16: 575-591. Taniguchi, M. (1980). On estimation of the integrals of certain functions of spectral density. Journal ofApplied Probability 17: 73-83. Tchamitchian, Ph. (1987). Biorthogonalite et theorie des operateurs. Revista Matemdtica Iberoamericana 3: 163-189. Unser, M. (1996). A practical gUide to the implementation of the wavelet transform. In Wavelets in Medicine and Biology. Aldroubi, A., and Unser, M. (eds.). CRe Press: Boca Raton, Florida. Vidakovic, B. (1994). Nonlinear wavelet shrinkage with Bayes rules and Bayes factors. Discussion Paper 94-A-24, ISDS, Duke University, Durham, North Carolina. Vidakovic, B., and Miiller, P. (1994). Wavelets for kids: A tutorial introduction. Discussion Paper 94-A-13, ISDS, Duke University, Durham, North Carolina.

a

198

REFERENCES

Wahba, G. (1980). Automatic smoothing of the log periodogram. Journal of the American Statistical Association 75: 122-132. Walter, G. G. (1992). Approximation of the delta function by wavelets. Journal ofApproximation Theory 71: 329-343. Walter, G. G. (1994). Wavelets and Other Orthogonal Systems With Applications CRC Press: Boca Raton, Florida. Wang, Y (1995). Jump and sharp cusp detection by wavelets. Biometrika 82: 385-397. Wang, Y (1996). Function estimation via wavelet shrinkage for long-memory data. Annals ofStatistics, to appear. Weaver, J. B., Yansun, X., Healy, D. M., Jr., and Cromwell, L. D. (1991). Filtering noise from images with wavelet transforms. Magnetic Resonance in Medicine 24: 288-295. Wei, W. W. S. (1990). Time Series Analysis: Univariate and Multivariate Methods. Addison-Wesley: Redwood City, California. Wertz, W. (1978). Statistical Density Estimation: A Survey. Vandenhoeck and Ruprecht: GOttingen. Weyrich, N., and Warhola, G. T. (1994). De-noising using wavelets and crossvalidation. Technical Report AFIT/EN!fR/94-01 , Department of Mathematics and Statistics, Air Force Institute ofTechnology, Wright-Patterson Air Force Base, Ohio. Wickerhauser, M. v: (1994). Adapted Wavelet Analysis: From Theory to Software. AI( Peters: Boston.

Glossary ofNotation

lR the set of real numbers (-

00, 00 ) .

7L the set of integers: 7L = { ... , -1,0, 1, ...}.

L 2 (I) the set of square-integrable functions on the interval I: {f :

II f2 (x) dx <

oo}.

(f, g) the L 2 inner product: (f, g) Ilfll the L 2 norm: IIfl1 2 = (f, f).

=I

f(x)g(x) dx.

S the closure of the set S.

f 1.g the functions f and g are orthogonal, i.e., (f, g) = 0. V 1. W the subspaces V and W are orthogonal, i.e. for every f E V and g E W, f1.g.

EB

the sum of orthogonal subspaces.

£2(7L) the set of square-summable sequences: {ak : L:z a~ < oo}. flA the restriction of the function f to the set A. supp f

the support of the function

f.

[x] the greatest integer function. O(g(n)) A sequence an = O(g(n)) for a function g(n) if there exists some M > 0 such that lanl/g(n) < M for all n = 1,2, ....

f

alternatively (depending on context) the continuous Fourier transform of f or an estimate of f.

lid independent and identically distributed. [a,b) the half-open interval {x: a <x < b} (similarly for (a,b), (a,b], [a,b]).

a the complex conjugate of a: for a = b + ci, a = b - ci. <5 (x)

the Dirac delta function .

.l!t convergence in probability. X n .l!tJ1 if for each E > 0, P[lXn asn ~ 00.

-

J11

> E]

~

°

Glossary of Terms This glossary is included here for ready reference while reading through this book. Listings here should not, in general, be taken to be strict definitions but as basic descriptions of concepts.

approximation space any of the Vj spaces. basis A collection of functions {II, ... , 1m} forms a basis for a space V if the Ii'S span V and they are linearly independent. cascade algorithm see decomposition algorithm. coefficient A function 9 E V can be written as a linear combination of functions in a basis {iI, ... , 1m} for V: 9 = L: aili; the constants aI, ... ,am are the coefficients of 9 with respect to the basis {I I, ... , 1m}. If the basis is an orthonormal basis, then the coefficients are computed byai = (g, Ii), i = 1, ... , m. Each coefficient gives some information about the nature of the function g, e.g., a Fourier coefficient specifies the amount of the frequency content in 9 at the specified frequency. complete orthonormal system (CONS) A sequence of functions {/il is a complete orthonormal system if the Ii'S are pairwise orthogonal and the only function orthogonal to each Ii is the zero function. decomposition algorithm fast algorithm for computing lower-level scaling function and wavelet coefficients given scaling function coefficients at a higher level (see Section 4.1). detail function (or detail signal) a function in the space W j . detail space any of the W j spaces. dilation The dilation of a function I(x) is given by I(ax) for a > O. If a > 1, the function is stretched out over the real line; if 0 < a < 1, the function is compacted. dilation equation see two-scale relationship. Dirac delta function the function <5 (x) which is defined to be infinite for x = 0 and zero for all other x's with the property that f <5(x) dx = 1. The Dirac delta function is the function for which (I, <5) = f I (x)<5 (x) dx I (0) for any function I. even function a function I for which I (x) = I (- x) for all x. father wavelet see scaling function.

=

202

GLOSSARY OF TERMS

Fourier coefficient see coefficient. Fourier transform The continuous Fourier transform of a function L 2 (JR) is given by

J(w) =

I:

f

E

f(x)e-iWXdx.

The discrete Fourier transform of a function f E L 2 (JR) refers to the set of Fourier coefficients {ao, aI, b1 , a2, b2, ...} from the representation 00

f(x)

= ~ao + L(aj cos(jx) + bj sin(jx)). j=l

function space a set of functions that is complete and closed under addition and scalar multiplication. Haar wavelet the mother wavelet defined by I,

'ljJ(x) =

°<x < 1

-1,1<x<1 otherwise.

{ 0,

inner product The L 2 inner product of two functions f and 9 is (f, g) J f(x)g(x) dx. inverse Fourier transform A function f E L 2 (JR) can be recovered from its Fourier transform f by means of the inverse Fourier transform ~

fix)

= 2"

I:

iwx

J(w) e

to.

level The wavelet level j refers to wavelets, scaling functions, and their coefficients with first subSCript (dilation parameter) j. mother wavelet see wavelet. modulus The modulus of a complex-valued number a = b + ci is J a x a = Jb 2 + c2 • multiresolution analysis (MRA) see Definition 1.4. norm The L 2 norm ofa function f is given by 11111 = .)(f, f). odd function a function f for which f (x) = - f (- x) for all x. orthogonal Two functions f and 9 are orthogonal if (f, g) = 0. orthogonal basis a basis whose elements are orthogonal. orthonormal basis a basis whose elements are orthogonal and Ilfill 1, i = 1, ... , m.

Glossary 0/ Terms

203

projection Let V be a subspace of L 2 (JR) and let W denote its orthogonal complement in L 2 (JR). Any function f E L 2 (JR) can be uniquely decomposed as f = 9 + h, with 9 E V and hEW. The function 9 is known as the projection of f on V. pyramid algorithm see decomposition algorithm. reconstruction algorithm algorithm for computing higher-level scaling func tion coefficients given lower-level wavelet coefficients (see Section 4.1). refinement equation see two-scale relationship. scaling function a function whose translates { (. - k), k E Z} form an orthogonal basis for the space Vo in the usual multiresolution context. The term scaling function is often used generically to refer to any dilated and translated version j,k = 2j / 2 (2 j . -k) of the function (¢ is known as the/ather wavelet). scaling function coefficient see coefficient. span A set offunctions {f I, ... , f m} are said to span a vector space V if each function in V can be written as a linear combination of f I , ... , f m' subspace A subspace of L 2 (JR), for instance, is a complete set of functions, each in L 2 (JR), that is closed under addition and scalar multiplication. support The support of a function f is the smallest closed set A for which f(x) is identically zero for all x ¢ A. translation The translation of a function f (x) is given by f (x - a) for a E JR. If a > 0, the function is moved to the right; if a < 0, it is moved to the left. two-scale relationship equation relating a scaling function to its dilated versions: (x)

= Vi L

hk(2x - k).

kEZ

The sequence {h k } is known as the two-scale sequence. vector space a set ofvectors that is complete and closed under addition and scalar multiplication. wavelet a function 'ljJ whose translates {'ljJ(. - k), k E Z} form an orthonormal basis for the space W o, where VI = Vo EB W o in the usual multiresolution context. The term wavelet is often used generically to refer to any dilated and translated version 'ljJj,k = 2j /2'ljJ(2 j . - k) of the mother wavelet 'ljJ. wavelet coefficient see coefficient.

Index a trous

algorithm 117 Akaike Information Criterion (AIC) 146 approximation 9, 10, 11, 13, 14,89 approximation spaces 15, 18,84, 115,201 dual 84 two-dimensional 172 autocorrelation function 134 autocovariance function 134

cumulative distribution function (edt) 29 cumulative sum (CUSUM) process 141, 153 cusps 140-142

B-splines 24, 79 bandwidth 33,35,36,40,44, 47, 144 basis 3, 186, 201 orthogonal 6, 187 orthonormal 187 Battle-Lemarie wavelet family 23-24, 81-82 Bayes rule 162 best basis 174, 177-180 binwidth 31-32 blocky function 97-99, 149 Bonferroni correction 151 boundary handling periodic 111-112, 119 symmetric 112-113 boxplot 101-102 Brownian bridge 154

Daubechies wavelet family 25-27, 82--83 decomposition algorithm 20,51,53, 59-66, 108, 170, 178,201 two-dimensional 170 density estimation 29-38, 119, 143 histograms 31-32 kernel 32-35 naive 33,34 orthogonal series 35-38 "raw" 36, 37, 50 wavelet 49-54, 132-133 detail function 11, 13, 14,90, 201 detail image 169 detail signal 23, 90, 168 detail spaces 17, 18,84,86, 114, 169, 175,201 dilation 8, 174, 201 equation 60 index 8 Dirac delta function 36-37, 163, 201 Doppler function 95 down-sampling 63, 66, 96, 179

cascade algorithm 63 change-point problem 140-142 Chui-Wang wavelet family 24-25 coiflets 83 complete orthonormal system (CONS) 7,9,15,42,60,62,110,201 convolution 40 discrete 67 coefficient 201 correlogram 136 covariance function 134 cross-validation 156-161

edge detection 141 empirical Bayes 163 empirical distribution function 32, 37 even function 5, 45, 201 fast Fourier transform 105-107, 109, 116 father wavelet (see scaling function) 15 ftlters 66-69, 82, 109, 170, 178 high pass 68 low pass 68, 109 quadrature mirror 68

INDEX Fourier coefficients 4-5, 69, 70, 104-105 Fourier series representation 3, 4, 35, 70,134 Fourier transform continuous 69-72, 202 discrete 1-7,202 of data 104-107, 134 windowed 72-74 frames 86 function space 188, 202 Gabor transform 72-74,92-93 Gibbs phenomenon 183 gray scale 22, 171

205

library of basis functions 174, 177 loss 42 mean square error (MSE) 41-42, 129, 148 median absolute deviation (MAD) 131-132 Meyer boundary wavelets 113-114 Meyer wavelet basis 23, 83 modulation parameter 174 multiple comparisons 151 multiresolution analysis (MRA) 14-16, 22-23,60,168,202 multiresolution approximation plot 89-91 multiresolution decomposition plot 90-92

Haar function 7, 11, 14 scaling function 49, 59 system 7-23, 175-176 transform 110-111 wavelet 9, 17, 59, 78, 184, 202 Heisenberg Uncertainty Principle 74 Hermite polynomials 42 Hilbert spaces 188 histograms 31-32 wavelet (Haar) based 49-52

natural frequencies 104-105 noise level, estimation of 131-132 nonparametric regression 3s-44, 110, 119, 143-165 Fourier series 43 kernel 39-42, 45-47 orthogonal series 42-44,45-47 "raw" 39,43 wavelet 54-58 norm 5,202

image analysis 22-23, 141, 171 indicator function 15 inner product 5, 187,202 integrated mean absolute error (IMAE) 52 integrated mean squared error (IMSE) 51

odd function 5,202 Old Faithful data 32, 36, 52, 54 orthogonal 6, 202 orthogonality of scaling function and wavelet 60-62 orthonormality 6, 174 oscillation parameter 174

jumps, detecting 140-142

Parseval identity 71-72, 76, 138 wavelet version 78, 144, 157, 181 parsimonious representation 22, 23 periodogram 137, 138-139 probability density function (pdf) (see density) 30 projection 14-15, 188, 202 onto approximation space 14-15, 16,53,55,89,172 pruning 179 pyramid algorithm 63

kernel function 33, 34, 39 biweight 34 Dirichlet 46 Epanechnikov 34, 40 Gaussian 34 higher-order 34 triangular 34 wavelet-based 56 L2 function space 2, 188 Legendre polynomials 7,42 "Lena" 171-173 level 202

Q-Q plot 100-101 quality control 141 quantiles 100

206

Index

reconstruction algorithm 22, 63-66, 170,202 coefficients 16, 19 two-dimensional 170 refinement equation 60 reflection boundary handling 45, 112-113 regression function 38 estimation (see nonparametric regression) Riesz basis 86,87 risk 42, 144, 157 sample size 143 not a power of two 115-117 selective wavelet reconstruction 120-121 semiorthogonal wavelets 24 scaling function 15, 16, 174, 202 coefficients 62,65, 108, 170 scalogram 93-96 spatial adaptivity 126-128 span 16, 186 sparsity of wavelet representation 101, 120, 132, 148 spectral density 119, 134-135, 138 estimation 133-140 sample 136-137 spectrogram 92-93 Spin Cycle 184 splitting algorithm 179 subspace 186, 202 support 202 symmlets 83 tensor product 168 thresholding 124-126, 133, 143-165, 144 Bayesian methods 161-165 cross-validation 156-161 global 128-131, 147, 155 hard 125-126 hypothesis testing 149-156 false discovery rates 154-156

recursive 151-154 minimax 100, 129-130 soft 125-126, 143 SURE 144-149, 151, 184, hybrid 148-149 universal (VisuShrink) 130-131, 156, 159, 160, 184 time-frequency localization 69-79 time-frequency plane 175 time-scale plots 92-95 time series 119, 134-140 translation 8, 174, 202 index 8 translation invariance 180-184 two dimensional wavelets 167-174 two-scale sequence 60,65, 174 two-scale relation 59, 60-62, 87, 169, 174, 202 vector space 185, 202 wavelet 16,18,23,60,75,202 biorthogonal 79, 83-87, 117 coefficients 21,62,65,95-102, 108, 112-113 empirical 121-122, 123-124, 132, 143, 150, 151, 161, 163 plotting 95-102 mother 8,85, 174 on an interval 110-115 orthogonal 25-26, 81-83 representation 12, 16-22 semiorthogonal 79, 87-88 wavelet packets 173-180 wavelet transform continuous 74-79 of data 107-110,117 matrix representation 123 orthogonality 116 window 72-73 lag 138 spectral 137 "zoom-in, zoom-out" 23