Lines-preserving terminal embeddings enable dimension-free coresets for time-series clustering

The authors develop a generalization of terminal embeddings to affine line-segments to address the limitation that standard terminal embeddings cannot preserve linear structures required for clustering time-series data under common straight-line interpolation. They utilize these lines-preserving embeddings to obtain the first dimension-free coresets for clustering time-series under the Fréchet distance, leveraging Johnson-Lindenstrauss (JL) embeddings as the underlying dimension reduction technique.

• The method generalizes terminal embeddings to affine line-segments, overcoming the inability of standard techniques to preserve linear structures.
• It enables the construction of the first dimension-free coresets for clustering time-series under the Fréchet distance.
• Experiments on synthetic and real-world time-series show performance similar to JL embeddings and favorable results against PCA.
• Unlike other methods, only terminal embeddings extend pairwise distance preservation to the full ambient space.

This approach allows for effective dimension reduction in complex time-series clustering tasks where preserving linear interpolation between measurements is critical.