論文の概要: Rotation Coordinate Descent for Fast Globally Optimal Rotation Averaging

• arxiv url: http://arxiv.org/abs/2103.08292v2
• Date: Tue, 16 Mar 2021 02:06:53 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-17 11:16:01.485566
• Title: Rotation Coordinate Descent for Fast Globally Optimal Rotation Averaging
• Title（参考訳）: 回転座標の高速なグローバル最適回転平均化
• Authors: \'Alvaro Parra, Shin-Fang Chng, Tat-Jun Chin, Anders Eriksson, Ian Reid
• Abstract要約: 回転座標降下 (RCD) と呼ばれる世界最適性を実現する高速アルゴリズムを提案する。 半定値行列を行ごと更新することでSDPを解くブロック座標降下(BCD)とは異なり、RCDは繰り返しを通して全ての有効な回転を直接維持・更新する。 我々は数学的にアルゴリズムの収束を証明し、最先端のグローバル手法よりも優れた効率を示す。
• 参考スコア（独自算出の注目度）: 47.3713707521106
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Under mild conditions on the noise level of the measurements, rotation averaging satisfies strong duality, which enables global solutions to be obtained via semidefinite programming (SDP) relaxation. However, generic solvers for SDP are rather slow in practice, even on rotation averaging instances of moderate size, thus developing specialised algorithms is vital. In this paper, we present a fast algorithm that achieves global optimality called rotation coordinate descent (RCD). Unlike block coordinate descent (BCD) which solves SDP by updating the semidefinite matrix in a row-by-row fashion, RCD directly maintains and updates all valid rotations throughout the iterations. This obviates the need to store a large dense semidefinite matrix. We mathematically prove the convergence of our algorithm and empirically show its superior efficiency over state-of-the-art global methods on a variety of problem configurations. Maintaining valid rotations also facilitates incorporating local optimisation routines for further speed-ups. Moreover, our algorithm is simple to implement; see supplementary material for a demonstration program.
• Abstract（参考訳）: 測定値の雑音レベルに関する穏やかな条件下では、回転平均化は強い双対性を満たすため、半有限計画法(SDP)緩和による大域的解が得られる。 しかし、SDPの一般的な解法は、適度な大きさの回転平均化の場合でさえ、実際にはかなり遅いため、特殊化アルゴリズムの開発は不可欠である。 本稿では,回転座標降下(RCD)と呼ばれる大域的最適性を実現する高速アルゴリズムを提案する。 半定値行列を行ごと更新することでSDPを解くブロック座標降下(BCD)とは異なり、RCDは繰り返しを通して全ての有効な回転を直接維持・更新する。 これにより、大きな密度の半定義行列を格納する必要がなくなる。 アルゴリズムの収束を数学的に証明し、様々な問題構成に関する最先端のグローバル手法よりも優れた効率を実証的に示す。 有効なローテーションを維持することで、さらなるスピードアップのために局所最適化ルーチンを組み込むことも容易になる。 さらに,本アルゴリズムは実装が容易であり,デモプログラムの補足資料も参照する。

関連論文リスト

• 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)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Large-scale Optimization of Partial AUC in a Range of False Positive Rates [51.12047280149546]
  ROC曲線 (AUC) の下の領域は、機械学習において最も広く使われている分類モデルのパフォーマンス指標の1つである。 近年の封筒平滑化技術に基づく効率的な近似勾配降下法を開発した。 提案アルゴリズムは,効率のよい解法を欠くランク付けされた範囲損失の和を最小化するためにも利用できる。
  論文  参考訳（メタデータ） (2022-03-03T03:46:18Z)
• Distributed stochastic optimization with large delays [59.95552973784946]
  大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。 DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
  論文  参考訳（メタデータ） (2021-07-06T21:59:49Z)
• Momentum-inspired Low-Rank Coordinate Descent for Diagonally Constrained SDPs [12.7944665592057]
  本稿では,制約付き半有限計画法(SDP)を高速化した非自明なプログラムを用いて大規模に解くための,新しい,実用的で証明可能なアプローチを提案する。
  論文  参考訳（メタデータ） (2021-06-16T13:35:40Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Efficient Algorithms for Rotation Averaging Problems [17.101725065752486]
  平均問題は、コンピュータアプリケーションにおける基本的なタスクです。 定常点への収束を保証したブロック平均化アルゴリズムを提案する。 また,上界最小化を適用した平均化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-03-18T05:22:45Z)
• Hybrid Rotation Averaging: A Fast and Robust Rotation Averaging Approach [28.56388668402907]
  運動からのインクリメンタル構造(SfM)に対するハイブリッド回転平均化手法を提案する。 グローバルRAは低騒音条件下でのグローバルな最適性を保証するが、非効率であり、外れ値や高騒音の影響を受けやすい。 提案手法は,悪いカメラポーズを効果的に補正し,ドリフトを低減し,高い実用性を示す。
  論文  参考訳（メタデータ） (2021-01-22T14:11:19Z)
• Shonan Rotation Averaging: Global Optimality by Surfing $SO(p)^n$ [26.686173666277725]
  焼南回転平均化は, 測定ノイズの軽度な仮定の下で, 世界規模で最適解を復元することが保証される。 そこで本手法では, 回転平均化問題の最適解を導出するために半定緩和法を用いる。
  論文  参考訳（メタデータ） (2020-08-06T16:08:23Z)
• Stochastic Coordinate Minimization with Progressive Precision for Stochastic Convex Optimization [16.0251555430107]
  凸最適化のための反復座標最小化(CM)に基づくフレームワークを開発した。 最適精度制御と結果の順序-最適後悔性能を確立する。 提案アルゴリズムは,大規模最適化のためのCMのスケーラビリティと並列性特性を継承し,オンライン実装に適したアルゴリズムである。
  論文  参考訳（メタデータ） (2020-03-11T18:42:40Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。