Fugu-MT 論文翻訳(概要): The NP-hardness of the Gromov-Wasserstein distance

論文の概要: The NP-hardness of the Gromov-Wasserstein distance

arxiv url: http://arxiv.org/abs/2408.06525v1
Date: Mon, 12 Aug 2024 23:04:30 GMT
ステータス: 処理完了
システム内更新日: 2024-08-14 19:07:10.109022
Title: The NP-hardness of the Gromov-Wasserstein distance
Title（参考訳）: Gromov-Wasserstein距離のNP硬度
Authors: Natalia Kravtsova,
Abstract要約: このノートは、Gro-Wasserstein (GW) 距離が NP-hard であるという文献でしばしば言及される性質を取り上げている。我々は、任意の有限空間に対する有限空間間の距離のNP硬度を暗示するGW問題に関するデータを提供する。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: This note addresses the property frequently mentioned in the literature that the Gromov-Wasserstein (GW) distance is NP-hard. We provide the details on the non-convex nature of the GW optimization problem that imply NP-hardness of the GW distance between finite spaces for any instance of an input data. We further illustrate the non-convexity of the problem with several explicit examples.
Abstract（参考訳）: このノートは、Gromov-Wasserstein (GW) 距離が NP-hard であるという文献でしばしば言及される性質を取り上げている。入力データの任意のインスタンスに対して有限空間間のGW距離のNP硬度を示すGW最適化問題の非凸性の詳細を提供する。さらに、いくつかの明示的な例で、問題の非凸性について説明する。

関連論文リスト

Metric properties of partial and robust Gromov-Wasserstein distances [3.9485589956945204]
グロモフ=ワッサーシュタイン距離(Gromov-Wasserstein distance, GW)は、最適な輸送のアイデアに基づいて、メトリクスの族を定義する。 GW距離は本質的に外れ音に敏感であり、部分的マッチングに対応できない。我々の新しい距離は真の測度を定義し、それらがGW距離と同じ位相を誘導し、摂動にさらなる堅牢性をもたらすことを示す。
論文参考訳（メタデータ） (2024-11-04T15:53:45Z)
Linear Partial Gromov-Wasserstein Embedding [8.23887869467319]
Gromov Wasserstein(GW)問題は、機械学習とデータサイエンスコミュニティへの関心が高まっている。 PGW問題に対する線形化埋め込み手法であるGromov Wasserstein埋め込みを提案する。古典的 OT 問題に対する線形化手法と同様に、LPGW が計量測度空間の有効な計量を定義することを証明している。
論文参考訳（メタデータ） (2024-10-22T03:54:52Z)
All You Need is Resistance: On the Equivalence of Effective Resistance and Certain Optimal Transport Problems on Graphs [48.84819106277247]
我々は、グラフ上の効果的な抵抗と最適輸送は、最大$p$を選択するまで、一つと同じものとして理解されるべきであると主張する。最適停止時間とグラフ上のランダムウォーク,グラフソボレフ空間,ベナモ・ブレニエ型式に対する2ドルベックマン距離の明示的な接続を示す。本稿では、ワッサーシュタイン距離が計算ボトルネックを引き起こす可能性のあるこれらの指標のさらなる利用法を提案する。
論文参考訳（メタデータ） (2024-04-23T17:50:52Z)
A Convergent Single-Loop Algorithm for Relaxation of Gromov-Wasserstein in Graph Data [37.89640056739607]
本稿では,Gromov-Wasserstein (GW) 距離の近似解を提供する単一ループアルゴリズムであるBregman Alternating Projected Gradient (BAPG) を提案する。本稿では,カップリングマップの実現可能性においていくつかの妥協点があるにもかかわらず,精度と計算効率のバランスをとる新しい緩和手法を提案する。
論文参考訳（メタデータ） (2023-03-12T07:23:16Z)
Uncovering Challenges of Solving the Continuous Gromov-Wasserstein Problem [63.99794069984492]
グロモフ=ワッサーシュタイン最適輸送(Gromov-Wasserstein Optimal Transport, GWOT)問題は、MLコミュニティの特別な関心を集めている。既存の連続GWOTアプローチをさまざまなシナリオでクラッシュテストし、結果を注意深く記録し分析し、問題を特定します。本稿では,離散的手法に依存しない新たな連続GWOT法を提案し,競合の問題を部分的に解決する。
論文参考訳（メタデータ） (2023-03-10T15:21:12Z)
Markovian Sliced Wasserstein Distances: Beyond Independent Projections [51.80527230603978]
我々は、射影方向にマルコフ構造を課す新しいSW距離の族、Markovian sliced Wasserstein (MSW) 距離を導入する。フロー,色移動,深部生成モデルなどの様々な応用において,従来のSW変種との距離を比較し,MSWの良好な性能を示す。
論文参考訳（メタデータ） (2023-01-10T01:58:15Z)
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)
Augmented Sliced Wasserstein Distances [55.028065567756066]
拡張スライスされたワッサーシュタイン距離(ASWD)と呼ばれる新しい距離測定法を提案する。 ASWDは、ニューラルネットワークによってパラメータ化された高次元超曲面への最初のマッピングサンプルによって構成される。数値的な結果から、ASWDは、合成問題と実世界の問題の両方において、他のワッサーシュタイン変種を著しく上回っていることが示されている。
論文参考訳（メタデータ） (2020-06-15T23:00:08Z)
Projection Robust Wasserstein Distance and Riemannian Optimization [107.93250306339694]
プロジェクション・ソリッドスタイン(PRW)は、ワッサーシュタイン・プロジェクション(WPP)のロバストな変種であることを示す。本稿では,PRW距離の計算への第一歩として,その理論と実データに関する実験の関連について述べる。
論文参考訳（メタデータ） (2020-06-12T20:40:22Z)
Fast and Robust Comparison of Probability Measures in Heterogeneous Spaces [62.35667646858558]
本稿では, アンカー・エナジー (AE) とアンカー・ワッサースタイン (AW) 距離を紹介する。我々の主な貢献は、素案実装が立方体となる対数四重項時間でAEを正確に計算するスイープラインアルゴリズムを提案することである。 AE と AW は,一般的な GW 近似の計算コストのごく一部において,様々な実験環境において良好に動作することを示す。
論文参考訳（メタデータ） (2020-02-05T03:09:23Z)

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