Working with Dimensionality Reduction part2(Machine Learning)

Abstract: The weighted Euclidean distance between two vectors is a Euclidean distance where the contribution of each dimension is scaled by a given non-negative weight. The Johnson-Lindenstrauss (JL) lemma can be easily adapted to the weighted Euclidean distance if weights are known at construction time. Given a set of n vectors with dimension d, it suffices to scale each dimension of the input vectors according to the weights, and then apply any standard JL reduction: the weighted Euclidean distance between pairs of vectors is preserved within a multiplicative factor ε with high probability. However, this is not the case when weights are provided after the dimensionality reduction. In this paper, we show that by applying a linear map from real vectors to a complex vector space, it is possible to update the compressed vectors so that the weighted Euclidean distances between pairs of points can be computed within a multiplicative factor ε, even when weights are provided after the dimensionality reduction.