Skip to content Skip to navigation

OpenStax_CNX

You are here: Home » Content » Solving the Wavelet Dilation Equation

Navigation

Recently Viewed

This feature requires Javascript to be enabled.
 

Solving the Wavelet Dilation Equation

Module by: Ivan Selesnick. E-mail the author

Suppose hn=0 h n 0 for n<0 n 0 and n>N1 n N 1 . Then the support of φt φ t is 0 N1 0 N 1 as we saw before . How can we find φt φ t from hn h n ? φt=2n=0N1hnφ2tn φ t 2 n 0 N 1 h n φ 2 t n It turns out that we can find samples of φt φ t using the following procedure.

For example, if hn h n is of length N=4 N 4 , then from the dilation equation we have φ0=2(h0φ0+h1φ-1+h2φ-2+h3φ-3) φ 0 2 h 0 φ 0 h 1 φ -1 h 2 φ -2 h 3 φ -3 φ1=2(h0φ2+h1φ1+h2φ0+h3φ-1) φ 1 2 h 0 φ 2 h 1 φ 1 h 2 φ 0 h 3 φ -1 φ2=2(h0φ4+h1φ3+h2φ2+h3φ1) φ 2 2 h 0 φ 4 h 1 φ 3 h 2 φ 2 h 3 φ 1 φ3=2(h0φ6+h1φ5+h2φ4+h3φ3) φ 3 2 h 0 φ 6 h 1 φ 5 h 2 φ 4 h 3 φ 3 As we know that φt φ t is supported on 0 N1 0 N 1 ( 0 3 0 3 for this example), we can see that φ-1 φ -1 , φ4 φ 4 , etc fall outside the support. Therefore these equations can be simplified. φ0=2h0φ0 φ 0 2 h 0 φ 0 φ1=2(h0φ2+h1φ1+h2φ0) φ 1 2 h 0 φ 2 h 1 φ 1 h 2 φ 0 φ2=2(h1φ3+h2φ2+h3φ1) φ 2 2 h 1 φ 3 h 2 φ 2 h 3 φ 1 φ3=2h3φ3 φ 3 2 h 3 φ 3 or in matrix form, φ0φ1φ2φ3=2( h0000 h2h1h00 0h3h2h1 000h3 )φ0φ1φ2φ3 φ 0 φ 1 φ 2 φ 3 2 h 0 0 0 0 h 2 h 1 h 0 0 0 h 3 h 2 h 1 0 0 0 h 3 φ 0 φ 1 φ 2 φ 3 Remember that φt φ t is zero outside the range 0 3 0 3 .

This matrix equation reveals that the vector of values of φt φ t on the integers 0N1 0 N 1 is an eigenvector of the matrix P=2( h0000 h2h1h00 0h3h2h1 000h3 ) P 2 h 0 0 0 0 h 2 h 1 h 0 0 0 h 3 h 2 h 1 0 0 0 h 3 Specifically, it is an eigenvector corresponding to the eigenvalue 11. However, not just any set of coefficients will give a matrix PP with 11 as an eigenvalue.

It turns out that PP will always have 11 as an eigenvalue whenever the coefficients hn h n satisfy the condition

nh2n=nh2n1=12 n h 2 n n h 2 n 1 1 2
(1)
In other words, whenever the even terms sum up to 12 1 2 , and likewise for the odd terms, we are sure that PP has 11 as an eigenvalue. This can be shown as follows. Note that if nh2n=nh2n1=12 n h 2 n n h 2 n 1 1 2 then 11112( h0000 h2h1h00 0h3h2h1 000h3 )=1111 1 1 1 1 2 h 0 0 0 0 h 2 h 1 h 0 0 0 h 3 h 2 h 1 0 0 0 h 3 1 1 1 1 That is because the columns of PP consist of the even and odd terms of hn h n . Therefore, the vector of ones is an eigenvector of PT P with eigenvalue 11. Because the transpose PT P has the same eigenvalues as PP, λP=λPT λ P λ P , the matrix PP also has 11 as an eigenvalue.

note:

Even though PP and PT P have the same eigenvalues, they do not have the same eigenvectors.

As a result, if the condition is satisfied, we can calculate the integer samples of φt φ t by calculating the eigenvector of PP corresponding to the eigenvalue 11.

We can also write the equation as follows: 2( h0000 h2h1h00 0h3h2h1 000h3 )φ0φ1φ2φ3φ0φ1φ2φ3=0000 2 h 0 0 0 0 h 2 h 1 h 0 0 0 h 3 h 2 h 1 0 0 0 h 3 φ 0 φ 1 φ 2 φ 3 φ 0 φ 1 φ 2 φ 3 0 0 0 0 or (2( h0000 h2h1h00 0h3h2h1 000h3 )( 1000 0100 0010 0001 ))φ0φ1φ2φ3=0000 2 h 0 0 0 0 h 2 h 1 h 0 0 0 h 3 h 2 h 1 0 0 0 h 3 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 φ 0 φ 1 φ 2 φ 3 0 0 0 0 (PI)φ=0 P I φ 0

note:

If vv is an eigenvector of PP, then so is αv α v .
The solution is only unique up to a scaling. Likewise, the dilation equation itself does not impose a normalization on φt φ t .

Recall from the sum-integral equality that φtdt=kφk t φ t k φ k . Therefore, if we want the normalization φtdt=A t φ t A , say, we can get it by the normalization kφk=A k φ k A Therefore, we can add this equation to the matrix equation we already have.

( PI ( 1111 ) )φ=0A P I 1 1 1 1 φ 0 A
(2)
Now we have one more equation than unknowns, however, the new equation is consistent with the existing equations. It only normalizes the solution. Solving this linear system of equations gives the integer samples of φt φ t .

Notice that the matrix PP is a convolution matrix, but with every other row removed. It can be constructed by using the convmtx command and then removing every other row:


      H = convmtx(h(:),N);
      P = sqrt(2)*H(1:2:2*N-1,:);
    

Refinement

We can get more samples of φt φ t by using the dilation equation. φt=2khkφ2tk φ t 2 k h k φ 2 t k To find the value of φt φ t on half integers n2 n 2 , for nZ n , let t=n2 t n 2 in the dilation equation.

φn2=2khkφnk=2hn*φn φ n 2 2 k h k φ n k 2 h n φ n
(3)
According to the dilation equation, the value of φt φ t on the half-integers can be obtained by convolving the scaling filter hn h n with the integer-samples of φt φ t , as illustrated in Figure 1.

Figure 1
Figure 1 (fig1_sec7-1.png)

Similarly, we can get samples of φt φ t on the quarter-integers by setting t=n4 t n 4 in the dilation equation.

φn4=2khkφn2k=2khkgn2k=2[↑2]hn*gn=2[↑2]hn*φn2 φ n 4 2 k h k φ n 2 k 2 k h k g n 2 k 2 [↑2] h n g n 2 [↑2] h n φ n 2
(4)
where gnφn2 g n φ n 2 . The notation [↑2]xn [↑2] x n represents an upsampled version of xn x n . Recalling that the transfer function of [↑2]hn [↑2] h n is Hz2 H z 2 we get the following diagram (Figure 2).

Figure 2
Figure 2 (fig2_sec7-1.png)

The value of φt φ t for t=n8 t n 8 is found as

φn8=2khkφn4k=2khkgn4k=2[↑4]hn*gn=2[↑4]hn*φn4 φ n 8 2 k h k φ n 4 k 2 k h k g n 4 k 2 [↑4] h n g n 2 [↑4] h n φ n 4
(5)
where gnφn4 g n φ n 4 , with corresponding diagram (Figure 3),

Figure 3
Figure 3 (fig3_sec7-1.png)

Similarly, φn16=2[↑8]hn*φn8 φ n 16 2 [↑8] h n φ n 8 Given the value of φt φ t on the integers, a simple method emerges for finding φt φ t on the dyadic rationals. In general, we have Equation 6 and Figure 4.

φn2j+1=2 [ 2 j ] hn*φn2j φ n 2 j 1 2 [ 2 j ] h n φ n 2 j
(6)

Figure 4
Figure 4 (fig4_sec7-1.png)

Let hh be a vector of the scaling filter coefficients. Let pp be a vector of samples of φt φ t on the integers. Then the samples of φt φ t on the dyadic rationals are obtained by the following simple loop.


	for k = 1:5
	   p = sqrt(2) * conv(h,p);
	   h = up(h,2);
	end
      

We also have the diagram in Figure 5,

Figure 5
Figure 5 (fig5_sec7-1.png)

Using the Z-transform, we can write

𝒵φn2j=2j2HzHz2Hzj1𝒵φn 𝒵 φ n 2 j 2 j 2 H z H z 2 H z j 1 𝒵 φ n
(7)

H(z) has a zero at z=-1

Note that hn h n satisfies the sum rule

nh2n=nh2n1 n h 2 n n h 2 n 1
(8)
if and only if Hz H z has z-1+1 z 1 as a factor, Hz=Qz(z-1+1) H z Q z z 1 To see this, note that if Hz=Qz(z-1+1) H z Q z z 1 , then H1=0 H 1 0 . Writing this out, we get
Hz=nhnzn H z n h n z n
(9)
H-1=nhn1n H -1 n h n 1 n
(10)
H-1=nh2nnh2n1 H -1 n h 2 n n h 2 n 1
(11)
So the condition in Equation 8 can be written as H-1=0 H -1 0 , or equivalently as Hz=Qz(z-1+1) H z Q z z 1 .

To summarize, the sum rule (Equation 8) can be written in various forms. nh2n=nh2n1n1nhn=0 n h 2 n n h 2 n 1 n 1 n h n 0 H-1=0 H -1 0 Hz=Qz(z-1+1) H z Q z z 1 (z-1+1)  divides  Hz z 1   divides   H z If we note the following, nh2n=nh2n1=12(nhn=2)(n1nhn=0) n h 2 n n h 2 n 1 1 2 n h n 2 n 1 n h n 0 then we can state the previous result in the following form. (nhn=2)(n1nhn=0)1  is an eigenvalue of  P n h n 2 n 1 n h n 0 1   is an eigenvalue of   P Or in terms of Hz H z : (H1=2)(H-1=0)1  is an eigenvalue of  P H 1 2 H -1 0 1   is an eigenvalue of   P

Content actions

Download module as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Add module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks