論文の概要: Efficient Detection of Long Consistent Cycles and its Application to Distributed Synchronization
- arxiv url: http://arxiv.org/abs/2407.04260v1
- Date: Fri, 5 Jul 2024 05:19:53 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-08 14:31:15.250462
- Title: Efficient Detection of Long Consistent Cycles and its Application to Distributed Synchronization
- Title（参考訳）: 長周期の効率的な検出と分散同期への応用
- Authors: Shaohan Li, Yunpeng Shi, Gilad Lerman,
- Abstract要約: グループ同期は、SfM(Structure from Motion)のグローバルパイプラインにおいて重要な役割を果たす
サイクル同期はこれらの課題に対処するのに有効である。
3から6までの長さの周期からの情報を活用するグループ同期アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 16.017134759593333
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Group synchronization plays a crucial role in global pipelines for Structure from Motion (SfM). Its formulation is nonconvex and it is faced with highly corrupted measurements. Cycle consistency has been effective in addressing these challenges. However, computationally efficient solutions are needed for cycles longer than three, especially in practical scenarios where 3-cycles are unavailable. To overcome this computational bottleneck, we propose an algorithm for group synchronization that leverages information from cycles of lengths ranging from three to six with a time complexity of order $O(n^3)$ (or $O(n^{2.373})$ when using a faster matrix multiplication algorithm). We establish non-trivial theory for this and related methods that achieves competitive sample complexity, assuming the uniform corruption model. To advocate the practical need for our method, we consider distributed group synchronization, which requires at least 4-cycles, and we illustrate state-of-the-art performance by our method in this context.
- Abstract（参考訳）: グループ同期は、Structure from Motion (SfM)のグローバルパイプラインにおいて重要な役割を果たす。
その定式化は非凸であり、高度に劣化した測定に直面している。
サイクル一貫性はこれらの課題に対処するのに有効です。
しかし、特に3サイクルが利用できない現実的なシナリオでは、3サイクルよりも長いサイクルで計算的に効率的な解が必要である。
この計算ボトルネックを克服するために,より高速な行列乗算アルゴリズムを使用する場合,3から6までの周期から,次数$O(n^3)$(または$O(n^{2.373})$)の時間的複雑さを持つ情報を利用するグループ同期アルゴリズムを提案する。
我々は、一様腐敗モデルを仮定して、競合するサンプルの複雑さを実現する、これと関連した手法について、非自明な理論を確立する。
提案手法の実践的ニーズを提起するために,少なくとも4サイクルの分散グループ同期を考察し,本手法による最先端性能について述べる。
関連論文リスト
- 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) - An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。
このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。
本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-09-30T15:57:14Z) - SYNTHESIS: A Semi-Asynchronous Path-Integrated Stochastic Gradient
Method for Distributed Learning in Computing Clusters [7.968142741470549]
ulstochastic gradulient ulsearchは、同期および非同期分散学習アルゴリズムの制限を克服するために開発された。
algnameアルゴリズムは(O(sqrtNepsilon-2(Delta+1) d+N))と(O(sqrtNepsilon-2(+1) d+N))を持つ
(エプシロン)分散共有メモリアーキテクチャにおける非デルタ学習の定常点
論文 参考訳（メタデータ） (2022-08-17T17:42:33Z) - Unrolled algorithms for group synchronization [7.969977930633441]
群同期問題は、そのペア比のノイズ測定から群要素の集合を推定することを含む。
群要素を推定する標準的な方法は、線形および非線形作用素を反復的に適用することに基づいている。
深層ニューラルネットワークと構造的類似性により、我々はアルゴリズムのアンロールの概念を採用した。
論文 参考訳（メタデータ） (2022-07-19T17:25:56Z) - 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) - Sketching as a Tool for Understanding and Accelerating Self-attention
for Long Sequences [52.6022911513076]
トランスフォーマーベースのモデルは、自己アテンションモジュールの二次空間と時間的複雑さのために、長いシーケンスを処理するのに効率的ではない。
我々はLinformerとInformerを提案し、低次元投影と行選択により2次複雑性を線形(モジュラー対数因子)に還元する。
理論的解析に基づいて,Skeinformerを提案することにより,自己注意の促進と,自己注意への行列近似の精度の向上を図ることができる。
論文 参考訳（メタデータ） (2021-12-10T06:58:05Z) - Learning Iterative Robust Transformation Synchronization [71.73273007900717]
グラフニューラルネットワーク(GNN)を用いて変換同期を学習することを提案する。
本研究では、ロバストな損失関数のハンドクラフトを回避するとともに、グラフニューラルネットワーク(GNN)を用いて変換同期を学習することを提案する。
論文 参考訳（メタデータ） (2021-11-01T07:03:14Z) - Asynchronous Advantage Actor Critic: Non-asymptotic Analysis and Linear
Speedup [56.27526702716774]
本稿では、A3CアルゴリズムをTD(0)で修正し、A3C-TD(0)と呼ばれ、証明可能な収束を保証する。
i.i.d.
サンプリング a3c-td(0) は、作業者あたり $mathcalo(epsilon-2.5/n)$ のサンプル複雑性を取得して $epsilon$ 精度を達成する。
2 に対して $mathcalO(epsilon-2.5/N)$ の最もよく知られたサンプル複雑性との比較
論文 参考訳（メタデータ） (2020-12-31T09:07:09Z) - Triclustering in Big Data Setting [2.752817022620644]
本稿では、MapReduceモデルや並列化機構を備えた分散環境での効率的な計算に適応したトリクラスタリングアルゴリズムのバージョンについて述べる。
OAC- family of triclustering algorithm shows good parallelization capabilities due by the independent processing of triples of a triadic formal context。
論文 参考訳（メタデータ） (2020-10-24T16:55:55Z) - Near-Optimal Performance Bounds for Orthogonal and Permutation Group
Synchronization via Spectral Methods [0.7614628596146599]
グループ同期は、それぞれの測定値からグループ要素を復元することを要求する。
スペクトル法は 効率と利便性で 大人気でした
ランダムな乱れの下での置換群同期では、広く使われている2段階の手順がすべての群要素を正確に復元できることが示される。
論文 参考訳（メタデータ） (2020-08-12T14:20:16Z) - Accelerating Feedforward Computation via Parallel Nonlinear Equation
Solving [106.63673243937492]
ニューラルネットワークの評価や自己回帰モデルからのサンプリングなどのフィードフォワード計算は、機械学習においてユビキタスである。
本稿では,非線形方程式の解法としてフィードフォワード計算の課題を定式化し,ジャコビ・ガウス・シーデル固定点法とハイブリッド法を用いて解を求める。
提案手法は, 並列化可能な繰り返し回数の削減(あるいは等値化)により, 元のフィードフォワード計算と全く同じ値が与えられることを保証し, 十分な並列化計算能力を付与する。
論文 参考訳（メタデータ） (2020-02-10T10:11:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。