論文の概要: Quantized Gromov-Wasserstein

• arxiv url: http://arxiv.org/abs/2104.02013v1
• Date: Mon, 5 Apr 2021 17:03:20 GMT
• ステータス: 処理完了
• システム内更新日: 2021-04-06 17:34:48.527449
• Title: Quantized Gromov-Wasserstein
• Title（参考訳）: 量子化Gromov-Wasserstein
• Authors: Samir Chowdhury, David Miller, Tom Needham
• Abstract要約: Quantized Gromov Wasserstein(qGW)は、部品を基本的なオブジェクトとして扱い、問題の理論上の上限の階層に収まるメトリクスです。 最適なgwマッチングを近似するアルゴリズムを開発し,アルゴリズムによる高速化とメモリ複雑性の低減を実現する。 我々は、最先端の状況を超えて、既存の文献よりも桁違いに大きいスケールでGWマッチングを適用することができる。
• 参考スコア（独自算出の注目度）: 10.592277756185046
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: The Gromov-Wasserstein (GW) framework adapts ideas from optimal transport to allow for the comparison of probability distributions defined on different metric spaces. Scalable computation of GW distances and associated matchings on graphs and point clouds have recently been made possible by state-of-the-art algorithms such as S-GWL and MREC. Each of these algorithmic breakthroughs relies on decomposing the underlying spaces into parts and performing matchings on these parts, adding recursion as needed. While very successful in practice, theoretical guarantees on such methods are limited. Inspired by recent advances in the theory of sketching for metric measure spaces, we define Quantized Gromov Wasserstein (qGW): a metric that treats parts as fundamental objects and fits into a hierarchy of theoretical upper bounds for the GW problem. This formulation motivates a new algorithm for approximating optimal GW matchings which yields algorithmic speedups and reductions in memory complexity. Consequently, we are able to go beyond outperforming state-of-the-art and apply GW matching at scales that are an order of magnitude larger than in the existing literature, including datasets containing over 1M points.
• Abstract（参考訳）: gromov-wasserstein (gw) フレームワークは、異なる距離空間上で定義される確率分布の比較を可能にするために最適輸送からのアイデアを適応させる。 S-GWL や MREC のような最先端のアルゴリズムにより,GW 距離のスケーラブルな計算とグラフおよび点雲上の関連マッチングが可能となった。 それぞれのアルゴリズムのブレークスルーは、基礎となる空間を部品に分解し、必要に応じて再帰を加えることに依存する。 実際には非常に成功したが、そのような方法に関する理論的保証は限られている。 計量測度空間のスケッチ理論の最近の進歩に触発され、量子化グロモフ・ワッサーシュタイン (Quantized Gromov Wasserstein, qGW) を定義する。 この定式化は、アルゴリズムの高速化とメモリ複雑性の低減をもたらす最適なGWマッチングを近似する新しいアルゴリズムを動機付けている。 その結果,100万点を超えるデータセットを含む,既存の文献よりも桁違いの大きさのスケールでGWマッチングを適用することが可能になった。

関連論文リスト

• Metric properties of partial and robust Gromov-Wasserstein distances [3.9485589956945204]
  グロモフ=ワッサーシュタイン距離(Gromov-Wasserstein distance, GW)は、最適な輸送のアイデアに基づいて、メトリクスの族を定義する。 GW距離は本質的に外れ音に敏感であり、部分的マッチングに対応できない。 我々の新しい距離は真の測度を定義し、それらがGW距離と同じ位相を誘導し、摂動にさらなる堅牢性をもたらすことを示す。
  論文  参考訳（メタデータ） (2024-11-04T15:53:45Z)
• Covariance alignment: from maximum likelihood estimation to Gromov-Wasserstein [27.2585517709102]
  また, 最適輸送によるGromov-Wassersteinアルゴリズムも最適であることを示す。 これらの結果は、Gromov-Wassersteinアルゴリズムを実際に展開するための最初の統計的正当性を与える。
  論文  参考訳（メタデータ） (2023-11-22T18:55:27Z)
• 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)
• Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
  点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。 第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
  論文  参考訳（メタデータ） (2023-02-02T08:33:36Z)
• Efficient Approximation of Gromov-Wasserstein Distance using Importance Sparsification [34.865115235547286]
  本稿では,Gromov-Wasserstein距離を効率的に近似するために,Spar-GWと呼ばれる新しい重要空間分割法を提案する。 Spar-GW法は任意の地価でGW距離に適用可能であることを示す。 さらに、この方法は、エントロピーGW距離、融合GW距離、不均衡GW距離を含むGW距離の変種を近似するために拡張することができる。
  論文  参考訳（メタデータ） (2022-05-26T18:30:40Z)
• Orthogonal Gromov-Wasserstein Discrepancy with Efficient Lower Bound [11.086440815804226]
  Gromov-Wasserstein (GW) は、最適な輸送データセットに基づいて、構造化されたデータ間のノードグラフを定式化する。 本稿では,代入問題との関係から着想を得て,GWの代理としてGromov-Wasserstein離散性を提案する。
  論文  参考訳（メタデータ） (2022-05-12T02:10:56Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。 このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。 我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-03-28T21:34:16Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Finding Geometric Models by Clustering in the Consensus Space [61.65661010039768]
  本稿では,未知数の幾何学的モデル,例えばホモグラフィーを求めるアルゴリズムを提案する。 複数の幾何モデルを用いることで精度が向上するアプリケーションをいくつか提示する。 これには、複数の一般化されたホモグラフからのポーズ推定、高速移動物体の軌道推定が含まれる。
  論文  参考訳（メタデータ） (2021-03-25T14:35:07Z)
• Fast and Robust Comparison of Probability Measures in Heterogeneous Spaces [62.35667646858558]
  本稿では, アンカー・エナジー (AE) とアンカー・ワッサースタイン (AW) 距離を紹介する。 我々の主な貢献は、素案実装が立方体となる対数四重項時間でAEを正確に計算するスイープラインアルゴリズムを提案することである。 AE と AW は,一般的な GW 近似の計算コストのごく一部において,様々な実験環境において良好に動作することを示す。
  論文  参考訳（メタデータ） (2020-02-05T03:09:23Z)

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

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