Wavelets

Introduction

Modern computers are constantly sending images and videos that need to be compressed in order to be put into a smaller package for high speed transmission.  When the receiver receives the package, the image must be decompressed.  Ideally, we would want a system that compresses and decompresses without losing any data.  This is usually impossible.  Instead, computers strive to accomplish compression and decompression with a minimal loss of data. 

For example, if the data is a picture, we want the transformed picture to look about the same as the original.  Digital pictures are just a sequence of numbers so we are interested in taking a large sequence of numbers, compressing the large sequence into a smaller sequence of numbers and then decompressing into a new large sequence of numbers that is approximately the same as the original list.  The new sequence that approximates the original sequence is called a wavelet.


Averaging

Giving two numbers, if we want to compress the numbers into one number, the most logical number to send is the average of the two numbers.  We can think of this process as starting with the vector

        v  =  [a,b]T

and sending it to the vector

       w  =  Av

where A is the matrix

        [0.5,0.5]

This transformation has the advantage of sending information that is half the size that contains information from both numbers.  Of course we can never get back to the original two numbers from just the average.

This method works for larger data sets.  For example if

        v  =  [a,b,c,d]T

we take the average of a and b and the average of c and d.  If we think of this as compressing an image, we are merging adjacent pixels together.  The matrix A that takes pairwise averages is given by

       


Average-Difference Representation

For most pictures, there are areas where the color does not change much at all.  When this is the case, we compute the average and the distance from the average.  If the distance from the average is close to zero, we round to zero and omit the distance.  For most pictures, this allows us to compress a picture to a file that is much smaller in size than sending information about every pixel. 

For a sequence of two numbers, v  =  [a,b], we take the average and the distance from the first entry to the average.  The matrix that corresponds to this transformation is

       

For example if

        v  =  [3,7]

then

        AvT  =  [5,-2]T

Notice that 5 is the average of 3 and 7 and -2 is the first (3) minus the average (5).  Also notice that A has the inverse

       

This allows us to get the original data back from the the transformed data.  Notice that

        A-1 [5,-2]T  =  [3,7]T

For a sequence of four numbers [a,b,c,d], we use a two step process to make a transformation.  For the first step,  the first outcome is the average of a and b, the second is the average of c and d, the third is the distance from a to the average of a and b, and the fourth is the distance from c to the average of c and d.  The matrix for this transformation is

       

The second step is to transform these intermediate numbers so that the first number is the average of the first two (the final average), the second is the distance from the intermediate first number to the total average, and the last two numbers remain the same.  The matrix that accomplishes this is

       

Composing these two transformation is the same as multiplying these matrices.  If we start with a 4 x 1 vector v, then we obtain the new vector using

        u  =  A1 A2 v

 

Example

Suppose that we want to transform the vector v  =  [2,6,9,3].  We have

        A1vT  =  [4,6,-2,3]T

and

        (A2 A1)vT  =  A2(A1v)T  =  A2[4,6,-2,3]T  =  [5,-1,-2,-3]T


Threshold Values

We are now ready to demonstrate a general way of compressing and decompressing data.  We will show by example how to accomplish this for a vector of length eight. 

We denote the following:

       

Then the 8 x 8 matrix that computes pairwise averages and then distances is given by

 

       

We let the second matrix be the matrix that computes the averages of the first four and last four respectively and then distances from the first average to the combined averages of the first two averages and from the third average to the final two averages.  Finally it leaves the final four entries the same.  The matrix that accomplishes this is 

       

The third step is to let the first entry be the final average and the second entry be the distance between the average of the first four and the final average.  The matrix should leave the final six entries the same.  This matrix is 

       

To transform a vector v we take the product of the three matrices.

        wT  =  A3A2A1vT 

Before we send the information wT we compress the data.  The first entry is the final average and we do not touch this number.  The last seven numbers are the detail coefficients.  One way of compressing the data is to consider all small detail coefficient zero.  Think of this as saying that if nearby data points are close to their averages, then replace the data with the average.  The threshold number e is the value such that if a detail coefficient is below this value (in absolute value) then it is replaced by zero. 

To get back to close to the original vector we take the inverse.  We use the fact that

       (A3A2A1) -1  =  A1-1A2-1A3-1

Thus

        vT  @  A1-1A2-1A3-1wT  

 

Example

Consider the vector

        v  =  [23, 54, 55, 70, 89, 91, 93, 100]

Use the threshold number 5 to compress the data.  Then decompress the data.

 

Solution

We find that

        A3A2A1vT  =  [71.875, -21.375, -12,-3.25, -15.5, -7.5, -1, -3.5]

Next replace the values that are below 5 with a zero to get the compressed data

        w  =  [71.875, -21.375, -12,0,3.25, -15.5, -7.5, 0, 0]

Notice that this contains only 5 nonzero numbers, which is smaller than the original 8.  Now decompress to get

        A1-1A2-1A3-1wT  =  [23, 54, 55, 70, 93.25, 93.25, 93.25, 93.25]

Although the numbers are not exactly the same as the original, they are close.



Back to the Matrices and Applications Home Page

Back to the Linear Algebra Home Page

Back to the Math Department Home Page

e-mail Questions and Suggestions