Fugu-MT 論文翻訳(概要): Wasserstein barycenters can be computed in polynomial time in fixed dimension

論文の概要: Wasserstein barycenters can be computed in polynomial time in fixed dimension

arxiv url: http://arxiv.org/abs/2006.08012v2
Date: Wed, 9 Dec 2020 22:15:32 GMT
ステータス: 処理完了
システム内更新日: 2022-11-21 13:41:12.274251
Title: Wasserstein barycenters can be computed in polynomial time in fixed dimension
Title（参考訳）: Wasserstein Barycenters は固定次元の多項式時間で計算できる
Authors: Jason M. Altschuler, Enric Boix-Adsera
Abstract要約: ヴァッサーシュタインのバリセンタが時間で計算できるか、高精度に計算できるかは不明である。我々のアプローチは指数関数サイズの線形プログラミングの定式化を解くことである。
参考スコア（独自算出の注目度）: 2.66512000865131
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Computing Wasserstein barycenters is a fundamental geometric problem with widespread applications in machine learning, statistics, and computer graphics. However, it is unknown whether Wasserstein barycenters can be computed in polynomial time, either exactly or to high precision (i.e., with $\textrm{polylog}(1/\varepsilon)$ runtime dependence). This paper answers these questions in the affirmative for any fixed dimension. Our approach is to solve an exponential-size linear programming formulation by efficiently implementing the corresponding separation oracle using techniques from computational geometry.
Abstract（参考訳）: コンピューティング wasserstein barycenters は、機械学習、統計学、コンピュータグラフィックスに広く応用される基本的な幾何学的問題である。しかし、Wasserstein Barycenters が多項式時間、正確にまたは高い精度で計算できるかどうかは不明である(例えば $\textrm{polylog}(1/\varepsilon)$ ランタイム依存)。本稿では,任意の固定次元に対する肯定的質問に答える。計算幾何学の手法を用いて, 対応する分離オラクルを効率よく実装することにより, 指数関数型線形プログラミングの定式化を解く。

関連論文リスト

Towards Efficient Time Stepping for Numerical Shape Correspondence [55.2480439325792]
偏微分方程式(PDE)に基づく手法が確立されており、例えば古典的な熱核シグネチャを含む。本研究の目的は,形状解析の文脈における時間積分の手法の有用な性質を特定できるかどうかを評価することである。
論文参考訳（メタデータ） (2023-12-21T13:40:03Z)
Approximating a RUM from Distributions on k-Slates [88.32814292632675]
与えられた分布を平均で最もよく近似するRUMを求める一般化時間アルゴリズムを求める。我々の理論的結果は、実世界のデータセットに効果的でスケール可能なものを得るという、実践的な結果も得られます。
論文参考訳（メタデータ） (2023-05-22T17:43:34Z)
Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
論文参考訳（メタデータ） (2023-02-14T22:12:16Z)
Stability of Entropic Wasserstein Barycenters and application to random geometric graphs [8.7314407902481]
ワッサーシュタイン・バリーセンタ(Wasserstein Barycenters、WB)は、最適輸送の理論に由来するバリーセンタの概念である。離散化されたメッシュ上のWBが基底多様体の幾何学とどのように関係するかを示す。
論文参考訳（メタデータ） (2022-10-19T13:17:03Z)
Leverage Score Sampling for Tensor Product Matrices in Input Sparsity Time [54.65688986250061]
我々は,$q$-foldカラムワイドテンソル積の$q$行列に対応するグラム行列を近似するための入力空間時間サンプリングアルゴリズムを提案する。我々のサンプリング技術は、合計時間でデータセット$X$に同時に適用できる$q$部分相関ランダムプロジェクションのコレクションに依存している。
論文参考訳（メタデータ） (2022-02-09T15:26:03Z)
Wasserstein Iterative Networks for Barycenter Estimation [80.23810439485078]
生成モデルを用いて連続測度のワッサーシュタイン2バリセンターを近似するアルゴリズムを提案する。有名人の顔のデータセットに基づいて、バリセンタアルゴリズムの定量的評価に使用できるAve, celeba!データセットを構築した。
論文参考訳（メタデータ） (2022-01-28T16:59:47Z)
Dimensionality Reduction for Wasserstein Barycenter [6.327655795051619]
本稿では,Wasserstein Barycenter問題に対する次元還元手法について検討する。ランダム化次元減少は、その問題を$d$と$k$に独立に次元$O(log n)$の空間にマッピングするために利用できることを示す。また、Wasserstein Barycenter問題に対するコアセットの構成も提供し、入力分布を著しく減少させる。
論文参考訳（メタデータ） (2021-10-18T02:57:25Z)
Fixed Support Tree-Sliced Wasserstein Barycenter [40.087553363884396]
本研究では, 固定支持木-ワッセルシュタインバリセンタ (FS-TWB) と呼ばれる木-ワッセルシュタイン距離下のバリセンタと, 固定支持木-スライスされたワッセルシュタインバリセンタ (FS-TSWB) と呼ばれる拡張部を提案する。 FS-TWB と FS-TSWB は,元の Wasserstein バリセンタよりも2桁早く解けることを示す。
論文参考訳（メタデータ） (2021-09-08T04:50:33Z)
Projection Robust Wasserstein Barycenter [36.97843660480747]
ワッサースタイン・バリセンターの近似は次元の呪いのため数値的に困難です本稿では,次元の呪いを緩和するプロジェクションロバストなワッサーシュタインバリセンタ(PRWB)を提案する。
論文参考訳（メタデータ） (2021-02-05T19:23:35Z)
Wasserstein barycenters are NP-hard to compute [0.0]
Wasserstein barycenters(a.k.a.)の計算の問題 Optimal Transport Barycenters)は、データサイエンスの多くの応用により、近年注目を集めています。この指数依存性が依存に対して即興であるかどうかは明らかな疑問である。本稿では,計算における「次元の帰結」を明らかにする。
論文参考訳（メタデータ） (2021-01-04T17:16:45Z)
Fast and Robust Comparison of Probability Measures in Heterogeneous Spaces [62.35667646858558]
本稿では, アンカー・エナジー (AE) とアンカー・ワッサースタイン (AW) 距離を紹介する。我々の主な貢献は、素案実装が立方体となる対数四重項時間でAEを正確に計算するスイープラインアルゴリズムを提案することである。 AE と AW は,一般的な GW 近似の計算コストのごく一部において,様々な実験環境において良好に動作することを示す。
論文参考訳（メタデータ） (2020-02-05T03:09:23Z)

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