Dimension Reduction for Curves: Simplified and Generalized

• URL: http://arxiv.org/abs/2607.03112v1
• Date: Fri, 03 Jul 2026 08:48:35 GMT
• Title: Dimension Reduction for Curves: Simplified and Generalized
• Abstract summary: We revisit random projections for reducing the dimension of high-dimensional polygonal curves.<n>We give a simplified proof of the known $O(varepsilon-2log(nm))$ bound on the target dimension of a random projection.<n>Our proof is based on the concept of sparse oblivious subspace embeddings.
• Score: 56.23281156053955
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Intrinsic Wasserstein Rates for Score-Based Generative Models on Smooth Manifolds [61.14405512940818]
  We show that Score-based generative models are trained in high-dimensional ambient spaces.<n>We use a ReLU implementation of nearest-projection coordinates via finite intrinsic anchors and Gauss Newton.
  arXiv  Detail & Related papers  (2026-05-15T10:20:05Z)
• Denoising distances beyond the volumetric barrier [13.045166411221539]
  ORDER achieves pointwise distance estimation of order $n-ari(d+5)$ up to polylogthmic factors in $n$ in time.<n>We prove that the Gromov-Wasserstein distance between the reconstructed metric measure space and the true latent manifold is of order $n-1/d$.<n>Our results are proven in a very general setting which includes general models of noisy pairwise distances, random geometric graphs, and unknown connection probability functions.
  arXiv  Detail & Related papers  (2026-04-01T03:20:16Z)
• Non-Euclidean Broximal Point Method: A Blueprint for Geometry-Aware Optimization [55.002497070656624]
  Broximal Point Method (BPM) offers an idealized optimization framework based on iteratively minimizing the objective function over norm balls centered at the current iterate.<n>It enjoys striking global convergence guarantees, converging linearly and in a finite number of steps for proper, closed and convex functions.<n>In this note, we ask whether the convergence theory of BPM can be extended to this more general, non-Euclidean setting.
  arXiv  Detail & Related papers  (2025-10-01T12:32:52Z)
• Sharp detection of low-dimensional structure in probability measures via dimensional logarithmic Sobolev inequalities [0.5592394503914488]
  We introduce a method for identifying and approximating a target measure $pi$ as a perturbation of a given reference measure $mu$. Our main contribution unveils a connection between the emphdimensional logarithmic Sobolev inequality (LSI) and approximations with this ansatz.
  arXiv  Detail & Related papers  (2024-06-18T20:02:44Z)
• Sampling and estimation on manifolds using the Langevin diffusion [45.57801520690309]
  Two estimators of linear functionals of $mu_phi $ based on the discretized Markov process are considered.<n>Error bounds are derived for sampling and estimation using a discretization of an intrinsically defined Langevin diffusion.
  arXiv  Detail & Related papers  (2023-12-22T18:01:11Z)
• The signaling dimension in generalized probabilistic theories [48.99818550820575]
  The signaling dimension of a given physical system quantifies the minimum dimension of a classical system required to reproduce all input/output correlations of the given system. We show that it suffices to consider extremal measurements with rayextremal effects, and we bound the number of elements of any such measurement in terms of the linear dimension. For systems with a finite number of extremal effects, we recast the problem of characterizing the extremal measurements with ray-extremal effects.
  arXiv  Detail & Related papers  (2023-11-22T02:09:16Z)
• Contrastive Moments: Unsupervised Halfspace Learning in Polynomial Time [8.419603619167813]
  We give a Gaussian-time algorithm for learning high-dimensional halfspaces with margins in $d$-dimensional space to within desired TV distance. Notably, our algorithm does not need labels and establishes unique (and efficient) identifiability of the hidden halfspace. We improve on this by providing polytime guarantees based on Total Variation (TV) distance, in place of existing moment-bound guarantees that can be super-polynomial.
  arXiv  Detail & Related papers  (2023-11-02T17:51:10Z)
• Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable Approach for Continuous Markov Random Fields [53.31927549039624]
  We show that a piecewise discretization preserves better contrast from existing discretization problems. We apply this theory to the problem of matching two images.
  arXiv  Detail & Related papers  (2021-07-13T12:31:06Z)
• Matrix factorisation and the interpretation of geodesic distance [6.445605125467574]
  Given a graph or similarity matrix, we consider the problem of recovering a notion of true distance between the nodes. We show that this can be accomplished in two steps: matrix factorisation, followed by nonlinear dimension reduction.
  arXiv  Detail & Related papers  (2021-06-02T16:11:33Z)
• Entropy-Regularized $2$-Wasserstein Distance between Gaussian Measures [2.320417845168326]
  We study the Gaussian geometry under the entropy-regularized 2-Wasserstein distance. We provide a fixed-point characterization of a population barycenter when restricted to the manifold of Gaussians. As the geometries change by varying the regularization magnitude, we study the limiting cases of vanishing and infinite magnitudes.
  arXiv  Detail & Related papers  (2020-06-05T13:18:57Z)
• Convex Geometry and Duality of Over-parameterized Neural Networks [70.15611146583068]
  We develop a convex analytic approach to analyze finite width two-layer ReLU networks. We show that an optimal solution to the regularized training problem can be characterized as extreme points of a convex set. In higher dimensions, we show that the training problem can be cast as a finite dimensional convex problem with infinitely many constraints.
  arXiv  Detail & Related papers  (2020-02-25T23:05:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.