論文の概要: 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$の繰り返し使用による既存のメソッドの重大な制限を克服し、数値性能の向上につながる。
提案手法の最適性を確立するために,細粒度スペクトル解析を行い,極大率に一致する鋭い指数関数的誤差境界を求める。
関連論文リスト
- A Novel Normalized-Cut Solver with Nearest Neighbor Hierarchical
Initialization [107.07093621337084]
正規化カット(N-Cut)は、スペクトルクラスタリングの有名なモデルである。
1)正規化ラプラシア行列の連続スペクトル埋め込みを計算する; 2)$K$-meansまたはスペクトル回転による離散化。
有名な座標降下法に基づく新しいN-Cut解法を提案する。
論文 参考訳(メタデータ) (2023-11-26T07:11:58Z) - 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) - 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) - Statistical Inference of Constrained Stochastic Optimization via
Sketched Sequential Quadratic Programming [59.36379287247961]
この問題を解決するために,完全オンライン逐次2次プログラミング(StoSQP)手法を開発した。
最近の数値二階法の設計により、StoSQPは任意のランダムなステップサイズを適応的に選択できる。
また,2次法の計算コストを大幅に削減するため,StoSQPはランダム化反復解法を用いて2次プログラムを不正確に解けるようにした。
論文 参考訳(メタデータ) (2022-05-27T00:34:03Z) - Halpern-Type Accelerated and Splitting Algorithms For Monotone
Inclusions [14.445131747570962]
我々は、最大単調方程式のクラスを解くために、新しいタイプの加速アルゴリズムを開発する。
我々の手法は[32]におけるハルパーン型固定点反復と呼ばれるものに依存しており、近年多くの研究者が利用している。
論文 参考訳(メタデータ) (2021-10-15T15:26:32Z) - Sparse Quadratic Optimisation over the Stiefel Manifold with Application
to Permutation Synchronisation [71.27989298860481]
二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。
そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-09-30T19:17:35Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳(メタデータ) (2021-06-16T03:34:14Z) - Learning Sparse Classifiers: Continuous and Mixed Integer Optimization
Perspectives [10.291482850329892]
混合整数計画法(MIP)は、(最適に) $ell_0$-正規化回帰問題を解くために用いられる。
数分で5万ドルの機能を処理できる正確なアルゴリズムと、$papprox6$でインスタンスに対処できる近似アルゴリズムの2つのクラスを提案する。
さらに,$ell$-regularizedsに対する新しい推定誤差境界を提案する。
論文 参考訳(メタデータ) (2020-01-17T18:47:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。