論文の概要: An $\tilde{O}(n^{5/4})$ Time $\varepsilon$-Approximation Algorithm for
RMS Matching in a Plane
- arxiv url: http://arxiv.org/abs/2007.07720v1
- Date: Wed, 15 Jul 2020 14:47:25 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-10 06:48:47.121836
- Title: An $\tilde{O}(n^{5/4})$ Time $\varepsilon$-Approximation Algorithm for
RMS Matching in a Plane
- Title（参考訳）: 平面に一致するrmsに対する$\tilde{o}(n^{5/4})$ time $\varepsilon$近似アルゴリズム
- Authors: Nathaniel Lahn, Sharath Raghvendra
- Abstract要約: 2-ワッサーシュタイン距離(英: 2-Wasserstein distance、RMS distance)は確率分布間の類似性の有用な尺度である。
我々は$O(n5/4mathrmpolylog n,1/varepsilon)$timeで実行される新しい$varepsilon$-approximationアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 3.9596068699962315
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The 2-Wasserstein distance (or RMS distance) is a useful measure of
similarity between probability distributions that has exciting applications in
machine learning. For discrete distributions, the problem of computing this
distance can be expressed in terms of finding a minimum-cost perfect matching
on a complete bipartite graph given by two multisets of points $A,B \subset
\mathbb{R}^2$, with $|A|=|B|=n$, where the ground distance between any two
points is the squared Euclidean distance between them. Although there is a
near-linear time relative $\varepsilon$-approximation algorithm for the case
where the ground distance is Euclidean (Sharathkumar and Agarwal, JACM 2020),
all existing relative $\varepsilon$-approximation algorithms for the RMS
distance take $\Omega(n^{3/2})$ time. This is primarily because, unlike
Euclidean distance, squared Euclidean distance is not a metric. In this paper,
for the RMS distance, we present a new $\varepsilon$-approximation algorithm
that runs in $O(n^{5/4}\mathrm{poly}\{\log n,1/\varepsilon\})$ time.
Our algorithm is inspired by a recent approach for finding a minimum-cost
perfect matching in bipartite planar graphs (Asathulla et al., TALG 2020).
Their algorithm depends heavily on the existence of sub-linear sized vertex
separators as well as shortest path data structures that require planarity.
Surprisingly, we are able to design a similar algorithm for a complete
geometric graph that is far from planar and does not have any vertex
separators. Central components of our algorithm include a quadtree-based
distance that approximates the squared Euclidean distance and a data structure
that supports both Hungarian search and augmentation in sub-linear time.
- Abstract（参考訳）: 2-wasserstein距離(またはrms距離)は、機械学習にエキサイティングな応用をもたらす確率分布の類似性の有用な尺度である。
離散分布に対して、この距離を計算する問題は、2つの点の多重集合 $a,b \subset \mathbb{r}^2$, with $|a|=|b|=n$ によって与えられる完全二部グラフ上の最小コストの完全マッチングを見つけるという観点で表現できる。
地上距離がユークリッド(英語版)(Sharathkumar and Agarwal, JACM 2020)である場合、ほぼ直線時間で$\varepsilon$-approximationアルゴリズムがあるが、既存のRMS距離に対する$\varepsilon$-approximationアルゴリズムは$\Omega(n^{3/2})$timeである。
これは主にユークリッド距離とは異なり、平方ユークリッド距離が計量ではないためである。
本稿では、RMS距離に対して、$O(n^{5/4}\mathrm{poly}\{\log n,1/\varepsilon\})$timeで実行される新しい$\varepsilon$-approximationアルゴリズムを提案する。
我々のアルゴリズムは、二部平面グラフにおける最小コスト完全マッチングを求める最近のアプローチに触発されている(asathulla et al., talg 2020)。
それらのアルゴリズムは、平面性を必要とする最短経路データ構造と同様に、サブ線形サイズの頂点分離器の存在に大きく依存する。
意外なことに、平面から遠く、頂点分離器を持たない完全幾何グラフに対して、同様のアルゴリズムを設計することができる。
アルゴリズムの中心的な構成要素は、正方形ユークリッド距離を近似するクワッドツリーに基づく距離と、ハンガリー語検索と亜線形時間の拡張の両方をサポートするデータ構造である。
関連論文リスト
- Relative-Translation Invariant Wasserstein Distance [82.6068808353647]
距離の新しい族、相対翻訳不変ワッサーシュタイン距離(RW_p$)を導入する。
我々は、$RW_p 距離もまた、分布変換に不変な商集合 $mathcalP_p(mathbbRn)/sim$ 上で定義される実距離測度であることを示す。
論文 参考訳（メタデータ） (2024-09-04T03:41:44Z) - A Near-Linear Time Algorithm for the Chamfer Distance [21.018781726524946]
チャンファー距離は点雲間の相似性の一般的な尺度である。
1+epsilon)$-approximate アルゴリズムは,Chamfer 距離をほぼ直線走行時間で推定する。
我々の実験は、大規模な高次元データセット上では正確かつ高速であることを示した。
論文 参考訳（メタデータ） (2023-07-06T15:07:48Z) - Linearized Wasserstein dimensionality reduction with approximation
guarantees [65.16758672591365]
LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。
我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。
また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
論文 参考訳（メタデータ） (2023-02-14T22:12:16Z) - Metricizing the Euclidean Space towards Desired Distance Relations in
Point Clouds [1.2366208723499545]
我々は教師なし学習アルゴリズム、具体的には$k$-Means and density-based clustering algorithm(DBSCAN)を攻撃している。
クラスタリングアルゴリズムの結果は、特定の距離関数を使用するための標準化された固定された処方令がなければ、一般的には信頼できない可能性がある。
論文 参考訳（メタデータ） (2022-11-07T16:37:29Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - A Push-Relabel Based Additive Approximation for Optimal Transport [5.111364864495785]
最適な輸送を計算するための厳密なアルゴリズムは遅くなる。
我々は、OT距離の$varepsilon$approximationを求めるための、新しい非常に単純なアプローチを導入する。
我々のアルゴリズムは、OT距離を計算するために、O(n2/varepsilon2)$のほぼ最適実行時間を達成する。
論文 参考訳（メタデータ） (2022-03-07T21:40:14Z) - Well Separated Pair Decomposition and power weighted shortest path
metric algorithm fusion [0.0]
私たちは、あるポイントセットで$s$-wellの分離ペアを$mathbbrn$, $n$$$>$$1で計算するアルゴリズムを考えています。
また、ダイクストラのアルゴリズムの置換であるアルゴリズムについても検討し、特定のパワー重み付き最短経路メトリックを用いてk$-nearestの隣人を計算し、$mathbbrn$,$n$$$$$$$$$$で計算する。
論文 参考訳（メタデータ） (2021-03-20T17:38:13Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z) - On Efficient Low Distortion Ultrametric Embedding [18.227854382422112]
データの基盤となる階層構造を保存するために広く用いられる方法は、データを木や超音波に埋め込む方法を見つけることである。
本稿では,$mathbbRd2(ユニバーサル定数$rho>1$)の点集合を入力として,超測度$Deltaを出力する新しいアルゴリズムを提案する。
我々のアルゴリズムの出力はリンクアルゴリズムの出力に匹敵するが、より高速な実行時間を実現する。
論文 参考訳（メタデータ） (2020-08-15T11:06:45Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。