論文の概要: Globally solving the Gromov-Wasserstein problem for point clouds in low dimensional Euclidean spaces

• arxiv url: http://arxiv.org/abs/2307.09057v1
• Date: Tue, 18 Jul 2023 08:20:56 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-19 15:42:15.797525
• Title: Globally solving the Gromov-Wasserstein problem for point clouds in low dimensional Euclidean spaces
• Title（参考訳）: 低次元ユークリッド空間における点雲のグロモフ・ワッセルシュタイン問題に対する大域的解法
• Authors: Martin Ryner, Jan Kronqvist, Johan Karlsson
• Abstract要約: 本稿では,低次元空間における2つの点間のGromov-Wasserstein問題を計算するための枠組みを提案する。 これは、AIと機械学習における一般的な問題である2つの構成または形状の類似性を定量化するために使用できる。
• 参考スコア（独自算出の注目度）: 5.534626267734822
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper presents a framework for computing the Gromov-Wasserstein problem between two sets of points in low dimensional spaces, where the discrepancy is the squared Euclidean norm. The Gromov-Wasserstein problem is a generalization of the optimal transport problem that finds the assignment between two sets preserving pairwise distances as much as possible. This can be used to quantify the similarity between two formations or shapes, a common problem in AI and machine learning. The problem can be formulated as a Quadratic Assignment Problem (QAP), which is in general computationally intractable even for small problems. Our framework addresses this challenge by reformulating the QAP as an optimization problem with a low-dimensional domain, leveraging the fact that the problem can be expressed as a concave quadratic optimization problem with low rank. The method scales well with the number of points, and it can be used to find the global solution for large-scale problems with thousands of points. We compare the computational complexity of our approach with state-of-the-art methods on synthetic problems and apply it to a near-symmetrical problem which is of particular interest in computational biology.
• Abstract（参考訳）: 本稿では,低次元空間における2つの点の集合間のグロモフ・ワッセルシュタイン問題を解くための枠組みを提案する。 グロモフ=ワッサーシュタイン問題(Gromov-Wasserstein problem)は、ペア距離を極力保った2つの集合間の割当を求める最適輸送問題の一般化である。 これは、AIと機械学習における一般的な問題である2つの構成または形状の類似性を定量化するために使用できる。 この問題は二次割当問題 (QAP) として定式化できるが、これは小さな問題であっても一般に計算的に難解である。 本フレームワークは,QAPを低次元領域の最適化問題として再構成し,低階の凹凸2次最適化問題として表現できるという事実を活用することで,この問題に対処する。 この手法はポイント数によく適合しており、数千ポイントの大規模問題に対するグローバルソリューションを見つけるのに使うことができる。 提案手法の計算複雑性を,合成問題に関する最先端の手法と比較し,計算生物学に特に関心を持つ準対称問題に適用する。

関連論文リスト

• Scalable unsupervised alignment of general metric and non-metric structures [21.29255788365408]
  異なるドメインからのデータのアライメントは、非常に異なる領域にわたる幅広いアプリケーションによる機械学習の基本的な問題である。 我々は、2次代入問題 (QAP) の最小化問題でもある、関連よく計算可能な線形代入問題 (LAP) を学習する。 単一セルマルチオミクスとニューラル潜在空間からの合成および実データに対するアプローチを評価する。
  論文  参考訳（メタデータ） (2024-06-19T12:54:03Z)
• Sparse Partitioning Around Medoids [0.0]
  パーティショニング・アラウンド・メドイド (PAM, k-メドイド) は任意の距離関数や類似性を持つ一般的なクラスタリング手法である。 FastPAMは最近、大きな問題に適用できるように、大きな k の高速化を導入したが、このメソッドは N で実行時二次性を持つ。 本稿では,例えば道路網などのグラフデータにおいて,この問題のスパースかつ非対称な変種について論じる。
  論文  参考訳（メタデータ） (2023-09-05T19:52:24Z)
• Approximation of optimization problems with constraints through kernel Sum-Of-Squares [77.27820145069515]
  我々は、点的不等式が非負の kSoS 関数のクラス内で等式となることを示す。 また, 等式制約に焦点をあてることで, 散乱不等式を用いることで, 制約のサンプリングにおける次元性の呪いを軽減することができることを示す。
  論文  参考訳（メタデータ） (2023-01-16T10:30:04Z)
• Sparse Polynomial Optimization: Theory and Practice [5.27013884159732]
  本書は、この課題に重要な科学的意味を持って取り組むためのいくつかの取り組みを提示している。 これは計算複雑性の観点からうまくスケールする代替の最適化スキームを提供する。 制約のない問題や制約のない問題に対して、緩和の疎開的階層を提示する。
  論文  参考訳（メタデータ） (2022-08-23T18:56:05Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。 量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。 提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
  論文  参考訳（メタデータ） (2022-05-24T03:49:10Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。 本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。 Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
  論文  参考訳（メタデータ） (2021-05-06T17:59:38Z)
• A Riemannian Block Coordinate Descent Method for Computing the Projection Robust Wasserstein Distance [36.97843660480747]
  wasserstein距離は、機械学習とディープラーニングにおいてますます重要になっている。 最近提案された次元の呪いを和らげるためのアプローチは、サンプルデータを低次元の部分空間に投影し、それから投影されたデータ間のワッサーシュタイン距離を計算することである。 しかし、このアプローチは、実際には非常に難しいStiefel多様体上の最大分問題を解決する必要があります。 本研究では,Stiefel多様体上の正規化最大ミン問題の新たな再構成に基づく,この問題を解くための新しいブロック座標降下法(RBCD)を提案する。
  論文  参考訳（メタデータ） (2020-12-09T17:47:56Z)
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic [142.1492359556374]
  双レベル最適化は、2レベル構造を示す問題のクラスである。 このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。 本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
  論文  参考訳（メタデータ） (2020-07-10T05:20:02Z)
• Aligning Partially Overlapping Point Sets: an Inner Approximation Algorithm [80.15123031136564]
  変換の値に関する事前情報がない点集合を整列するロバストな手法を提案する。 我々のアルゴリズムは変換の正規化を必要とせず、変換の値に関する事前情報がない状況に対処できる。 実験により,提案手法が最先端のアルゴリズムよりも高いロバスト性を示した。
  論文  参考訳（メタデータ） (2020-07-05T15:23:33Z)
• Efficient and Robust Shape Correspondence via Sparsity-Enforced Quadratic Assignment [16.03666555216332]
  そこで我々は,新しい局所的なペアワイズ記述子を導入し,その結果の2次代入を解くための,シンプルで効果的な反復法を開発した。 我々のペアワイズ記述子は、ラプラス・ベルトラミ微分作用素の有限要素近似の剛性と質量反復行列に基づいている。 我々は,大規模データセット,パッチ,ポイントクラウド上での手法の効率性,品質,汎用性を示すために,様々な実験を行った。
  論文  参考訳（メタデータ） (2020-03-19T10:56:16Z)
• Fast and Robust Comparison of Probability Measures in Heterogeneous Spaces [62.35667646858558]
  本稿では, アンカー・エナジー (AE) とアンカー・ワッサースタイン (AW) 距離を紹介する。 我々の主な貢献は、素案実装が立方体となる対数四重項時間でAEを正確に計算するスイープラインアルゴリズムを提案することである。 AE と AW は,一般的な GW 近似の計算コストのごく一部において,様々な実験環境において良好に動作することを示す。
  論文  参考訳（メタデータ） (2020-02-05T03:09:23Z)

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

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