Friday 26 June 2015

set union and intersection in the MatSumSig model

A version of set union and intersection in the MatSumSig model.

First, note that union corresponds to max(a,b), and intersection to min(a,b).
Then note these identities:
abs(x) = pos(x) + pos(-x)
abs(a - b) = pos(a - b) + pos(-a + b)
a + b + abs(a - b) = 2*max(a,b)
a + b - abs(a - b) = 2*min(a,b)
So, for example:
[ r1 ]   [ 1  1  1 ] [ pos[x1] ] [  1  1 ] [ a ]
[ r2 ] = [ 1 -1 -1 ] [ pos[x2] ] [  1 -1 ] [ b ]
                     [ pos[x3] ] [ -1  1 ]
expands to:
r1 = a + b + pos(a - b) + pos(-a + b) = 2*max(a,b)
r2 = a + b - pos(a - b) - pos(-a + b) = 2*min(a,b)
These are our two functions we want to reproduce:
set-union(f,g):
  [max(f[k],g[k]) for k in range(len(f))]

set-intersection(f,g):
  [min(f[k],g[k]) for k in range(len(f))]
And here they are in MatSumSig (ignoring a factor of 2):
[ U1 ]   [ 1  1  1  0  0  0  0  0  0  0  0  0 ] [ pos[x1]  ] [  1  1  0  0  0  0  0  0 ] [ f1 ]
[ I1 ] = [ 1 -1 -1  0  0  0  0  0  0  0  0  0 ] [ pos[x2]  ] [  1 -1  0  0  0  0  0  0 ] [ g1 ]
[ U2 ]   [ 0  0  0  1  1  1  0  0  0  0  0  0 ] [ pos[x3]  ] [ -1  1  0  0  0  0  0  0 ] [ f2 ]
[ I2 ]   [ 0  0  0  1 -1 -1  0  0  0  0  0  0 ] [ pos[x4]  ] [  0  0  1  1  0  0  0  0 ] [ g2 ]
[ U3 ]   [ 0  0  0  0  0  0  1  1  1  0  0  0 ] [ pos[x5]  ] [  0  0  1 -1  0  0  0  0 ] [ f3 ]
[ I3 ]   [ 0  0  0  0  0  0  1 -1 -1  0  0  0 ] [ pos[x6]  ] [  0  0 -1  1  0  0  0  0 ] [ g3 ]
[ U4 ]   [ 0  0  0  0  0  0  0  0  0  1  1  1 ] [ pos[x7]  ] [  0  0  0  0  1  1  0  0 ] [ f4 ]
[ I4 ]   [ 0  0  0  0  0  0  0  0  0  1 -1 -1 ] [ pos[x8]  ] [  0  0  0  0  1 -1  0  0 ] [ g4 ]
                                                [ pos[x9]  ] [  0  0  0  0 -1  1  0  0 ]
                                                [ pos[x10] ] [  0  0  0  0  0  0  1  1 ]
                                                [ pos[x11] ] [  0  0  0  0  0  0  1 -1 ]
                                                [ pos[x12] ] [  0  0  0  0  0  0 -1  1 ]
which expands to:
[U1,U2,U3,U4] = 2* [max(f1,g1), max(f2,g2), max(f3,g3), max(f4,g4)]
[I1,I2,I3,I4] = 2* [min(f1,g1), min(f2,g2), min(f3,g3), min(f4,g4)]
So I guess you could say they are space based union and intersection. We can also do a time based one:

[ U[t] ] = [ 1  1  1 ] [ pos[x1] ] [  1  1 ] [ f ]
[ I[t] ]   [ 1 -1 -1 ] [ pos[x2] ] [  1 -1 ] [ g ]
                       [ pos[x3] ] [ -1  1 ]
where U[t] is union of f[t] and g[t] with respect to time, and I[t] is intersection.

No comments:

Post a Comment