matrix multiplication result value range

Question

Here is the initial question: About the output value range of LeGall 5/3 wavelet

Today I found actually the transform can be seen as a matrix multiplication. It is easy to calculate the wavelet coefficients as a matrix (in order to estimate the value, all the Rounded down action is ignored which will not affect the estimation of the max value).

The 1st level of DWT2 has two steps which is to perform the LeGall 5/3 filter on two directions. If we see the I as the input 8*8 matrix and A as the wavelet coefficients matrix.

1. For the horizontal direction: output1 = I.A

2. Then the vertical direction is calculated: In fact, it can be represented as output2 = output1'.A (use the transpose of output1 to multiply A again) which will get the transpose of the result we want.

3. Transpose the output2. output_lvl1 = output2' = (output1'.A)' = ((I.A)'.A)' = (A'.I'.A)'=A'.I.A (I put details here to make it clear without the math symbol...)

And the 2nd level of the wavelet is only performed at the LL area which is the output_lvl1(1:4,1:4). And basically the process is the same (let the coefficients matrix represented as B).

Here is the coefficients of the matrix A and B based on my calculation (hope it is correct...)

A = [0.75  -0.125 0      0      -0.5  0    0    0;
        0.5     0.25   0      0      1    0    0    0;
        -0.25 0.75  -0.125  0      -0.5 -0.5 0    0;
        0     0.25   0.25   0      0    1    0    0;
        0     -0.125 0.75   -0.125 0    -0.5 -0.5 0
        0     0      0.25   0.25   0    0    1    0;
        0     0      -0.125 0.625  0    0    -0.5  -1;
        0     0      0      0.25   0    0    0    1];

B = [0.75  -0.125 -0.5 0;
     0.5   0.25   1    0;
     -0.25 0.75   -0.5 -1;
     0     0.125  0    1];

And now the question became: 1. if we know A and the range of Input(matrix I) which is -128 to +127, what is the value range of output_lvl1 = A'.I.A?

2. if we use the output_lvl1(1:4,1:4) as input I2, what is value range of B'.I2.B?

I really need some math help here. Thank you in advance.

Answer 1

Well finally I found a way to solve this. SymPy lib is what I really need.

As the max value could only be possible in results of B'.I2.B. So a program will do this.

from sympy import *
def calcu_max(strin):
    x=0
    strin1 = str(strin).replace('*',' ').replace('+',' ').replace('-',' ')
    strin1 = strin1.split(' ')
    for ele in strin1:
        if '[' in ele or ']' in ele or ele =='':
            continue
        x = x + float(ele)
    return x

DWT1 = Matrix(8, 8, [0.75, -0.125, 0, 0,-0.5, 0, 0, 0, 0.5, 0.25, 0, 0, 1, 0, 0, 0, -0.25, 0.75, -0.125, 0, -0.5, -0.5, 0, 0, 0, 0.25, 0.25, 0, 0, 1, 0, 0, 0,-0.125, 0.75, -0.125, 0, -0.5, -0.5, 0, 0, 0, 0.25, 0.25, 0, 0, 1, 0, 0, 0, -0.125, 0.625, 0, 0, -0.5, -1, 0, 0, 0, 0.25, 0, 0, 0, 1])

Input1 = MatrixSymbol('A',8,8)
DWT1_t = Transpose(DWT1)

output_lvl1_1d = DWT1_t*Input1
output_lvl1_2d = output_lvl1_1d* DWT1

#print 'output_lvl1_2d[0,0]: ' 
#print simplify(output_lvl1_2d[0,0])

#bulit 2nd lvl input from the lvl1 output (1:4,1:4)

input_lvl2 = output_lvl1_2d[0:4,0:4]

DWT2 = Matrix(4, 4, [0.75, -0.125, -0.5, 0, 0.5, 0.25, 1, 0, -0.25, 0.75, -0.5, -1, 0, 0.125, 0, 1])

DWT2_t = Transpose(DWT2)

output_lvl2_1d = DWT2_t*input_lvl2
output_lvl2_2d = output_lvl2_1d * DWT2


#Lvl 2 calculate max
max_lvl2 = zeros(4,4)
for i in range(4):
    for j in range(4):
        max_lvl2[i,j]=128.0*calcu_max(simplify(output_lvl2_2d[i,j]))
        print str(i)+' '+str(j)+' '+str(max_lvl2[i,j])
        #print max_lvl2[i,j]
print max_lvl2

Well, here is the result (putting all possible max values in one matrix, and min values are correspondingly negative):

[338.000000000000, 266.500000000000, 468.000000000000, 468.000000000000], 
[266.500000000000, 210.125000000000, 369.000000000000, 369.000000000000], 
[468.000000000000, 369.000000000000, 648.000000000000, 648.000000000000], 
[468.000000000000, 369.000000000000, 648.000000000000, 648.000000000000]

Then 648 is what I am looking for.