论文标题
具有动态重量的欧几里得距离的复杂矢量空间上的尺寸降低
Dimensionality Reduction on Complex Vector Spaces for Euclidean Distance with Dynamic Weights
论文作者
论文摘要
\ in \ in \ Mathbb {r}^d $带权重s $ x \ in \ in \ mathbb {r}^d $的加权欧几里得norm $ \ | x \ | | | _w $ in \ mathbb {r}^d $ in \ mathbb {r}^d $是欧几里得范围，其中每个尺寸的贡献按给定的重量缩放。如果已知并固定权重，则可以轻松地适应满足Johnson-Lindenstrauss（JL）引理的降低性降低方法：足以根据权重缩放输入向量的每个维度，然后采用任何标准方法。但是，当权重降低期间未知或可能动态变化时，情况并非如此。在本文中，我们通过提供线性函数来解决此问题，该函数将向量映射到一个较小的复杂矢量空间中，并允许在揭示了加权后的加权欧几里得距离的类似JL样估计值。我们的结果基于将复数维度还原为几个Rademacher混乱随机变量的分解，这些变量是使用新型浓度不等式进行研究的，以实现独立的Rademacher Chaoses。
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.
