Machine_Learning_Research/Johnsson Lindenstrauss Transform at master · Pidem/Machine_Learning_Research · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
import numpy as np
dataset=np.random.rand(20,100)
eps=0.4
d=int(np.round(24*np.log(100)/((3*eps**2-2*eps**3)*np.log(2))))

mapping_matrix=np.random.rand(d,20)

def mapping(n):
    return (1/np.sqrt(d))*np.dot(mapping_matrix,np.transpose(dataset[:,n]))

a=np.random.randint(0,99)
b=np.random.randint(0,99)
while a==b:
    b=np.random.randint(0,99)

distance_before_mapping = np.linalg.norm(dataset[:,a]-dataset[:,b])
distance_after_mapping = np.linalg.norm(mapping(a)-mapping(b))
#eps = 0.4 and d=453
print("the euclidian distance BEFORE mapping is {}".format(distance_before_mapping))
print("the euclidian distance AFTER mapping is {}".format(distance_after_mapping))


eps=0.3
d=int(np.round(24*np.log(100)/((3*eps**2-2*eps**3)*np.log(2))))
# d = 738
mapping_matrix=np.random.rand(d,20)

distance_before_mapping = np.linalg.norm(dataset[:,a]-dataset[:,b])
distance_after_mapping = np.linalg.norm(mapping(a)-mapping(b))

print("the euclidian distance AFTER mapping is {}".format(distance_before_mapping))
print("the euclidian distance AFTER mapping is {}".format(distance_after_mapping))

eps=0.1
d=int(np.round(24*np.log(100)/((3*eps**2-2*eps**3)*np.log(2))))
#d = 5695
mapping_matrix=np.random.rand(d,20)

distance_before_mapping = np.linalg.norm(dataset[:,a]-dataset[:,b])
distance_after_mapping = np.linalg.norm(mapping(a)-mapping(b))

print("the euclidian distance BEFORE mapping is {}".format(distance_before_mapping))
print("the euclidian distance AFTER mapping is {}".format(distance_after_mapping))


## Dimensionality reduction

D1=np.diag(np.random.choice([-1,1],32))
gaussianvector=np.random.rand(d+32,1)
toeplitz_matrix=toeplitz(gaussianvector[:d],gaussianvector[d:])

a=np.random.randint(0,99)
b=np.random.randint(0,99)
while a==b:
    b=np.random.randint(0,99)

def structured_mapping(n):
    zer=np.zeros((1,12))

    vector=list(dataset[:,n])

    for i in range(12):
        vector.append(0)


    x11=np.dot(hadamard(32),vector)
    x12=np.dot(D1,x11)
    x13=np.dot(toeplitz_matrix,x12)

    return (1/np.sqrt(d))*x13

eps=0.4
d=int(np.round(24*np.log(100)/((3*eps**2-2*eps**3)*np.log(2))))

D1=np.diag(np.random.choice([-1,1],32))
gaussianvector=np.random.rand(d+32,1)
toeplitz_matrix=toeplitz(gaussianvector[:d],gaussianvector[d:])

distance_before_mapping = np.linalg.norm(dataset[:,a]-dataset[:,b])
distance_after_mapping = np.linalg.norm(structured_mapping(a)-structured_mapping(b))
#eps = 0.4 and d=453
print("the euclidian distance BEFORE mapping is {}".format(distance_before_mapping))

eps=0.3
d=int(np.round(24*np.log(100)/((3*eps**2-2*eps**3)*np.log(2))))
# d = 738

D1=np.diag(np.random.choice([-1,1],32))
gaussianvector=np.random.rand(d+32,1)
toeplitz_matrix=toeplitz(gaussianvector[:d],gaussianvector[d:])


distance_before_mapping = np.linalg.norm(dataset[:,a]-dataset[:,b])
distance_after_mapping = np.linalg.norm(mapping(a)-mapping(b))

print("the euclidian distance AFTER mapping is {}".format(distance_before_mapping))
print("the euclidian distance AFTER mapping is {}".format(distance_after_mapping))

eps=0.1
d=int(np.round(24*np.log(100)/((3*eps**2-2*eps**3)*np.log(2))))
# d = 738

D1=np.diag(np.random.choice([-1,1],32))
gaussianvector=np.random.rand(d+32,1)
toeplitz_matrix=toeplitz(gaussianvector[:d],gaussianvector[d:])


distance_before_mapping = np.linalg.norm(dataset[:,a]-dataset[:,b])
distance_after_mapping = np.linalg.norm(mapping(a)-mapping(b))

print("the euclidian distance AFTER mapping is {}".format(distance_before_mapping))
print("the euclidian distance AFTER mapping is {}".format(distance_after_mapping))
print("the euclidian distance AFTER mapping is {}".format(distance_after_mapping))