論文の概要: A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization

• arxiv url: http://arxiv.org/abs/2112.13199v1
• Date: Sat, 25 Dec 2021 07:38:14 GMT
• ステータス: 処理完了
• システム内更新日: 2021-12-29 08:29:00.249830
• Title: A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization
• Title（参考訳）: 共同コミュニティ検出と直交群同期のためのスペクトル法
• Authors: Yifeng Fan, Yuehaw Khoo, and Zhizhen Zhao
• Abstract要約: 我々は、スペクトル分解ステップとブロックワイドカラムピボットQR因子分解(CPQR)からなる単純なアルゴリズムを提案する。 提案アルゴリズムは効率的で,データ点数に応じて線形にスケールする。 また、最近開発されたLeft-one-out技術を利用して、クラスタメンバシップの正確なリカバリをほぼ最適に保証する。
• 参考スコア（独自算出の注目度）: 20.413250472034143
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Community detection and orthogonal group synchronization are both fundamental problems with a variety of important applications in science and engineering. In this work, we consider the joint problem of community detection and orthogonal group synchronization which aims to recover the communities and perform synchronization simultaneously. To this end, we propose a simple algorithm that consists of a spectral decomposition step followed by a blockwise column pivoted QR factorization (CPQR). The proposed algorithm is efficient and scales linearly with the number of data points. We also leverage the recently developed `leave-one-out' technique to establish a near-optimal guarantee for exact recovery of the cluster memberships and stable recovery of the orthogonal transforms. Numerical experiments demonstrate the efficiency and efficacy of our algorithm and confirm our theoretical characterization of it.
• Abstract（参考訳）: コミュニティ検出と直交群同期はどちらも科学と工学における様々な重要な応用の基本的な問題である。 本研究では,コミュニティを回復し,同時に同期することを目的とした,コミュニティ検出と直交グループ同期の連立問題を考察する。 この目的のために、スペクトル分解ステップとブロックワイドカラムピボットQR因子分解(CPQR)からなる単純なアルゴリズムを提案する。 提案アルゴリズムは効率的で,データ点数に応じて線形にスケールする。 また,最近開発された「リーブ・ワン・アウト」手法を利用して,クラスターメンバシップの完全回復と直交変換の安定回復の至近保証を確立する。 数値実験により,本アルゴリズムの効率と有効性を示し,その理論的特徴を検証した。

関連論文リスト

• ALEXR: An Optimal Single-Loop Algorithm for Convex Finite-Sum Coupled Compositional Stochastic Optimization [53.14532968909759]
  ALEXRと呼ばれる,効率的な単ループプリマルデュアルブロックコーディネートアルゴリズムを提案する。 本研究では, ALEXR の凸面および強凸面の収束速度を滑らか性および非滑らか性条件下で確立する。 本稿では,ALEXRの収束速度が,検討されたcFCCO問題に対する1次ブロック座標アルゴリズムの中で最適であることを示すために,より低い複雑性境界を示す。
  論文  参考訳（メタデータ） (2023-12-04T19:00:07Z)
• An Optimization-based Deep Equilibrium Model for Hyperspectral Image Deconvolution with Convergence Guarantees [71.57324258813675]
  本稿では,ハイパースペクトル画像のデコンボリューション問題に対処する新しい手法を提案する。 新しい最適化問題を定式化し、学習可能な正規化器をニューラルネットワークの形で活用する。 導出した反復解法は、Deep Equilibriumフレームワーク内の不動点計算問題として表現される。
  論文  参考訳（メタデータ） (2023-06-10T08:25:16Z)
• Unrolled algorithms for group synchronization [7.969977930633441]
  群同期問題は、そのペア比のノイズ測定から群要素の集合を推定することを含む。 群要素を推定する標準的な方法は、線形および非線形作用素を反復的に適用することに基づいている。 深層ニューラルネットワークと構造的類似性により、我々はアルゴリズムのアンロールの概念を採用した。
  論文  参考訳（メタデータ） (2022-07-19T17:25:56Z)
• Multi-Frequency Joint Community Detection and Phase Synchronization [22.683901672480353]
  本稿では, 相対位相をもつテクスト確率ブロックモデルにおける共同コミュニティ検出と位相同期問題について検討する。 本稿では,その最大推定値(MLE)の定式化を精査し,テキストマルチ周波数構造を示す。 MLEの定式化を利用して、複数の周波数にまたがる情報から得られる2つの単純かつ効率的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-06-16T23:08:27Z)
• Perfect Spectral Clustering with Discrete Covariates [68.8204255655161]
  本稿では,大規模なスパースネットワークのクラスにおいて,高い確率で完全クラスタリングを実現するスペクトルアルゴリズムを提案する。 本手法は,スペクトルクラスタリングによる一貫した潜在構造回復を保証する最初の方法である。
  論文  参考訳（メタデータ） (2022-05-17T01:41:06Z)
• First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems [88.58409977434269]
  非線形一般化ナッシュ均衡問題(NGNEP)における平衡計算の問題を考える。 我々の貢献は、2次ペナルティ法と拡張ラグランジアン法に基づく2つの単純な一階アルゴリズムフレームワークを提供することである。 これらのアルゴリズムに対する漸近的理論的保証を提供する。
  論文  参考訳（メタデータ） (2022-04-07T00:11:05Z)
• Gradient Based Clustering [72.15857783681658]
  本稿では,クラスタリングの品質を計測するコスト関数の勾配を用いて,距離に基づくクラスタリングの一般的な手法を提案する。 アプローチは反復的な2段階の手順(クラスタ割り当てとクラスタセンターのアップデートの代替)であり、幅広い機能に適用できる。
  論文  参考訳（メタデータ） (2022-02-01T19:31:15Z)
• Joint Community Detection and Rotational Synchronization via Semidefinite Programming [17.845257705485533]
  ランダムに回転したオブジェクトを複数の下位カテゴリに分類する異種データが存在する場合、それらをクラスタに分類し、ペア関係に基づいて同期させることは困難である。 本稿では, 半定値緩和を連続的に提案し, お祝いブロックモデルをこの新しい設定に拡張する際の正確な回復を実証する。 数値実験により,提案アルゴリズムの有効性を実証し,正確な回復のための急激な相転移を示す理論的結果を確認する。
  論文  参考訳（メタデータ） (2021-05-13T01:40:20Z)
• Near-Optimal Performance Bounds for Orthogonal and Permutation Group Synchronization via Spectral Methods [0.7614628596146599]
  グループ同期は、それぞれの測定値からグループ要素を復元することを要求する。 スペクトル法は 効率と利便性で 大人気でした ランダムな乱れの下での置換群同期では、広く使われている2段階の手順がすべての群要素を正確に復元できることが示される。
  論文  参考訳（メタデータ） (2020-08-12T14:20:16Z)
• Message Passing Least Squares Framework and its Application to Rotation Synchronization [16.650654530240566]
  まず,測定されたグループ比の劣化レベルを推定する理論的に保証されたメッセージパッシングアルゴリズムについて述べる。 次に, グループ要素を推定する新たな最小二乗法を提案し, そこでは, 推定汚職レベルを用いて重みを反復的に更新する。 合成データと実データの両方を用いた回転同期の最先端手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2020-07-27T15:39:19Z)
• IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method [64.15649345392822]
  本稿では,局所関数が滑らかで凸な分散最適化環境下での原始的手法設計のためのフレームワークを提案する。 提案手法は,加速ラグランジアン法により誘導されるサブプロブレム列を概ね解いたものである。 加速度勾配降下と組み合わせることで,収束速度が最適で,最近導出された下界と一致した新しい原始アルゴリズムが得られる。
  論文  参考訳（メタデータ） (2020-06-11T18:49:06Z)

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

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