A Linear Transportation $\mathrm{L}^p$ Distance for Pattern Recognition

• URL: http://arxiv.org/abs/2009.11262v1
• Date: Wed, 23 Sep 2020 17:19:19 GMT
• Title: A Linear Transportation $\mathrm{L}^p$ Distance for Pattern Recognition
• Authors: Oliver M. Crook, Mihai Cucuringu, Tim Hurst, Carola-Bibiane Sch\"onlieb, Matthew Thorpe and Konstantinos C. Zygalakis
• Abstract summary: The transportation $mathrmLp$ distance has been proposed as a generalisation of Wasserstein $mathrmWp$ distances. We show that the linear $mathrmTLp$ distance significantly improves over the linear $mathrmWp$ distance on signal processing tasks.
• Score: 4.991212094743681
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The transportation $\mathrm{L}^p$ distance, denoted $\mathrm{TL}^p$, has been proposed as a generalisation of Wasserstein $\mathrm{W}^p$ distances motivated by the property that it can be applied directly to colour or multi-channelled images, as well as multivariate time-series without normalisation or mass constraints. These distances, as with $\mathrm{W}^p$, are powerful tools in modelling data with spatial or temporal perturbations. However, their computational cost can make them infeasible to apply to even moderate pattern recognition tasks. We propose linear versions of these distances and show that the linear $\mathrm{TL}^p$ distance significantly improves over the linear $\mathrm{W}^p$ distance on signal processing tasks, whilst being several orders of magnitude faster to compute than the $\mathrm{TL}^p$ distance.

Related papers

• IT$^3$: Idempotent Test-Time Training [95.78053599609044]
  This paper introduces Idempotent Test-Time Training (IT$3$), a novel approach to addressing the challenge of distribution shift. IT$3$ is based on the universal property of idempotence. We demonstrate the versatility of our approach across various tasks, including corrupted image classification.
  arXiv  Detail & Related papers  (2024-10-05T15:39:51Z)
• Relative-Translation Invariant Wasserstein Distance [82.6068808353647]
  We introduce a new family of distances, relative-translation invariant Wasserstein distances ($RW_p$) We show that $RW_p distances are also real distance metrics defined on the quotient set $mathcalP_p(mathbbRn)/sim$ invariant to distribution translations.
  arXiv  Detail & Related papers  (2024-09-04T03:41:44Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  Multi-head attention layer is one of the key components of the transformer architecture that sets it apart from traditional feed-forward models. In this work, we initiate the study of provably learning a multi-head attention layer from random examples. We prove computational lower bounds showing that in the worst case, exponential dependence on $m$ is unavoidable.
  arXiv  Detail & Related papers  (2024-02-06T15:39:09Z)
• A Near-Linear Time Algorithm for the Chamfer Distance [21.018781726524946]
  Chamfer distance is a popular measure of dissimilarity between point clouds. We present the first $(1+epsilon)$-approximate algorithm for estimating the Chamfer distance with a near-linear running time. Our experiments demonstrate that it is both accurate and fast on large high-dimensional datasets.
  arXiv  Detail & Related papers  (2023-07-06T15:07:48Z)
• The Monge Gap: A Regularizer to Learn All Transport Maps [34.81915836064636]
  Brenier's theorem states that when the ground cost is the squared-Euclidean distance, the best'' map to morph a continuous measure in $mathcalP(Rd)$ into another must be the gradient of a convex function. Despite their mathematical elegance, fitting OT maps with ICNNs raises many challenges. We propose a radically different approach to estimating OT maps.
  arXiv  Detail & Related papers  (2023-02-09T21:56:11Z)
• Simplifying and Understanding State Space Models with Diagonal Linear RNNs [56.33053691749856]
  This work disposes of the discretization step, and proposes a model based on vanilla Diagonal Linear RNNs. We empirically show that, despite being conceptually much simpler, $mathrmDLR$ is as performant as previously-proposed SSMs. We also characterize the expressivity of SSMs and attention-based models via a suite of $13$ synthetic sequence-to-sequence tasks.
  arXiv  Detail & Related papers  (2022-12-01T18:53:06Z)
• Metricizing the Euclidean Space towards Desired Distance Relations in Point Clouds [1.2366208723499545]
  We attack unsupervised learning algorithms, specifically $k$-Means and density-based (DBSCAN) clustering algorithms. We show that the results of clustering algorithms may not generally be trustworthy, unless there is a standardized and fixed prescription to use a specific distance function.
  arXiv  Detail & Related papers  (2022-11-07T16:37:29Z)
• Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
  We consider the problem of learning a latent $k$-vertex simplex $KsubsetmathbbRdtimes n$, given access to $AinmathbbRdtimes n$. We show that the dependence on $k$ in the running time is unnecessary given a natural assumption about the mass of the top $k$ singular values of $A$.
  arXiv  Detail & Related papers  (2021-05-17T16:40:48Z)
• Faster Binary Embeddings for Preserving Euclidean Distances [9.340611077939828]
  We propose a fast, distance-preserving, binary embedding algorithm to transform a dataset $mathcalTsubseteqmathbbRn$ into binary sequences in the cube $pm 1m$. Our method is both fast and memory efficient, with time complexity $O(m)$ and space complexity $O(m)$.
  arXiv  Detail & Related papers  (2020-10-01T22:41:41Z)
• An $\tilde{O}(n^{5/4})$ Time $\varepsilon$-Approximation Algorithm for RMS Matching in a Plane [3.9596068699962315]
  The 2-Wasserstein distance (or RMS distance) is a useful measure of similarity between probability distributions. We present a new $varepsilon$-approximation algorithm that runs in $O(n5/4mathrmpolylog n,1/varepsilon)$ time.
  arXiv  Detail & Related papers  (2020-07-15T14:47:25Z)
• Few-Shot Learning via Learning the Representation, Provably [115.7367053639605]
  This paper studies few-shot learning via representation learning. One uses $T$ source tasks with $n_1$ data per task to learn a representation in order to reduce the sample complexity of a target task.
  arXiv  Detail & Related papers  (2020-02-21T17:30:00Z)

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.