# Dimension Reduction for Curves: Simplified and Generalized

arXiv: https://arxiv.org/abs/2607.03112 · HTML: https://mlsanity.com/paper/2607.03112/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 35 references that are in the map.
- First posted on arXiv 3 Jul 2026.

## Builds on (most cited first, 14 of 14)

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering](https://mlsanity.com/paper/1807.04518/) (2018)
- [Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension](https://mlsanity.com/paper/1809.02961/) (2018)
- [Optimal Sketching Bounds for Sparse Linear Regression](https://mlsanity.com/paper/2304.02261/) (2023)
- [Random Projections and Sampling Algorithms for Clustering of High-Dimensional Polygonal Curves](https://mlsanity.com/paper/1907.06969/) (2019)
- [(k, l)-Medians Clustering of Trajectories Using Continuous Dynamic Time Warping](https://mlsanity.com/paper/2012.00464/) (2020)
- [Computing Continuous Dynamic Time Warping of Time Series in Polynomial Time](https://mlsanity.com/paper/2203.04531/) (2022)
- [On Generalization Bounds for Projective Clustering](https://mlsanity.com/paper/2310.09127/) (2023)
- [No Dimensional Sampling Coresets for Classification](https://mlsanity.com/paper/2402.05280/) (2024)
- [A Tight VC-Dimension Analysis of Clustering Coresets with Applications](https://mlsanity.com/paper/2501.06588/) (2025)
- [Random projections for curves in high dimensions](https://mlsanity.com/paper/2207.07442/) (2022)
- [Improved Learning via k-DTW: A Novel Dissimilarity Measure for Curves](https://mlsanity.com/paper/2505.23431/) (2025)
- [Hardness of High-Dimensional Linear Classification](https://mlsanity.com/paper/2603.19061/) (2026)
- [Optimal Dimension-Free Sampling for Regularized Classification](https://mlsanity.com/paper/2605.23726/) (2026)

## 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.