Dimension Reduction for Curves: Simplified and Generalized
Not on the map. Why?
Abstract (arXiv)
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-2log(nm)) bound on the target dimension of a random projection that preserves the continuous Fr'echet distance of polygonal curves up to a factor (1±varepsilon). Our proof is based on the concept of sparse oblivious subspace embeddings. While previous techniques were limited to the case of the Fr'echet 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'echet, 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.
Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 14 of its 35 references that are in the map. First posted on arXiv 3 Jul 2026.
Builds on
14 of 35 references.
References · 14
- 2014Sketching as a Tool for Numerical Linear Algebracited by 285
- 2018Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clusteringcited by 94
- 2018Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimensioncited by 27
- 2023Optimal Sketching Bounds for Sparse Linear Regressioncited by 6
- 2019Random Projections and Sampling Algorithms for Clustering of High-Dimensional Polygonal Curvescited by 5
- 2020(k, l)-Medians Clustering of Trajectories Using Continuous Dynamic Time Warpingcited by 5
- 2022Computing Continuous Dynamic Time Warping of Time Series in Polynomial Timecited by 4
- 2023On Generalization Bounds for Projective Clusteringcited by 4
- 2024No Dimensional Sampling Coresets for Classificationcited by 4
- 2025A Tight VC-Dimension Analysis of Clustering Coresets with Applicationscited by 4
- 2022Random projections for curves in high dimensionscited by 2
- 2025Improved Learning via k-DTW: A Novel Dissimilarity Measure for Curvescited by 2
2 more
- 2026Hardness of High-Dimensional Linear Classificationcited by 1
- 2026Optimal Dimension-Free Sampling for Regularized Classificationcited by 1
Built on by
Not cited yet.