論文の概要: A Novel and Optimal Spectral Method for Permutation Synchronization
- arxiv url: http://arxiv.org/abs/2303.12051v1
- Date: Tue, 21 Mar 2023 17:43:26 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-22 13:53:26.240587
- Title: A Novel and Optimal Spectral Method for Permutation Synchronization
- Title（参考訳）: 置換同期のための新しい最適スペクトル法
- Authors: Duc Nguyen, Anderson Ye Zhang
- Abstract要約: 置換同期はコンピュータ科学において重要な問題であり、多くのコンピュータビジョンタスクの重要なステップを構成する。
目標は、雑音と不完全なペアワイズ測定から$n$潜在置換を回復することである。
スペクトル法は、データ行列の先頭の固有空間$U$とそのブロックサブマトリクス$U_1,U,ldots,U_n$を利用して、置換を回復する。
- 参考スコア（独自算出の注目度）: 1.14219428942199
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Permutation synchronization is an important problem in computer science that
constitutes the key step of many computer vision tasks. The goal is to recover
$n$ latent permutations from their noisy and incomplete pairwise measurements.
In recent years, spectral methods have gained increasing popularity thanks to
their simplicity and computational efficiency. Spectral methods utilize the
leading eigenspace $U$ of the data matrix and its block submatrices
$U_1,U_2,\ldots, U_n$ to recover the permutations. In this paper, we propose a
novel and statistically optimal spectral algorithm. Unlike the existing methods
which use $\{U_jU_1^\top\}_{j\geq 2}$, ours constructs an anchor matrix $M$ by
aggregating useful information from all the block submatrices and estimates the
latent permutations through $\{U_jM^\top\}_{j\geq 1}$. This modification
overcomes a crucial limitation of the existing methods caused by the repetitive
use of $U_1$ and leads to an improved numerical performance. To establish the
optimality of the proposed method, we carry out a fine-grained spectral
analysis and obtain a sharp exponential error bound that matches the minimax
rate.
- Abstract（参考訳）: 順列同期はコンピュータ科学において重要な問題であり、多くのコンピュータビジョンタスクの重要なステップを構成する。
目標は、雑音と不完全なペアワイズ測定から$n$潜在置換を回復することである。
近年、スペクトル法は、その単純さと計算効率により人気が高まっている。
スペクトル法はデータ行列の先頭固有空間 $u$ とブロック部分行列 $u_1,u_2,\ldots,u_n$ を用いて置換を回復する。
本稿では,新しい,統計的に最適なスペクトルアルゴリズムを提案する。
u_ju_1^\top\}_{j\geq 2}$を使用する既存の方法とは異なり、我々はすべてのブロック部分行列から有用な情報を集約してアンカー行列 $m$を作成し、$\{u_jm^\top\}_{j\geq 1}$で潜在置換を推定する。
この修正は、$u_1$の繰り返し使用による既存のメソッドの重大な制限を克服し、数値性能の向上につながる。
提案手法の最適性を確立するために,細粒度スペクトル解析を行い,極大率に一致する鋭い指数関数的誤差境界を求める。
関連論文リスト
- QWO: Speeding Up Permutation-Based Causal Discovery in LiGAMs [20.661343069864888]
QWO は与えられた置換に対して$mathcalGpi$ の計算効率を大幅に向上させる新しい手法である。
QWOは、最先端のBICベースの手法と比較して、$O(n2)$$$(n$は変数の数)のスピードアップがあり、非常にスケーラブルである。
論文 参考訳（メタデータ） (2024-10-30T16:10:46Z) - Optimal level set estimation for non-parametric tournament and crowdsourcing problems [49.75262185577198]
クラウドソーシングによって動機づけられた我々は、$d$の質問に対する$n$の専門家の回答の正しさを部分的に観察する問題を考える。
本稿では、専門家$i$が疑問に答える確率を含む行列$M$が、行と列の置換までの双等方性であることを仮定する。
我々は,この分類問題に対して最小限のアルゴリズムを最適に構築する。
論文 参考訳（メタデータ） (2024-08-27T18:28:31Z) - Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems [9.30306458153248]
我々は、スペクトルテール条件数である$kappa_ell$を、システムを表す行列の最小特異値と$ell$2の比として定義する。
結果のいくつかの意味と$kappa_ell$の使用は、Conjugateメソッドのきめ細かい解析を直接改善することを含んでいる。
論文 参考訳（メタデータ） (2024-05-09T14:56:49Z) - Extra-Newton: A First Approach to Noise-Adaptive Accelerated
Second-Order Methods [57.050204432302195]
本研究では,2次スムーズな凸関数を最小化するための普遍的かつ適応的な2次法を提案する。
我々のアルゴリズムは、オラクルフィードバックが分散$sigma2$であるときに$O(sigma / sqrtT)$収束を達成し、決定論的オラクルで$O(1 / T3)$に収束を改善する。
論文 参考訳（メタデータ） (2022-11-03T14:12:51Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。
提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
論文 参考訳（メタデータ） (2022-10-23T21:24:37Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - Majorization-minimization for Sparse Nonnegative Matrix Factorization
with the $\beta$-divergence [2.3787352248749376]
他の因子(辞書行列)のノルムは不正な定式化を避けるために制御する必要があることはよく知られている。
標準のプラクティスは、辞書の列に単位ノルムを持つよう制約することであり、これは非自明な最適化問題につながる。
我々は,$ell_1$-regularization あるいはより "攻撃的" なログ規則化に対して,単純な乗法的更新をもたらすブロック・ディフレッシブ・プライマリゼーション・最小化アルゴリズムを導出する。
論文 参考訳（メタデータ） (2022-07-13T16:09:29Z) - Sparse Quadratic Optimisation over the Stiefel Manifold with Application
to Permutation Synchronisation [71.27989298860481]
二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。
そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-30T19:17:35Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。