Fugu-MT 論文翻訳(概要): A polynomial time iterative algorithm for matching Gaussian matrices with non-vanishing correlation

論文の概要: A polynomial time iterative algorithm for matching Gaussian matrices with non-vanishing correlation

arxiv url: http://arxiv.org/abs/2212.13677v1
Date: Wed, 28 Dec 2022 03:30:47 GMT
ステータス: 処理完了
システム内更新日: 2022-12-29 16:13:51.264293
Title: A polynomial time iterative algorithm for matching Gaussian matrices with non-vanishing correlation
Title（参考訳）: ガウス行列と非有界相関をマッチングする多項式時間反復アルゴリズム
Authors: Jian Ding, Zhangsong Li
Abstract要約: 本稿では, 2つのガウス行列間の相関が消えない限り, 繰り返しマッチングアルゴリズムを提案する。その結果、相関が任意に小さいとき、グラフマッチングタイプの問題を解く最初のアルゴリズムとなる。
参考スコア（独自算出の注目度）: 7.343886246061388
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Motivated by the problem of matching vertices in two correlated Erd\H{o}s-R\'enyi graphs, we study the problem of matching two correlated Gaussian Wigner matrices. We propose an iterative matching algorithm, which succeeds in polynomial time as long as the correlation between the two Gaussian matrices does not vanish. Our result is the first polynomial time algorithm that solves a graph matching type of problem when the correlation is an arbitrarily small constant.
Abstract（参考訳）: 2つの相関 erd\h{o}s-r\'enyi グラフにおけるマッチング頂点の問題に動機づけられ、2つの相関ガウスウィグナー行列をマッチングする問題の研究を行った。 2つのガウス行列間の相関が消滅しない限り多項式時間で成功する反復マッチングアルゴリズムを提案する。その結果、相関が任意に小さいとき、グラフマッチングタイプの問題を解く最初の多項式時間アルゴリズムが得られた。

関連論文リスト

An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
論文参考訳（メタデータ） (2023-09-30T15:57:14Z)
On Sinkhorn's Algorithm and Choice Modeling [6.43826005042477]
その結果, 最大推定問題は, 古典的行列バランス問題と, 対象列と列の和との等価性を示す。この視点は、一見無関係な2つの研究領域の間の扉を開く。これらの接続からインスピレーションを得て、シンクホーンのアルゴリズムの研究において重要なオープンな問題を解く。
論文参考訳（メタデータ） (2023-09-30T05:20:23Z)
A polynomial-time iterative algorithm for random graph matching with non-vanishing correlation [12.869436542291144]
本稿では,2つの相関した ErdHos--R'enyi グラフと,エッジが潜時対応によって相関している$n$ とをマッチングする効率的なアルゴリズムを提案する。我々のアルゴリズムは実行時間を持ち、エッジの相関が無くなる限り、潜時マッチングを回復することに成功した。
論文参考訳（メタデータ） (2023-06-01T00:58:50Z)
Efficient Algorithms for Exact Graph Matching on Correlated Stochastic Block Models with Constant Correlation [7.914348940034351]
本稿では,グラフとコミュニティ構造をマッチングする効率的なアルゴリズムを提案する。我々のアルゴリズムは2つの相関ブロックモデル間の正確なマッチングを実現する最初の低次時間アルゴリズムである。
論文参考訳（メタデータ） (2023-05-31T09:06:50Z)
Kernelized multi-graph matching [0.0]
本稿では,グラフの属性とエッジの両方を扱う,新しいカーネル化されたマルチグラフマッチング手法を提案する。結果の安定性の向上につながるプロジェクタをいくつか提案する。
論文参考訳（メタデータ） (2022-10-11T07:22:47Z)
Graph Learning from Multivariate Dependent Time Series via a Multi-Attribute Formulation [12.843340232167266]
定常時系列の条件独立グラフ(CIG)を推定する問題を考察する。時系列グラフでは、ベクトル列の各成分は異なるノードで表され、コンポーネント間の関連は対応するノード間のエッジで表される。ベクトルがグラフの各ノードに関連付けられているランダムベクトルに対するマルチ属性グラフ推定の1つとして問題を定式化する。
論文参考訳（メタデータ） (2022-04-29T00:17:52Z)
High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
共分散行列の明示的な構成を避ける新しい推論手法を提案する。本手法では, 数値線形代数と共役勾配アルゴリズムの対角線推定結果とを結合する。いくつかのシミュレーションにおいて,本手法は計算時間とメモリにおける既存手法よりも拡張性が高い。
論文参考訳（メタデータ） (2022-02-25T16:35:26Z)
Sublinear Time Approximation of Text Similarity Matrices [50.73398637380375]
一般的なNystr"om法を不確定な設定に一般化する。我々のアルゴリズムは任意の類似性行列に適用でき、行列のサイズでサブ線形時間で実行される。本手法は,CUR分解の単純な変種とともに,様々な類似性行列の近似において非常によく機能することを示す。
論文参考訳（メタデータ） (2021-12-17T17:04:34Z)
Linear Bandit Algorithms with Sublinear Time Complexity [67.21046514005029]
既存の線形バンディットアルゴリズムを高速化し,arms $k$ でステップ毎の複雑性サブリニアを実現する。提案するアルゴリズムは、いくつかの$alpha(t) > 0$ と $widetilde o(stt)$ regret に対して1ステップあたり$o(k1-alpha(t))$ の複雑さを達成することができる。
論文参考訳（メタデータ） (2021-03-03T22:42:15Z)
Robustly Learning Mixtures of $k$ Arbitrary Gaussians [47.40835932474677]
任意の固定された$k$に対して$k$任意のガウスの混合を$mathbbRd$で頑健に推定する問題に対して、一定数の任意の汚職が存在する場合の時間アルゴリズムを与える。本研究の主なツールは,2乗法に依拠する効率的な分節クラスタリングアルゴリズムと,Frobeniusノルムおよび低ランク項の誤りを許容する新しいテンソル分解アルゴリズムである。
論文参考訳（メタデータ） (2020-12-03T17:54:03Z)
Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
最小二乗問題に対する反復スケッチの性能について検討する。本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
論文参考訳（メタデータ） (2020-02-03T16:17:50Z)

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