Dimensionality Reduction on Complex Vector Spaces for Euclidean Distance with Dynamic Weights
This addresses a limitation in dimensionality reduction methods for applications where weights change dynamically, offering a theoretical solution with potential impact in data analysis and machine learning.
The paper tackles the problem of dimensionality reduction for weighted Euclidean distances when weights are unknown or dynamic, by introducing a linear mapping to a complex vector space that provides a Johnson-Lindenstrauss-like estimate once weights are revealed.
The weighted Euclidean norm $\|x\|_w$ of a vector $x\in \mathbb{R}^d$ with weights $w\in \mathbb{R}^d$ is the Euclidean norm where the contribution of each dimension is scaled by a given weight. Approaches to dimensionality reduction that satisfy the Johnson-Lindenstrauss (JL) lemma can be easily adapted to the weighted Euclidean distance if weights are known and fixed: it suffices to scale each dimension of the input vectors according to the weights, and then apply any standard approach. However, this is not the case when weights are unknown during the dimensionality reduction or might dynamically change. In this paper, we address this issue by providing a linear function that maps vectors into a smaller complex vector space and allows to retrieve a JL-like estimate for the weighted Euclidean distance once weights are revealed. Our results are based on the decomposition of the complex dimensionality reduction into several Rademacher chaos random variables, which are studied using novel concentration inequalities for sums of independent Rademacher chaoses.