System and method adapted to facilitate dimensional transform
View Patent ↗Systems and methods that facilitate dimensional transformations of data points are disclosed. In particular, the subject invention provides for a system and methodology that simplifies dimensional transformations while mitigating variations of a distance property between pairs of points. A set of n data points in d dimensional space is represented as an n×d input matrix, where d also corresponds to the number of attributes per data point. A transformed matrix represents the n data points in a lower dimensionality k after being mapped. The transformed matrix is an n×k matrix, where k is the number of attributes per data point and is less than d. The transformed matrix is obtained by multiplying the input matrix by a suitable projection matrix. The projection matrix is generated by randomly populating the entries of the matrix with binary or ternary values according to a probability distribution. Unlike previous methods, the projection matrix is formed without obtaining an independent sample from a Gaussian distribution for each entry in the projection matrix, without applying a linear algebraic technique to generate the projection matrix and without employing arbitrary floating point numbers. Processes and/or algorithms can utilize the reduced transformed matrix instead of the larger input matrix to facilitate computational efficiency and data compression.
1. A computer hardware system that dimensionally transforms a pointset, comprising the following computer executable components:
a receive matrix component that receives the pointset; and,
a transformation component that reduces the dimensionality of the pointset via employment of a projection matrix having randomly selected entries from a set comprising +1, 0, and −1, while maintaining a pairwise distance property of the pointset.
2. The system of claim 1 , the pointset including n points in d dimensional Euclidean space that may be represented as an n×d input matrix with respective points represented as a row (vector) having d attributes (coordinates), the points being transformed into k dimensional space so as to be representable as a n×k transformed matrix with each point represented as a row (vector) having k attributes (coordinates).
3. The system of claim 2 , the projection matrix having randomly selected entries of +1 with probability of 1/2 and −1 with probability of 1/2.
4. The system of claim 2 , the projection matrix having randomly selected entries of +1 with probability of 1/6, 0 with probability of 2/3 and −1 with probability of 1/6.
5. The system of claim 2 , a range of the pairwise distance property being maintained within an acceptable predetermined percentage.
6. The system of claim 2 , the k selected to maintain the pairwise distance property.
7. The system of claim 2 , the k being logarithmic in n and independent of d.
8. The system of claim 2 , the transformed pointset utilized by an algorithm to compute a distance between a first point and a second point, the first point and the second point belonging to the pointset.
9. The system of claim 1 , the transformation component embedding the pointset in different dimensionalities according to the following:
P is an arbitrary set of n points in d dimensional Euclidian space ( d ) represented as a n×d matrix A, given ε,β>0, where ε controls accuracy of the embeddings in terms of distance preservation and β controls probability of success
k
0
=
4
+
2
β
ɛ
2
/
2
-
ɛ
3
/
3
log
n
where, for k≧k 0 , R is a d×k projection matrix with R(i,j)=r ij , where {r ij } includes independent random variables from either one of probability distributions
r
ij
=
{
+
1
-
1
with
probability
1
/
2
1
/
2
r
ij
=
3
×
{
+
1
1
/
6
0
with
probability
2
/
3
-
1
1
/
6
where
T
=
1
k
AR
and
embedding from d dimensionality to k dimensionality (ƒ: d → k ) maps an i th row of A to an i th row of T
with probability at least 1−n −β , for all u,v ε P
(
1
-
ɛ
)
u
-
v
2
≤
f
(
u
)
-
f
(
v
)
2
≤
(
1
+
ɛ
)
u
-
v
2
.
10. A computer readable medium having computer usable components for a transformation component comprising:
a receive matrix component that receives a high dimensional point set; and,
a transformation component that reduces dimensionality of the pointset via employment of a projection matrix having entries of at least one of +1, 0, −1, while maintaining integrity of a pairwise distance property.
11. A system that dimensionally transforms a pointset, comprising:
a projection matrix generator that receives an input matrix and generates a projection matrix based thereon, the projection matrix having entries of a set of possible values of at least one of +1, 0 and −1; and
a transformation engine that reduces dimensionality of the pointset via employment of the projection matrix while maintaining a pairwise distance property.
12. The system of claim 11 , the set of possible values comprising +1, 0 and −1.
13. The system of claim 11 , the set of possible values comprising +1 and −1.
14. The system of claim 11 , further comprising a receive matrix component that receives a high dimensional pointset and converts the high dimensional pointset into the input matrix.
15. The system of claim 11 further comprising:
a random generator that randomly provides entries for the projection matrix to the projection matrix generator as entries for the projection matrix according to a probability distribution; and
a probability distribution that provides the probability distribution to the random generator.
16. The system of claim 15 , the probability distribution providing equal probabilities of 1/2 to entries of +1 and −1.
17. The system of claim 15 , the probability distribution providing probabilities of 1/6, 2/3, and 1/6 to entries of +1, 0 and −1, respectively.
18. The system of claim 11 , the transformation engine outputting the reduced dimensionality pointset and the preserved pairwise distance property to a requesting algorithm.
19. The system of claim 18 , the requesting algorithm being at least one of an ε-approximate nearest neighbor problem, where given an arbitrary point x, for every point
z
∈
P
,
x
-
z
≥
(
1
-
ɛ
)
x
-
y
,
a point y ε P is found, an approximation algorithm for a version of clustering where the sum of the squares of intra cluster distances is sought to be minimized, and data-stream computations, where a limited memory exists and only single pass over the data (stream) is facilitated.
20. A data compression method for transforming n points in d dimensionality, represented as an n×d input matrix, to k dimensionality thereby producing a n×k transformed matrix while mitigating variations in a distance property between pairs of the points, comprising the following computer executable acts:
multiplying the n×d input matrix by a d×k projection matrix having entries populated from a set of {+1, 0, −1};
for respective entries in the transformed matrix, discarding calculations wherein multiplication would be by 0;
for respective entries in the transformed matrix, producing a first sum wherein multiplication would be by +1;
for respective entries in the transformed matrix, producing a second sum wherein multiplication would be by −1; and
subtracting respective first and second sums to obtain each entry in the transformed matrix.
21. The method of claim 20 , the entries within the projection matrix being randomly populated with values of +1 and −1 according to equal probabilities of 1/2.
22. The method of claim 20 , the entries within the projection matrix being randomly populated with values of +1, 0 and −1 according to respective probabilities of 1/6, 2/3, and 1/6.
23. A computer executable hardware system for transforming n points in d dimensionality, represented as an n×d input matrix, to k dimensionality thereby producing a n×k transformed matrix while mitigating variations in a distance property between pairs of the points, comprising:
computer implemented means for multiplying the n×d input matrix by a d×k projection matrix having entries populated with at least one of +1, 0, or −1;
computer implemented means for discarding calculations wherein multiplication would be by 0 for each entry in the transformed matrix;
computer implemented means for producing a first sum wherein multiplication would be by +1 for each entry in the transformed matrix;
computer implemented means for producing a second sum wherein multiplication would be by −1 for each entry in the transformed matrix; and
computer implemented means for subtracting respective first and second sums to obtain each entry in the transformed matrix.