論文の概要: Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair

• arxiv url: http://arxiv.org/abs/2508.06774v1
• Date: Sat, 09 Aug 2025 02:00:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-31 21:54:20.512418
• Title: Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair
• Title（参考訳）: 高次元Mover距離を最も近いペアで近似する
• Authors: Lorenzo Beretta, Vincent Cohen-Addad, Rajesh Jayaram, Erik Waingarten,
• Abstract要約: 我々は、$(varepsilon)$-approximate Earth Mover's Distance (EMD)から$(varepsilon)$-approximate Closest Pair (CP)へ還元する。 CPをn2-phi$で計算し、1+O(varepsilon)$で計算し、n2-phi$で計算できることが示される。
• 参考スコア（独自算出の注目度）: 22.19805331012499
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We give a reduction from $(1+\varepsilon)$-approximate Earth Mover's Distance (EMD) to $(1+\varepsilon)$-approximate Closest Pair (CP). As a consequence, we improve the fastest known approximation algorithm for high-dimensional EMD. Here, given $p\in [1, 2]$ and two sets of $n$ points $X,Y \subseteq (\mathbb R^d,\ell_p)$, their EMD is the minimum cost of a perfect matching between $X$ and $Y$, where the cost of matching two vectors is their $\ell_p$ distance. Further, CP is the basic problem of finding a pair of points realizing $\min_{x \in X, y\in Y} ||x-y||_p$. Our contribution is twofold: we show that if a $(1+\varepsilon)$-approximate CP can be computed in time $n^{2-\phi}$, then a $1+O(\varepsilon)$ approximation to EMD can be computed in time $n^{2-\Omega(\phi)}$; plugging in the fastest known algorithm for CP [Alman, Chan, Williams FOCS'16], we obtain a $(1+\varepsilon)$-approximation algorithm for EMD running in time $n^{2-\tilde{\Omega}(\varepsilon^{1/3})}$ for high-dimensional point sets, which improves over the prior fastest running time of $n^{2-\Omega(\varepsilon^2)}$ [Andoni, Zhang FOCS'23]. Our main technical contribution is a sublinear implementation of the Multiplicative Weights Update framework for EMD. Specifically, we demonstrate that the updates can be executed without ever explicitly computing or storing the weights; instead, we exploit the underlying geometric structure to perform the updates implicitly.
• Abstract（参考訳）: 1+\varepsilon)$-approximate Earth Mover's Distance (EMD) から$(1+\varepsilon)$-approximate Closest Pair (CP) へ還元する。 その結果,高次元EMDの近似アルゴリズムの高速化が図られた。 ここで、$p\in [1, 2]$と$n$ポイント$X,Y \subseteq (\mathbb R^d,\ell_p)$の2組が与えられたとき、彼らのEMDは$X$と$Y$の完全マッチングの最小コストである。 さらに、CP は $\min_{x \in X, y\in Y} ||x-y||_p$ を満たす点の対を見つける基本的な問題である。 1+\varepsilon)$-approximate CP がtime $n^{2-\phi}$で計算できるなら、1+O(\varepsilon)$ Approximation to EMD がtime $n^{2-\Omega(\phi)}$で計算できる。 私たちの主な技術的貢献は、EMDのためのMultiplicative Weights Updateフレームワークのサブ線形実装です。 具体的には、更新を明示的に計算したり、重みを格納したりすることなく実行できることを示し、代わりに、基礎となる幾何学的構造を利用して暗黙的に更新を実行する。

関連論文リスト

• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。 これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。 また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
  論文  参考訳（メタデータ） (2024-08-16T02:33:07Z)
• Ridge Leverage Score Sampling for $\ell_p$ Subspace Approximation [47.790126028106734]
  NPハードネスに対処するための一般的なアプローチは、強力なコアセットを計算することである。 我々は$ell_p$サブスペース近似を$tilde O(kepsilon-4/p)$ for $p2$と$tilde O(kp/2epsilon-p)$ for $p>2$に対して強コアセットを構築するアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-07-03T16:49:28Z)
• Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams [34.7582575446942]
  準多項式依存のMDSに対する最初の近似アルゴリズムをDeltaに与える。 本アルゴリズムは,シェラリ・アダムスLPの条件付きラウンドリングの幾何学的認識に基づく新しい解析法である。
  論文  参考訳（メタデータ） (2023-11-29T17:42:05Z)
• $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
  コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。 p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。 p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
  論文  参考訳（メタデータ） (2023-07-11T08:51:53Z)
• Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces [2.687607197645453]
  次元$Theta(log n)$ が $(sqrt3/2-o(1))$hard である場合でさえ、FPTアルゴリズムを近似する。 また、次元 $Theta(log n)$ が $(sqrt3/2-o(1))$hard であるような特別な場合でさえ、FPTアルゴリズムを近似することを示す。
  論文  参考訳（メタデータ） (2023-05-12T08:43:28Z)
• Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
  報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討 我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
  論文  参考訳（メタデータ） (2022-10-05T22:52:00Z)
• Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions [51.19236668224547]
  テンソルの低階近似について検討し,テンソルトレインとタッカー分解に着目した。 テンソル列車の分解には、小さなビクリテリアランクを持つビクリテリア$(1 + eps)$-approximationアルゴリズムと、O(q cdot nnz(A))$ランニングタイムを与える。 さらに、任意のグラフを持つテンソルネットワークにアルゴリズムを拡張します。
  論文  参考訳（メタデータ） (2022-07-15T11:55:09Z)
• On Efficient Low Distortion Ultrametric Embedding [18.227854382422112]
  データの基盤となる階層構造を保存するために広く用いられる方法は、データを木や超音波に埋め込む方法を見つけることである。 本稿では,$mathbbRd2(ユニバーサル定数$rho>1$)の点集合を入力として,超測度$Deltaを出力する新しいアルゴリズムを提案する。 我々のアルゴリズムの出力はリンクアルゴリズムの出力に匹敵するが、より高速な実行時間を実現する。
  論文  参考訳（メタデータ） (2020-08-15T11:06:45Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。