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.
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