标题： Johnson-Lindenstrauss 引理超越欧几里得几何 显示英文标题

标题： Johnson-Lindenstrauss Lemma Beyond Euclidean Geometry

摘要： 约翰逊-林登施特劳斯（JL）引理是欧几里得空间中降维的基石，但其在非欧几里得数据中的适用性一直有限。 本文将JL引理扩展到欧几里得几何之外，以处理现实应用中常见的通用相异矩阵。 我们提出了两种互补的方法：首先，我们表明JL变换可以应用于具有签名的伪欧几里得空间中的向量$(p,q)$，提供了理论保证，这些保证取决于两个向量的$(p, q)$范数与欧几里得范数的比率，用于衡量偏离欧几里得几何的程度。 其次，我们证明任何对称空心相异矩阵都可以表示为广义幂距离矩阵，其中包含一个额外参数，用于表示数据中的不确定性水平。 在这种表示中，应用JL变换会产生乘法近似，并且具有与偏离欧几里得几何程度成比例的受控加性误差项。 我们的理论结果基于输入数据偏离欧几里得几何的程度，提供细粒度的性能分析，使更广泛的数据类别的维度降低变得实际且有意义。 我们在合成和真实世界数据集上验证了我们的方法，证明了将JL引理扩展到非欧几里得设置的有效性。 显示英文摘要

摘要： The Johnson-Lindenstrauss (JL) lemma is a cornerstone of dimensionality reduction in Euclidean space, but its applicability to non-Euclidean data has remained limited. This paper extends the JL lemma beyond Euclidean geometry to handle general dissimilarity matrices that are prevalent in real-world applications. We present two complementary approaches: First, we show the JL transform can be applied to vectors in pseudo-Euclidean space with signature $(p,q)$, providing theoretical guarantees that depend on the ratio of the $(p, q)$ norm and Euclidean norm of two vectors, measuring the deviation from Euclidean geometry. Second, we prove that any symmetric hollow dissimilarity matrix can be represented as a matrix of generalized power distances, with an additional parameter representing the uncertainty level within the data. In this representation, applying the JL transform yields multiplicative approximation with a controlled additive error term proportional to the deviation from Euclidean geometry. Our theoretical results provide fine-grained performance analysis based on the degree to which the input data deviates from Euclidean geometry, making practical and meaningful reduction in dimensionality accessible to a wider class of data. We validate our approaches on both synthetic and real-world datasets, demonstrating the effectiveness of extending the JL lemma to non-Euclidean settings.