論文の概要: Aligning Embeddings and Geometric Random Graphs: Informational Results and Computational Approaches for the Procrustes-Wasserstein Problem

• arxiv url: http://arxiv.org/abs/2405.14532v1
• Date: Thu, 23 May 2024 13:18:51 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-24 15:05:17.842984
• Title: Aligning Embeddings and Geometric Random Graphs: Informational Results and Computational Approaches for the Procrustes-Wasserstein Problem
• Title（参考訳）: 埋め込みと幾何学的ランダムグラフの整合性:Procrustes-Wasserstein問題に対する情報結果と計算的アプローチ
• Authors: Mathieu Even, Luca Ganassali, Jakob Maier, Laurent Massoulié,
• Abstract要約: Procrustes-Wstein問題(英語版)は、2つの高次元の点雲を教師なしの設定でマッチングするものである。 2つのデータセットが$X,Y$で、$mathbbRd$の$n$データポイントで構成されています。 そこで我々は,フランク=ウルフ凸緩和法を用いて,変換とレバーベリングを代替的に推定するPing-Passerongアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 12.629532305482423
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Procrustes-Wasserstein problem consists in matching two high-dimensional point clouds in an unsupervised setting, and has many applications in natural language processing and computer vision. We consider a planted model with two datasets $X,Y$ that consist of $n$ datapoints in $\mathbb{R}^d$, where $Y$ is a noisy version of $X$, up to an orthogonal transformation and a relabeling of the data points. This setting is related to the graph alignment problem in geometric models. In this work, we focus on the euclidean transport cost between the point clouds as a measure of performance for the alignment. We first establish information-theoretic results, in the high ($d \gg \log n$) and low ($d \ll \log n$) dimensional regimes. We then study computational aspects and propose the Ping-Pong algorithm, alternatively estimating the orthogonal transformation and the relabeling, initialized via a Franke-Wolfe convex relaxation. We give sufficient conditions for the method to retrieve the planted signal after one single step. We provide experimental results to compare the proposed approach with the state-of-the-art method of Grave et al. (2019).
• Abstract（参考訳）: Procrustes-Wasserstein問題(英語版)は、2つの高次元の点雲を教師なしの設定でマッチングすることであり、自然言語処理とコンピュータビジョンに多くの応用がある。 2つのデータセットが$X,Y$で、$n$のデータポイントが$\mathbb{R}^d$で、$Y$は$X$のノイズバージョンである。 この設定は幾何学モデルにおけるグラフアライメント問題と関連している。 本研究では,アライメント性能の指標として,点雲間のユークリッド輸送コストに着目した。 まず,高(d \gg \log n$)次元と低(d \ll \log n$)次元のレジームで情報理論結果を確立する。 次に計算面を研究し、代わりに直交変換と退化を推定するPing-Pongアルゴリズムを提案し、Franke-Wolfe convex relaxationを通じて初期化する。 本手法は,1ステップの後に植え付け信号を取得するのに十分な条件を与える。 提案手法とGrave et al (2019)の最先端手法との比較実験を行った。

関連論文リスト

• Information-Theoretic Thresholds for Planted Dense Cycles [52.076657911275525]
  本研究では,社会科学や生物科学においてユビキタスな小世界ネットワークのランダムグラフモデルについて検討する。 植え込み高密度サイクルの検出と回復の両面において、情報理論の閾値を$n$, $tau$、エッジワイド信号対雑音比$lambda$で特徴づける。
  論文  参考訳（メタデータ） (2024-02-01T03:39:01Z)
• Registration of algebraic varieties using Riemannian optimization [0.0]
  我々は、同じ物体を表すが、異なる座標系で表される2点雲間の変換を求める問題を考察する。 我々のアプローチは、ポイント・ツー・ポイント対応に基づいておらず、ソース・ポイント・クラウドのすべてのポイントとターゲット・ポイント・クラウドのポイントとを一致させる。
  論文  参考訳（メタデータ） (2024-01-16T18:47:38Z)
• Sparse Gaussian Graphical Models with Discrete Optimization: Computational and Statistical Perspectives [8.403841349300103]
  本研究では,無向ガウス図形モデルに基づくスパースグラフの学習問題を考察する。 擬似微分関数の $ell_0$-penalized バージョンに基づく新しい推定器 GraphL0BnB を提案する。 実/合成データセットに関する数値実験により,本手法がほぼ最適に,p = 104$の問題を解けることが示唆された。
  論文  参考訳（メタデータ） (2023-07-18T15:49:02Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。 注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。 本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
  期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。 低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
  論文  参考訳（メタデータ） (2023-02-13T22:51:07Z)
• Planted Bipartite Graph Detection [13.95780443241133]
  ランダムグラフに隠れた二部グラフを検出するタスクについて検討する。 ヌル仮説の下では、このグラフは、エッジ密度$q$の$n$上のアードホスラーイランダムグラフの実現である。 k_mathsfR times k_mathsfL$ bipartite subgraph with edge density $p>q$。
  論文  参考訳（メタデータ） (2023-02-07T18:18:17Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
  凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。 主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
  論文  参考訳（メタデータ） (2021-10-28T14:19:30Z)
• Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov Random Fields [51.07460861448716]
  本稿では,データから学ぶための凸解析フレームワークを提案する。 三角凸分解はその上部に対応する変換によって保証されることを示す。
  論文  参考訳（メタデータ） (2021-09-17T17:46:12Z)
• $\ell_2$-norm Flow Diffusion in Near-Linear Time [18.263667346853698]
  我々は$ell$-normフロー拡散問題に対して$widetildeO(m)$-timeランダム化アルゴリズムを提供する。 これは単純に双対解ベクトルを網羅することによって実現される。 Laplacianシステムソルバの高レベルなアルゴリズムフレームワークに適応するが、いくつかの新しいツールが必要である。
  論文  参考訳（メタデータ） (2021-05-30T21:27:58Z)

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

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