用简化方法实现曲线降维，保持距离不变性。
Dimension Reduction for Curves: Simplified and Generalized
- 基于稀疏无偏子空间嵌入，简化了降维证明。
- 在 $O(1^{-2}\log(nm))$ 维下保持距离误差小于 $\pm\varepsilon$。
- 适用于多种曲线距离度量，如 Fréchet、DTW、Hausdorff 等。
我们重新研究高维多边形曲线的随机投影降维方法。借鉴随机线性代数工具，给出了已知 $O(\varepsilon^{-2}\log(nm))$ 目标维度界的一个显著简化的证明，该界保证随机投影能以 $(1\pm\varepsilon)$ 因子保留连续 Fréchet 距离。我们的证明基于稀疏无偏子空间嵌入概念。尽管此前方法仅限于 Fréchet 距离，但本方法具有广泛适用性，可扩展至所有涉及点对间欧氏距离最大值、求和或积分的度量。我们定义了一种广义曲线相异度量，包含 Fréchet、$q$-DTW、Hausdorff 等作为特例，并证明同一降维技术在此度量下同样有效。最后，我们将该框架拓展至分段线性曲面，通过适当扩展距离度量实现降维。
原文摘要 · Abstract (English)
We revisit random projections for reducing the dimension of high-dimensional polygonal curves. Drawing from the toolbox of randomized linear algebra, we give a considerably simplified proof of the known $O(\varepsilon^{-2}\log(nm))$ bound on the target dimension of a random projection that preserves the continuous Fréchet distance of polygonal curves up to a factor $(1\pm\varepsilon)$. Our proof is based on the concept of sparse oblivious subspace embeddings. While previous techniques were limited to the case of the Fréchet distance, our techniques are fairly general and extend to all possible distance measures that involve the maximum, a sum or an integral over Euclidean distances between pairs of points on both input curves. We define a generalized dissimilarity measure for curves that includes several popular measures such as Fréchet, $q$-DTW, Hausdorff, etc. as special cases and show that the same dimension reduction technique works for this generalized dissimilarity measure. Finally, we apply the same framework for dimension reduction to piecewise linear surfaces, after extending the distance measure suitably to such surfaces.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。