論文の概要: Near-Optimal Performance Bounds for Orthogonal and Permutation Group
Synchronization via Spectral Methods
- arxiv url: http://arxiv.org/abs/2008.05341v3
- Date: Tue, 22 Feb 2022 12:05:55 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-31 06:09:02.959587
- Title: Near-Optimal Performance Bounds for Orthogonal and Permutation Group
Synchronization via Spectral Methods
- Title（参考訳）: スペクトル法による直交群と置換群同期の近似最適性能境界
- Authors: Shuyang Ling
- Abstract要約: グループ同期は、それぞれの測定値からグループ要素を復元することを要求する。
スペクトル法は 効率と利便性で 大人気でした
ランダムな乱れの下での置換群同期では、広く使われている2段階の手順がすべての群要素を正確に復元できることが示される。
- 参考スコア（独自算出の注目度）: 0.7614628596146599
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Group synchronization asks to recover group elements from their pairwise
measurements. It has found numerous applications across various scientific
disciplines. In this work, we focus on orthogonal and permutation group
synchronization which are widely used in computer vision such as object
matching and structure from motion. Among many available approaches, the
spectral methods have enjoyed great popularity due to their efficiency and
convenience. We will study the performance guarantees of the spectral methods
in solving these two synchronization problems by investigating how well the
computed eigenvectors approximate each group element individually. We establish
our theory by applying the recent popular~\emph{leave-one-out} technique and
derive a~\emph{block-wise} performance bound for the recovery of each group
element via eigenvectors. In particular, for orthogonal group synchronization,
we obtain a near-optimal performance bound for the group recovery in presence
of additive Gaussian noise. For permutation group synchronization under random
corruption, we show that the widely-used two-step procedure (spectral method
plus rounding) can recover all the group elements exactly if the SNR
(signal-to-noise ratio) is close to the information theoretical limit. Our
numerical experiments confirm our theory and indicate a sharp phase transition
for the exact group recovery.
- Abstract（参考訳）: グループ同期は、それぞれの測定値からグループ要素を復元することを要求する。
様々な科学分野に応用されている。
本研究では,物体マッチングや動き構造などのコンピュータビジョンにおいて広く用いられている直交群と置換群同期に着目した。
多くの利用可能なアプローチの中で、スペクトル法はその効率性と利便性から非常に人気がある。
本稿では,これら2つの同期問題に対するスペクトル法の性能保証を,計算固有ベクトルが各群要素をいかに個々に近似しているかを調べることにより検討する。
我々は,最近普及した~\emph{leave-one-out} の手法を適用し,固有ベクトルによる各群要素の回復に対する a~\emph{block-wise} のパフォーマンスを導出することによって,理論を確立する。
特に直交群同期について,加法ガウス雑音の存在下での群回復に最適に近い性能が得られる。
ランダムな腐敗下での置換群同期について,snr (signal-to-noise ratio) が情報理論上の限界に近い場合に,広く用いられている2段階法 (spectral method plus rounding) がすべての群要素を正しく回収できることを示す。
数値実験により,本理論を検証し,厳密な群回復のための鋭い相転移を示す。
関連論文リスト
- Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and
Optimal Algorithms [64.10576998630981]
最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。
ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。
本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
論文 参考訳（メタデータ） (2023-06-21T17:03:22Z) - Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。
本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
論文 参考訳（メタデータ） (2023-06-18T08:46:06Z) - Unrolled algorithms for group synchronization [7.969977930633441]
群同期問題は、そのペア比のノイズ測定から群要素の集合を推定することを含む。
群要素を推定する標準的な方法は、線形および非線形作用素を反復的に適用することに基づいている。
深層ニューラルネットワークと構造的類似性により、我々はアルゴリズムのアンロールの概念を採用した。
論文 参考訳（メタデータ） (2022-07-19T17:25:56Z) - Perfect Spectral Clustering with Discrete Covariates [68.8204255655161]
本稿では,大規模なスパースネットワークのクラスにおいて,高い確率で完全クラスタリングを実現するスペクトルアルゴリズムを提案する。
本手法は,スペクトルクラスタリングによる一貫した潜在構造回復を保証する最初の方法である。
論文 参考訳（メタデータ） (2022-05-17T01:41:06Z) - Optimal Clustering with Bandit Feedback [57.672609011609886]
本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。
これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。
合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
論文 参考訳（メタデータ） (2022-02-09T06:05:05Z) - A Spectral Method for Joint Community Detection and Orthogonal Group
Synchronization [20.413250472034143]
我々は、スペクトル分解ステップとブロックワイドカラムピボットQR因子分解(CPQR)からなる単純なアルゴリズムを提案する。
提案アルゴリズムは効率的で,データ点数に応じて線形にスケールする。
また、最近開発されたLeft-one-out技術を利用して、クラスタメンバシップの正確なリカバリをほぼ最適に保証する。
論文 参考訳（メタデータ） (2021-12-25T07:38:14Z) - Orthogonal Group Synchronization with Incomplete Measurements: Error
Bounds and Linear Convergence of the Generalized Power Method [22.901235010786287]
群同期とは、雑音の対の測度から群要素の集合を推定することを指す。
本稿では,不完全な測定条件下での一般付加音モデルを用いたグループ同期問題に焦点をあてる。
論文 参考訳（メタデータ） (2021-12-13T10:57:09Z) - Sparse Quadratic Optimisation over the Stiefel Manifold with Application
to Permutation Synchronisation [71.27989298860481]
二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。
そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-30T19:17:35Z) - Joint Community Detection and Rotational Synchronization via
Semidefinite Programming [17.845257705485533]
ランダムに回転したオブジェクトを複数の下位カテゴリに分類する異種データが存在する場合、それらをクラスタに分類し、ペア関係に基づいて同期させることは困難である。
本稿では, 半定値緩和を連続的に提案し, お祝いブロックモデルをこの新しい設定に拡張する際の正確な回復を実証する。
数値実験により,提案アルゴリズムの有効性を実証し,正確な回復のための急激な相転移を示す理論的結果を確認する。
論文 参考訳（メタデータ） (2021-05-13T01:40:20Z) - A Practical Method for Constructing Equivariant Multilayer Perceptrons
for Arbitrary Matrix Groups [115.58550697886987]
行列群の同変層を解くための完全一般的なアルゴリズムを提供する。
他作品からのソリューションを特殊ケースとして回収するだけでなく、これまで取り組んだことのない複数のグループと等価な多層パーセプトロンを構築します。
提案手法は, 粒子物理学および力学系への応用により, 非同変基底線より優れる。
論文 参考訳（メタデータ） (2021-04-19T17:21:54Z) - A Unified Approach to Synchronization Problems over Subgroups of the
Orthogonal Group [29.714239628405515]
群が閉部分群である同期問題のクラスを考える。
このような問題を解くための統一的なアプローチを提案する。
私たちのアプローチは既存のアプローチよりも優れています。
論文 参考訳（メタデータ） (2020-09-16T07:25:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。