Random projections for curves in high dimensions

DOI10.1007/S00454-024-00710-5MaRDI QIDQ6926518zbMATH OpenFDO

Authors Ioannis Psarros

Publication date 24 September 2025

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S00454-024-00710-5

zbMATH Keywords

dimension reductionFréchet distanceJohnson-Lindenstrauss lemmapolygonal curvestime series

Mathematics Subject Classification ID

Time series, auto-correlation, regression, etc. in statistics (GARCH) (62M10) Metric embeddings as related to computational problems and algorithms (68R12) Computational aspects of data analysis and big data (68T09) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites work

• An elementary proof of a theorem of Johnson and Lindenstrauss
• Approximate nearest neighbor for curves -- simple, efficient, and deterministic
• Approximating \((k,\ell)\)-center clustering for curves
• Approximating dynamic time warping and edit distance for a pair of point sequences
• Approximating the Fréchet distance for realistic curves in near linear time
• Clustering of time series data -- a survey
• Clustering time series under the Fréchet distance
• COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES
• Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
• Dimensionality reductions in \(\ell_{2}\) that preserve volumes and distance to affine spaces
• Embeddings of surfaces, curves, and moving points in Euclidean space
• Extensions of Lipschitz mappings into a Hilbert space
• scientific article; zbMATH DE number 4074316 (Why is no real title available?)
• scientific article; zbMATH DE number 2019638 (Why is no real title available?)
• scientific article; zbMATH DE number 1775450 (Why is no real title available?)
• scientific article; zbMATH DE number 7788498 (Why is no real title available?)
• Jaywalking your dog: computing the Fréchet distance with shortcuts
• Latent semantic indexing: A probabilistic analysis
• On the complexity of range searching among curves
• On the Hardness of Computing an Average Curve.
• Optimal terminal dimensionality reduction in Euclidean space
• Optimality of the Johnson-Lindenstrauss lemma
• Performance of Johnson-Lindenstrauss transform for \(k\)-means and \(k\)-medians clustering
• Probabilistic embeddings of the Fréchet distance
• Problems and results in extremal combinatorics. I.
• Random projections of smooth manifolds
• Sketching as a tool for numerical linear algebra
• Solving Fréchet distance problems by algebraic geometric methods
• Sparser Johnson-Lindenstrauss transforms
• The fast Johnson-Lindenstrauss transform and approximate nearest neighbors
• The geometry of graphs and some of its algorithmic applications
• The Johnson-Lindenstrauss lemma and the sphericity of some graphs
• The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction
• The persistent homology of distance functions under random projection
• The VC dimension of metric balls under Fréchet and Hausdorff distances
• Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails

This page was built for publication: Random projections for curves in high dimensions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6926518)