論文の概要: CLIPPER: Robust Data Association without an Initial Guess
- arxiv url: http://arxiv.org/abs/2402.07284v1
- Date: Sun, 11 Feb 2024 19:16:01 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-13 16:17:20.283969
- Title: CLIPPER: Robust Data Association without an Initial Guess
- Title（参考訳）: CLIPPER: 初期ガイダンスのないロバストデータアソシエーション
- Authors: Parker C. Lusk and Jonathan P. How
- Abstract要約: 初期推定を必要としないデータアソシエーションのためのグラフ理論の定式化について検討する。
既存のグラフ理論アプローチは、未重み付きグラフを最適化し、重み付きエッジに符号化された重要な一貫性情報を破棄し、NPハード問題を正確に解こうとする。
この問題に対して2つの緩和法を導入する: 凸半有限緩和法は経験的に厳密であることが判明し、CLIPPERと呼ばれる高速な1次アルゴリズムはミリ秒でほぼ最適解に到達する。
- 参考スコア（独自算出の注目度）: 38.56736000339334
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Identifying correspondences in noisy data is a critically important step in
estimation processes. When an informative initial estimation guess is
available, the data association challenge is less acute; however, the existence
of a high-quality initial guess is rare in most contexts. We explore
graph-theoretic formulations for data association, which do not require an
initial estimation guess. Existing graph-theoretic approaches optimize over
unweighted graphs, discarding important consistency information encoded in
weighted edges, and frequently attempt to solve NP-hard problems exactly. In
contrast, we formulate a new optimization problem that fully leverages weighted
graphs and seeks the densest edge-weighted clique. We introduce two relaxations
to this problem: a convex semidefinite relaxation which we find to be
empirically tight, and a fast first-order algorithm called CLIPPER which
frequently arrives at nearly-optimal solutions in milliseconds. When evaluated
on point cloud registration problems, our algorithms remain robust up to at
least 95% outliers while existing algorithms begin breaking down at 80%
outliers. Code is available at https://mit-acl.github.io/clipper.
- Abstract（参考訳）: ノイズデータ中の対応の特定は、推定プロセスにおいて極めて重要なステップである。
情報的初期推定が利用可能であれば、データアソシエーションの課題はそれほど難しくないが、ほとんどの文脈で高品質な初期推定が存在することは稀である。
初期推定を必要としないデータアソシエーションのためのグラフ理論の定式化について検討する。
既存のグラフ理論のアプローチは、非重み付けグラフを最適化し、重み付けエッジにエンコードされた重要な一貫性情報を破棄し、np-hard問題を正確に解決しようとする。
対照的に、重み付きグラフを完全に活用し、最も密度の高いエッジ重み付き傾きを求める新しい最適化問題を定式化する。
この問題に2つの緩和を導入する: 経験的にタイトな凸半定値緩和と、数ミリ秒で最適に近い解に頻繁に到達するクリッパーと呼ばれる高速一階アルゴリズムである。
ポイントクラウド登録問題で評価した場合、既存のアルゴリズムが80%の外れ値で分解し始めるまで、アルゴリズムは少なくとも95%の外れ値まで頑健である。
コードはhttps://mit-acl.github.io/clipperで入手できる。
関連論文リスト
- Fast and Robust Non-Rigid Registration Using Accelerated
Majorization-Minimization [35.66014845211251]
非剛性登録は、ターゲット形状と整合する非剛性な方法でソース形状を変形させるが、コンピュータビジョンにおける古典的な問題である。
既存のメソッドは通常$ell_p$型ロバストノルムを使用してアライメントエラーを測定し、変形の滑らかさを規則化する。
本稿では、アライメントと正規化のためのグローバルなスムーズなロバストノルムに基づく、ロバストな非剛体登録のための定式化を提案する。
論文 参考訳（メタデータ） (2022-06-07T16:00:33Z) - A Sketching Method for Finding the Closest Point on a Convex Hull [0.0]
我々は,データセットの凸殻上の点を,その外側の問合せ点に最も近いようにスケッチするアルゴリズムを開発した。
本手法は, 既成のアルゴリズムよりも高速な凸問題の最適解を導出する。
論文 参考訳（メタデータ） (2021-02-21T03:55:18Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - Outlier-Robust Estimation: Hardness, Minimally Tuned Algorithms, and
Applications [25.222024234900445]
本稿では,外乱推定,一般化最大収束(G-MC),一般化最小正方形(G-TLS)の2つの統一式を提案する。
最悪の場合、(概して)外れ値の集合を見つけることは不可能である。
そこで我々は, 降圧器から降圧器を分離する方法を動的に決定する, 降圧器のリジェクションのための最小調整アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-07-29T21:06:13Z) - Semi-Supervised Learning with Meta-Gradient [123.26748223837802]
半教師付き学習における簡単なメタ学習アルゴリズムを提案する。
その結果,提案アルゴリズムは最先端の手法に対して良好に動作することがわかった。
論文 参考訳（メタデータ） (2020-07-08T08:48:56Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-06-24T11:37:33Z) - Least Squares Regression with Markovian Data: Fundamental Limits and
Algorithms [69.45237691598774]
マルコフ連鎖からデータポイントが依存しサンプリングされる最小二乗線形回帰問題について検討する。
この問題を$tau_mathsfmix$という観点から、鋭い情報理論のミニマックス下限を確立する。
本稿では,経験的リプレイに基づくアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-16T04:26:50Z) - Quasi-Newton Solver for Robust Non-Rigid Registration [35.66014845211251]
データフィッティングと正規化のための大域的スムーズなロバスト推定器に基づくロバストな非剛性登録のための定式化を提案する。
本稿では,L-BFGS を用いた最小二乗問題の解法に,各繰り返しを減らし,最大化最小化アルゴリズムを適用した。
論文 参考訳（メタデータ） (2020-04-09T01:45:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。