Dimension Reduction for Curves: Simplified and Generalized
For researchers working with high-dimensional curve data, this work provides a unified theoretical guarantee for dimension reduction across multiple distance measures, simplifying previous proofs and extending applicability.
The paper simplifies the proof of an existing bound on the target dimension for random projections that preserve the Fréchet distance of polygonal curves, and generalizes the result to a broad class of dissimilarity measures including Fréchet, q-DTW, and Hausdorff distances, as well as to piecewise linear surfaces.
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.