論文の概要: Efficient Approximation of Gromov-Wasserstein Distance using Importance Sparsification

• arxiv url: http://arxiv.org/abs/2205.13573v1
• Date: Thu, 26 May 2022 18:30:40 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-30 13:24:32.484278
• Title: Efficient Approximation of Gromov-Wasserstein Distance using Importance Sparsification
• Title（参考訳）: 重要スパシフィケーションを用いたGromov-Wasserstein距離の効率的な近似
• Authors: Mengyu Li, Jun Yu, Hongteng Xu, Cheng Meng
• Abstract要約: 本稿では,Gromov-Wasserstein距離を効率的に近似するために,Spar-GWと呼ばれる新しい重要空間分割法を提案する。 Spar-GW法は任意の地価でGW距離に適用可能であることを示す。 さらに、この方法は、エントロピーGW距離、融合GW距離、不均衡GW距離を含むGW距離の変種を近似するために拡張することができる。
• 参考スコア（独自算出の注目度）: 34.865115235547286
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: As a valid metric of metric-measure spaces, Gromov-Wasserstein (GW) distance has shown the potential for the matching problems of structured data like point clouds and graphs. However, its application in practice is limited due to its high computational complexity. To overcome this challenge, we propose a novel importance sparsification method, called Spar-GW, to approximate GW distance efficiently. In particular, instead of considering a dense coupling matrix, our method leverages a simple but effective sampling strategy to construct a sparse coupling matrix and update it with few computations. We demonstrate that the proposed Spar-GW method is applicable to the GW distance with arbitrary ground cost, and it reduces the complexity from $\mathcal{O}(n^4)$ to $\mathcal{O}(n^{2+\delta})$ for an arbitrary small $\delta>0$. In addition, this method can be extended to approximate the variants of GW distance, including the entropic GW distance, the fused GW distance, and the unbalanced GW distance. Experiments show the superiority of our Spar-GW to state-of-the-art methods in both synthetic and real-world tasks.
• Abstract（参考訳）: 計量測度空間の有効な計量として、Gromov-Wasserstein (GW) 距離は、点雲やグラフのような構造化データの一致する問題の可能性を示している。 しかし、計算の複雑さが高いため、実際の用途は限られている。 この課題を克服するために、GW距離を効率的に近似するためのSpar-GWと呼ばれる新しい重要空間分割法を提案する。 特に, 密結合行列を考慮せず, 単純かつ効果的なサンプリング戦略を用いてスパース結合行列を構築し, 少ない計算量で更新する。 提案したSpar-GW法は任意の地上費用でGW距離に適用可能であることを示し、任意の小さな$\delta>0$に対して$\mathcal{O}(n^4)$から$\mathcal{O}(n^{2+\delta})$に複雑性を減少させる。 さらに、この方法は、エントロピーGW距離、融合GW距離、不均衡GW距離を含むGW距離の変種を近似するために拡張することができる。 実験により,Spar-GWと最先端の手法の両課題における優位性を示す。

関連論文リスト

• Linear Partial Gromov-Wasserstein Embedding [8.23887869467319]
  Gromov Wasserstein(GW)問題は、機械学習とデータサイエンスコミュニティへの関心が高まっている。 PGW問題に対する線形化埋め込み手法であるGromov Wasserstein埋め込みを提案する。 古典的 OT 問題に対する線形化手法と同様に、LPGW が計量測度空間の有効な計量を定義することを証明している。
  論文  参考訳（メタデータ） (2024-10-22T03:54:52Z)
• Relative-Translation Invariant Wasserstein Distance [82.6068808353647]
  距離の新しい族、相対翻訳不変ワッサーシュタイン距離(RW_p$)を導入する。 我々は、$RW_p 距離もまた、分布変換に不変な商集合 $mathcalP_p(mathbbRn)/sim$ 上で定義される実距離測度であることを示す。
  論文  参考訳（メタデータ） (2024-09-04T03:41:44Z)
• Scalable 3D Registration via Truncated Entry-wise Absolute Residuals [65.04922801371363]
  3ドルの登録アプローチでは、1000万ドル(107ドル)以上のポイントペアを、99%以上のランダムなアウトレイアで処理することができる。 我々はこの手法をTEARと呼び、Trncated Entry-wise Absolute Residualsを演算するoutlier-robust損失を最小限にする。
  論文  参考訳（メタデータ） (2024-04-01T04:43:39Z)
• Semidefinite Relaxations of the Gromov-Wasserstein Distance [8.971216891353752]
  グロモフ・ワッサー距離(Gromov-Wasser distance, GW)は、空間間の物体を一致させる最適な輸送問題の拡張である。 本稿では,GW距離の半定緩和法を提案する。 我々のアルゴリズムは、世界最適輸送計画(場合によっては)を、世界最適性の証明とともに計算する。
  論文  参考訳（メタデータ） (2023-12-22T10:09:52Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。 我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。 また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
  論文  参考訳（メタデータ） (2023-02-14T22:12:16Z)
• Outlier-Robust Gromov-Wasserstein for Graph Data [31.895380224961464]
  我々は、Gromov-Wasserstein (GW) 距離のRGWと呼ばれる新しい頑健なバージョンを導入する。 RGWは、クルバック・リーバーの発散に基づくあいまいさ集合の中で楽観的に摂動する限界制約を特徴とする。 サブグラフマッチングや部分形状対応などの実世界のグラフ学習におけるRGWの有効性を示す。
  論文  参考訳（メタデータ） (2023-02-09T12:57:29Z)
• Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
  我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。 我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
  論文  参考訳（メタデータ） (2022-10-14T01:42:05Z)
• Orthogonal Gromov-Wasserstein Discrepancy with Efficient Lower Bound [11.086440815804226]
  Gromov-Wasserstein (GW) は、最適な輸送データセットに基づいて、構造化されたデータ間のノードグラフを定式化する。 本稿では,代入問題との関係から着想を得て,GWの代理としてGromov-Wasserstein離散性を提案する。
  論文  参考訳（メタデータ） (2022-05-12T02:10:56Z)
• Quantized Gromov-Wasserstein [10.592277756185046]
  Quantized Gromov Wasserstein(qGW)は、部品を基本的なオブジェクトとして扱い、問題の理論上の上限の階層に収まるメトリクスです。 最適なgwマッチングを近似するアルゴリズムを開発し,アルゴリズムによる高速化とメモリ複雑性の低減を実現する。 我々は、最先端の状況を超えて、既存の文献よりも桁違いに大きいスケールでGWマッチングを適用することができる。
  論文  参考訳（メタデータ） (2021-04-05T17:03:20Z)
• Fast and Robust Comparison of Probability Measures in Heterogeneous Spaces [62.35667646858558]
  本稿では, アンカー・エナジー (AE) とアンカー・ワッサースタイン (AW) 距離を紹介する。 我々の主な貢献は、素案実装が立方体となる対数四重項時間でAEを正確に計算するスイープラインアルゴリズムを提案することである。 AE と AW は,一般的な GW 近似の計算コストのごく一部において,様々な実験環境において良好に動作することを示す。
  論文  参考訳（メタデータ） (2020-02-05T03:09:23Z)

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

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