Dimension Reduction for Curves: Simplified and Generalized
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Latent Space Representation of Electricity Market Curves for Improved Prediction Efficiency
This work presents a three-phase ML prediction framework designed to handle a high dimensionality and multivariate time series character of the electricity market curves. In the preprocessing phase, we transform the orig…
Dimensionality ReductionSpherical Principal Curves
This paper presents a new approach for dimension reduction of data observed in a sphere. Several dimension reduction techniques have recently developed for the analysis of non-Euclidean data. As a pioneer work, Hauberg (…
Dimensionality ReductionUsing Space-Filling Curves and Fractals to Reveal Spatial and Temporal Patterns in Neuroimaging Data
We present a novel method, Fractal Space-Curve Analysis (FSCA), which combines Space-Filling Curve (SFC) mapping for dimensionality reduction with fractal Detrended Fluctuation Analysis (DFA). The method is suitable for …
Computational EfficiencyDimensionality ReductionGaussian ProcessesSequential Learning of Principal Curves: Summarizing Data Streams on the Fly
When confronted with massive data streams, summarizing data with dimension reduction methods such as PCA raises theoretical and algorithmic pitfalls. Principal curves act as a nonlinear generalization of PCA and the pres…
Dimensionality ReductionShape Analysis of Euclidean Curves under Frenet-Serret Framework
Geometric frameworks for analyzing curves are common in applications as they focus on invariant features and provide visually satisfying solutions to standard problems such as computing invariant distances, averaging…