論文の概要: Fast, Accurate and Memory-Efficient Partial Permutation Synchronization
- arxiv url: http://arxiv.org/abs/2203.16505v1
- Date: Wed, 30 Mar 2022 17:41:17 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-31 14:25:24.402869
- Title: Fast, Accurate and Memory-Efficient Partial Permutation Synchronization
- Title（参考訳）: 高速, 高精度, メモリ効率の良い部分置換同期
- Authors: Shaohan Li, Yunpeng Shi, Gilad Lerman
- Abstract要約: 観測された部分置換の劣化レベルを推定するための改良されたアルゴリズムCEMP-Partialを提案する。
敵対的腐敗の下では、付加的なノイズが無く、特定の仮定でCEMP-Partialは、破損した部分置換を正確に分類することができる。
提案手法の精度,高速化,メモリ効率を,合成データと実データの両方で実証する。
- 参考スコア（独自算出の注目度）: 15.813217907813778
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Previous partial permutation synchronization (PPS) algorithms, which are
commonly used for multi-object matching, often involve computation-intensive
and memory-demanding matrix operations. These operations become intractable for
large scale structure-from-motion datasets. For pure permutation
synchronization, the recent Cycle-Edge Message Passing (CEMP) framework
suggests a memory-efficient and fast solution. Here we overcome the restriction
of CEMP to compact groups and propose an improved algorithm, CEMP-Partial, for
estimating the corruption levels of the observed partial permutations. It
allows us to subsequently implement a nonconvex weighted projected power method
without the need of spectral initialization. The resulting new PPS algorithm,
MatchFAME (Fast, Accurate and Memory-Efficient Matching), only involves sparse
matrix operations, and thus enjoys lower time and space complexities in
comparison to previous PPS algorithms. We prove that under adversarial
corruption, though without additive noise and with certain assumptions,
CEMP-Partial is able to exactly classify corrupted and clean partial
permutations. We demonstrate the state-of-the-art accuracy, speed and memory
efficiency of our method on both synthetic and real datasets.
- Abstract（参考訳）: 従来の部分置換同期(PPS)アルゴリズムは、一般にマルチオブジェクトマッチングに使用されるが、計算集約およびメモリ要求行列演算を伴うことが多い。
これらの操作は、運動データセットから大規模構造を抽出できる。
純粋な置換同期のために、最近の cycle-edge message passing (cemp) フレームワークは、メモリ効率が高く高速なソリューションを提案している。
ここでは,コンパクト群に対するcempの制限を克服し,観測された部分置換の腐敗レベルを推定する改良アルゴリズムcemp-partialを提案する。
これにより、スペクトル初期化を必要とせずに非凸重み付き電力法を実装できる。
得られた新しいPSアルゴリズムであるMatchFAME(Fast, Accurate and Memory-Efficient Matching)は、疎行列演算のみを伴い、従来のPSアルゴリズムと比較して時間と空間の複雑さが低い。
敵対的腐敗の下では、付加的なノイズが無く、特定の仮定でCEMP-Partialは、破損した部分置換を正確に分類することができる。
提案手法の精度,高速化,メモリ効率を,合成データと実データの両方で実証する。
関連論文リスト
- Faster WIND: Accelerating Iterative Best-of-$N$ Distillation for LLM Alignment [81.84950252537618]
本稿では,反復的BONDと自己プレイアライメントの統一的なゲーム理論接続を明らかにする。
WINレート支配(WIN rate Dominance, WIND)という新しいフレームワークを構築し, 正規化利率支配最適化のためのアルゴリズムを多数提案する。
論文 参考訳（メタデータ） (2024-10-28T04:47:39Z) - Fast OMP for Exact Recovery and Sparse Approximation [4.915061940934031]
本論文は, オリゴナル・マッチング・パースーツ(OMP)を2つの面で前進させる。
各イテレーションで入力信号の投影を高速に行うアルゴリズムと、グリーディ選択のための新しい選択基準を提供する。
実験結果は計算時間において古典的なOMPよりも大幅に改善したことを示している。
論文 参考訳（メタデータ） (2024-03-29T20:39:37Z) - Fast, Scalable, Warm-Start Semidefinite Programming with Spectral
Bundling and Sketching [53.91395791840179]
我々は、大規模なSDPを解くための、証明可能な正確で高速でスケーラブルなアルゴリズムであるUnified Spectral Bundling with Sketching (USBS)を提案する。
USBSは、20億以上の決定変数を持つインスタンス上で、最先端のスケーラブルなSDP解決器よりも500倍のスピードアップを提供する。
論文 参考訳（メタデータ） (2023-12-19T02:27:22Z) - An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。
このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。
本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-09-30T15:57:14Z) - Asymmetric Scalable Cross-modal Hashing [51.309905690367835]
クロスモーダルハッシュは、大規模なマルチメディア検索問題を解決する方法として成功している。
これらの問題に対処する新しい非対称スケーラブルクロスモーダルハッシュ(ASCMH)を提案する。
我々のASCMHは、最先端のクロスモーダルハッシュ法よりも精度と効率の点で優れています。
論文 参考訳（メタデータ） (2022-07-26T04:38:47Z) - Discrete Morse Sandwich: Fast Computation of Persistence Diagrams for
Scalar Data -- An Algorithm and A Benchmark [8.648433479399857]
本稿では,d-次元単純複素数 K 上で定義される入力片方向線形スカラー場 f を与えられた永続図計算の効率的なアルゴリズムを提案する。
我々はこのアルゴリズムを離散モース理論の設定内で表現し、考慮すべき入力単純さの数を著しく削減する。
また、この問題に対して「サンドウィッチ」と呼ばれる階層化アプローチを導入する。
論文 参考訳（メタデータ） (2022-06-27T10:54:24Z) - Greedier is Better: Selecting Multiple Neighbors per Iteration for
Sparse Subspace Clustering [18.888312436971187]
本稿では,一般化OMP(GOMP)を用いた新しいSSC方式を提案する。
GOMPはイテレーションが少ないため、アルゴリズムの複雑さが低い。
提案した停止規則は,部分空間次元と雑音パワーのオフライン推定が不要である。
論文 参考訳（メタデータ） (2022-04-06T04:20:35Z) - Rethinking Space-Time Networks with Improved Memory Coverage for
Efficient Video Object Segmentation [68.45737688496654]
各オブジェクトのマスク特徴を再エンコードすることなく,フレーム間の直接対応性を確立する。
対応によって、現在のクエリフレーム内の全てのノードは、過去の特徴を連想的に集約することによって推測される。
すべてのメモリノードにコントリビュートする機会があることを検証し、そのような多彩な投票がメモリ効率と推論精度の両方に有益であることを示した。
論文 参考訳（メタデータ） (2021-06-09T16:50:57Z) - Exact, Parallelizable Dynamic Time Warping Alignment with Linear Memory [0.0]
我々は,O(M+N)メモリを用いて,正確な大域的最適DTWアライメントを計算する分割・征服アルゴリズムを提案する。
我々のアルゴリズムは、同じメモリ制約でmin(M, N)の係数まで並列化できるので、十分なGPUで教科書版よりも効率的に実行できる。
論文 参考訳（メタデータ） (2020-08-04T15:00:33Z) - Fast and Robust Iterative Closest Point [32.42799285301607]
イテレーティブ・クローズト・ポイント(ICP)は、2つの点集合間の剛性登録のための基本技術である。
Sparse ICPのような最近の研究は、計算速度を犠牲にしてスパース性最適化によって堅牢性を達成する。
本稿では,古典的な点対点ICPを最大化最小化(MM)アルゴリズムとして扱えることを示す。
論文 参考訳（メタデータ） (2020-07-15T11:32:53Z) - Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。
この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。
古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
論文 参考訳（メタデータ） (2020-07-01T18:43:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。