論文の概要: ARCS: Accurate Rotation and Correspondence Search

• arxiv url: http://arxiv.org/abs/2203.14493v2
• Date: Tue, 29 Mar 2022 04:57:42 GMT
• ステータス: 処理完了
• システム内更新日: 2022-03-30 11:50:24.968339
• Title: ARCS: Accurate Rotation and Correspondence Search
• Title（参考訳）: ARCS:正確な回転と対応検索
• Authors: Liangzu Peng and Manolis C. Tsakiris and Ren\'e Vidal
• Abstract要約: 本論文は,「同時回転・対応探索」と呼ばれる,より汎用的な古いワフバ問題について述べる。 まず最初に、例えば$m,napprox 106$ を 0.1$ 秒で解けるように、$O(mlog m)$ time と $O(m)$ space, iv) を用いる。
• 参考スコア（独自算出の注目度）: 21.01267270902429
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper is about the old Wahba problem in its more general form, which we call "simultaneous rotation and correspondence search". In this generalization we need to find a rotation that best aligns two partially overlapping $3$D point sets, of sizes $m$ and $n$ respectively with $m\geq n$. We first propose a solver, $\texttt{ARCS}$, that i) assumes noiseless point sets in general position, ii) requires only $2$ inliers, iii) uses $O(m\log m)$ time and $O(m)$ space, and iv) can successfully solve the problem even with, e.g., $m,n\approx 10^6$ in about $0.1$ seconds. We next robustify $\texttt{ARCS}$ to noise, for which we approximately solve consensus maximization problems using ideas from robust subspace learning and interval stabbing. Thirdly, we refine the approximately found consensus set by a Riemannian subgradient descent approach over the space of unit quaternions, which we show converges globally to an $\varepsilon$-stationary point in $O(\varepsilon^{-4})$ iterations, or locally to the ground-truth at a linear rate in the absence of noise. We combine these algorithms into $\texttt{ARCS+}$, to simultaneously search for rotations and correspondences. Experiments show that $\texttt{ARCS+}$ achieves state-of-the-art performance on large-scale datasets with more than $10^6$ points with a $10^4$ time-speedup over alternative methods. \url{https://github.com/liangzu/ARCS}
• Abstract（参考訳）: 本稿では、「同時回転・対応探索」と呼ばれる、より一般的な形での古いワフバ問題について述べる。 この一般化では、それぞれ$m$と$n$の2つの部分重なり合う3$D点集合と$m\geq n$のそれぞれを合わせる回転を見つける必要がある。 まず最初に、$\texttt{ARCS}$という解決法を提案します。 一 一般位置における雑音のない点集合を仮定すること。 ii) 2ドルのイリアーのみを必要とする。 iii)$O(m\log m)$ timeと$O(m)$ spaceを使用し、 例えば、$m,n\approx 10^6$ を約0.1$秒で解決できる。 次に、ノイズに対して$\texttt{ARCS}$をロバスト化し、ロバストな部分空間学習とインターバルスタビングのアイデアを用いたコンセンサス最大化問題を概ね解決する。 第3に、単位四元数空間上のリーマン次階降下法(英語版)(Riemannian subgradient descent approach)によって設定された約定値のコンセンサスを洗練し、これは、$O(\varepsilon^{-4})$イテレーションにおける$\varepsilon$-定常点、あるいは雑音がない場合の線形速度で局所的に基底トラスに収束することを示す。 これらのアルゴリズムを$\texttt{ARCS+}$に組み合わせ、回転と対応を同時に検索する。 実験によると、$\texttt{ARCS+}$は10^6$以上の大規模データセットで、代替メソッドよりも10^4$のタイムスピードアップで最先端のパフォーマンスを達成する。 \url{https://github.com/liangzu/ARCS}

関連論文リスト

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces [2.687607197645453]
  次元$Theta(log n)$ が $(sqrt3/2-o(1))$hard である場合でさえ、FPTアルゴリズムを近似する。 また、次元 $Theta(log n)$ が $(sqrt3/2-o(1))$hard であるような特別な場合でさえ、FPTアルゴリズムを近似することを示す。
  論文  参考訳（メタデータ） (2023-05-12T08:43:28Z)
• On Submodular Contextual Bandits [92.45432756301231]
  作用が基底集合の部分集合であり、平均報酬が未知の単調部分モジュラ函数によってモデル化されるような文脈的包帯の問題を考える。 Inverse Gap Weighting 戦略により,提案アルゴリズムは推定関数の局所的最適度を効率よくランダム化することを示す。
  論文  参考訳（メタデータ） (2021-12-03T21:42:33Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
  我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。 実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
  論文  参考訳（メタデータ） (2021-05-17T16:40:48Z)
• Provably Approximated ICP [40.349822671753024]
  そこで、emphalwaysが$p times q$で3ドルのペアからなる"witness"集合があることを証明し、新しいアライメントアルゴリズムにより、この大域的最適化に対する定数因子近似を定義する。 私たちの近似定数は、実際には1ドル近くであり、最先端のアルゴリズムよりも最大10ドル小さいです。
  論文  参考訳（メタデータ） (2021-01-10T18:09:29Z)
• On Efficient Low Distortion Ultrametric Embedding [18.227854382422112]
  データの基盤となる階層構造を保存するために広く用いられる方法は、データを木や超音波に埋め込む方法を見つけることである。 本稿では,$mathbbRd2(ユニバーサル定数$rho>1$)の点集合を入力として,超測度$Deltaを出力する新しいアルゴリズムを提案する。 我々のアルゴリズムの出力はリンクアルゴリズムの出力に匹敵するが、より高速な実行時間を実現する。
  論文  参考訳（メタデータ） (2020-08-15T11:06:45Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Coreset-based Strategies for Robust Center-type Problems [0.6875312133832077]
  我々は、効率的なシーケンシャル、MapReduce、ストリーミングアルゴリズムをもたらす2つの問題に対するコアセットベースの戦略を考案する。 パラメータ$k,zepsilon,D$の広い範囲で、$|V|$で実行時間線形のシーケンシャルアルゴリズムと、ラウンド/パスが少なく、実質的にサブ線形な局所/ワーキングメモリを持つMapReduce/ストリーミングアルゴリズムを得る。
  論文  参考訳（メタデータ） (2020-02-18T10:04:08Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)

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

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