論文の概要: Provably Approximated ICP
- arxiv url: http://arxiv.org/abs/2101.03588v1
- Date: Sun, 10 Jan 2021 18:09:29 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-08 08:20:44.397994
- Title: Provably Approximated ICP
- Title（参考訳）: 近似ICP
- Authors: Ibrahim Jubran, Alaa Maalouf, Ron Kimmel, Dan Feldman
- Abstract要約: そこで、emphalwaysが$p times q$で3ドルのペアからなる"witness"集合があることを証明し、新しいアライメントアルゴリズムにより、この大域的最適化に対する定数因子近似を定義する。
私たちの近似定数は、実際には1ドル近くであり、最先端のアルゴリズムよりも最大10ドル小さいです。
- 参考スコア（独自算出の注目度）: 40.349822671753024
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The goal of the \emph{alignment problem} is to align a (given) point cloud $P
= \{p_1,\cdots,p_n\}$ to another (observed) point cloud $Q =
\{q_1,\cdots,q_n\}$. That is, to compute a rotation matrix $R \in \mathbb{R}^{3
\times 3}$ and a translation vector $t \in \mathbb{R}^{3}$ that minimize the
sum of paired distances $\sum_{i=1}^n D(Rp_i-t,q_i)$ for some distance function
$D$. A harder version is the \emph{registration problem}, where the
correspondence is unknown, and the minimum is also over all possible
correspondence functions from $P$ to $Q$. Heuristics such as the Iterative
Closest Point (ICP) algorithm and its variants were suggested for these
problems, but none yield a provable non-trivial approximation for the global
optimum.
We prove that there \emph{always} exists a "witness" set of $3$ pairs in $P
\times Q$ that, via novel alignment algorithm, defines a constant factor
approximation (in the worst case) to this global optimum. We then provide
algorithms that recover this witness set and yield the first provable constant
factor approximation for the: (i) alignment problem in $O(n)$ expected time,
and (ii) registration problem in polynomial time. Such small witness sets exist
for many variants including points in $d$-dimensional space, outlier-resistant
cost functions, and different correspondence types.
Extensive experimental results on real and synthetic datasets show that our
approximation constants are, in practice, close to $1$, and up to x$10$ times
smaller than state-of-the-art algorithms.
- Abstract（参考訳）: emph{alignment problem} の目標は、 (given) 点クラウド $p = \{p_1,\cdots,p_n\}$ を別の (observed) 点クラウド $q = \{q_1,\cdots,q_n\}$ に合わせることである。
すなわち、回転行列 $r \in \mathbb{r}^{3 \times 3}$ と変換ベクトル $t \in \mathbb{r}^{3}$ を計算すると、ある距離関数 $d$ に対して、対距離の和 $\sum_{i=1}^n d(rp_i-t,q_i)$ が最小になる。
より難しいバージョンは、対応が不明な \emph{registration problem} であり、最小値もまた$p$から$q$までの全ての対応関数である。
イテレーティブ・クローズト・ポイント(ICP)アルゴリズムやその変種のようなヒューリスティックスはこれらの問題に対して提案されたが、大域的最適値に対する証明可能な非自明な近似は得られなかった。
我々は、$P \times Q$に3ドルペアの「ウィットネス」集合が存在することを証明し、新しいアライメントアルゴリズムを通じて、この大域的最適値に対する定数係数近似(最悪の場合)を定義する。
次に、この証人集合を復元し、(i)$O(n)$期待時間におけるアライメント問題、(ii)多項式時間における登録問題の最初の証明可能な定数係数近似を与えるアルゴリズムを提供する。
このような小さな証人集合は、d$-次元空間の点、外れ値耐性コスト関数、異なる対応タイプを含む多くの変種に対して存在する。
実および合成データセットの広範な実験結果から、我々の近似定数は、実際には1ドル近くで、最先端のアルゴリズムよりも最大で10ドル小さいことが分かる。
関連論文リスト
- Near-Optimal and Tractable Estimation under Shift-Invariance [0.21756081703275998]
そのような信号のクラスは、非常にリッチである:$mathbbCn$ 上のすべての指数振動を含み、合計$s$ である。
このクラスの統計複雑性は、$(delta)$-confidence $ell$-ballの半径2乗最小マックス周波数によって測定されるが、$s$-sparse信号のクラス、すなわち$Oleft(slog(en) + log(delta-1)right) cdot log(en/s)とほぼ同じであることを示す。
論文 参考訳（メタデータ） (2024-11-05T18:11:23Z) - Dueling Optimization with a Monotone Adversary [35.850072415395395]
凸最適化の一般化である単調逆数を用いたデュエル最適化の問題点について検討する。
目的は、最小値$mathbfx*$の関数$fcolon XをmathbbRdに変換するために、オンラインアルゴリズムを設計することである。
論文 参考訳（メタデータ） (2023-11-18T23:55:59Z) - 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) - Near-Optimal Non-Convex Stochastic Optimization under Generalized
Smoothness [21.865728815935665]
2つの最近の研究は、$O(epsilon-3)$サンプル複雑性を確立し、$O(epsilon)$-定常点を得る。
しかし、どちらも$mathrmploy(epsilon-1)$という大きなバッチサイズを必要とする。
本研究では,STORMアルゴリズムの単純な変種を再検討することにより,従来の2つの問題を同時に解決する。
論文 参考訳（メタデータ） (2023-02-13T00:22:28Z) - Randomized Block-Coordinate Optimistic Gradient Algorithms for
Root-Finding Problems [8.0153031008486]
大規模設定における非線形方程式の解を近似する2つの新しいアルゴリズムを開発した。
我々は,機械学習における顕著な応用を網羅する大規模有限サム包含のクラスに,本手法を適用した。
論文 参考訳（メタデータ） (2023-01-08T21:46:27Z) - TURF: A Two-factor, Universal, Robust, Fast Distribution Learning
Algorithm [64.13217062232874]
最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。
本稿では,この数値をほぼ最適に推定する手法を提案する。
論文 参考訳（メタデータ） (2022-02-15T03:49:28Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。
構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文 参考訳（メタデータ） (2020-12-14T18:14:08Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - 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) - Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast
Algorithm [100.11971836788437]
固定支持ワッサーシュタインバリセンタ問題(FS-WBP)について検討する。
我々は,有望な反復的ブレグマン射影 (IBP) アルゴリズムであるtextscFastIBP の,証明可能な高速なテキスト決定論的変種を開発する。
論文 参考訳（メタデータ） (2020-02-12T03:40:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。