論文の概要: One Ring to Rule Them All: Certifiably Robust Geometric Perception with
Outliers
- arxiv url: http://arxiv.org/abs/2006.06769v2
- Date: Mon, 19 Oct 2020 14:27:57 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-22 14:43:24.373904
- Title: One Ring to Rule Them All: Certifiably Robust Geometric Perception with
Outliers
- Title（参考訳）: 1つのリングで全てのルールを定めます:アウトリーチによるロバストな幾何学的知覚
- Authors: Heng Yang, Luca Carlone
- Abstract要約: 本稿では,大量の外れ値が存在する場合の認識のための認証アルゴリズムを設計するための,最初の汎用的かつ実用的な手法を提案する。
我々の双対証明器は任意の問題の解の最適部分最適性を利用する。
- 参考スコア（独自算出の注目度）: 32.1176248075545
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose the first general and practical framework to design certifiable
algorithms for robust geometric perception in the presence of a large amount of
outliers. We investigate the use of a truncated least squares (TLS) cost
function, which is known to be robust to outliers, but leads to hard,
nonconvex, and nonsmooth optimization problems. Our first contribution is to
show that -for a broad class of geometric perception problems- TLS estimation
can be reformulated as an optimization over the ring of polynomials and
Lasserre's hierarchy of convex moment relaxations is empirically tight at the
minimum relaxation order (i.e., certifiably obtains the global minimum of the
nonconvex TLS problem). Our second contribution is to exploit the structural
sparsity of the objective and constraint polynomials and leverage basis
reduction to significantly reduce the size of the semidefinite program (SDP)
resulting from the moment relaxation, without compromising its tightness. Our
third contribution is to develop scalable dual optimality certifiers from the
lens of sums-of-squares (SOS) relaxation, that can compute the suboptimality
gap and possibly certify global optimality of any candidate solution (e.g.,
returned by fast heuristics such as RANSAC or graduated non-convexity). Our
dual certifiers leverage Douglas-Rachford Splitting to solve a convex
feasibility SDP. Numerical experiments across different perception problems,
including single rotation averaging, shape alignment, 3D point cloud and mesh
registration, and high-integrity satellite pose estimation, demonstrate the
tightness of our relaxations, the correctness of the certification, and the
scalability of the proposed dual certifiers to large problems, beyond the reach
of current SDP solvers.
- Abstract（参考訳）: 本稿では,多量の異常値が存在する場合にロバストな幾何知覚を行うための証明可能なアルゴリズムを設計するための,最初の汎用的かつ実用的な枠組みを提案する。
本稿では, 減算最小二乗(TLS)コスト関数の利用について検討するが, ハード, 非凸, 非平滑な最適化問題に繋がる。
我々の最初の貢献は、より広い種類の幾何学的知覚問題に対して、TLS推定は多項式環上の最適化として再計算でき、ラッサールの凸モーメント緩和の階層は最小緩和順序で経験的に厳密である(すなわち、非凸TLS問題の大域的最小値を得る)ことを示すことである。
第2の貢献は、目的多項式と制約多項式の構造的疎結合を利用して、その厳密さを損なうことなく、半定値プログラム(SDP)のサイズを大幅に削減することである。
第3の貢献は、サブオプティリティギャップを計算し、任意の候補解(例えば、ransac やgraditated non-convexity のような高速なヒューリスティックによって返される)のグローバル最適性を証明できる、sos(sums-of-squares)緩和のレンズからスケーラブルな2つの最適性証明器を開発することである。
我々の二重証明器はダグラス・ラフフォード分割を利用して凸実現可能性SDPを解く。
単一回転平均化,形状アライメント,3次元点雲とメッシュの登録,高積分衛星ポーズ推定などの異なる知覚問題に対する数値実験により,現在のSDP解法の範囲を超えて,我々の緩和の厳密さ,認証の正しさ,提案した二重証明器のスケーラビリティを大きな問題に適用できることを示した。
関連論文リスト
- Double Duality: Variational Primal-Dual Policy Optimization for
Constrained Reinforcement Learning [132.7040981721302]
本研究では,訪問尺度の凸関数を最小化することを目的として,制約付き凸決定プロセス(MDP)について検討する。
制約付き凸MDPの設計アルゴリズムは、大きな状態空間を扱うなど、いくつかの課題に直面している。
論文 参考訳（メタデータ） (2024-02-16T16:35:18Z) - Semidefinite Relaxations for Robust Multiview Triangulation [53.360555898338106]
既存の緩和手法を最小2乗のコスト関数を組み込むことで、非ロバストなマルチビュー三角測量に拡張する。
提案手法は,大きな雑音と大容量の異常の下でも,証明可能な最適再構成を計算できることを実証する。
論文 参考訳（メタデータ） (2023-01-26T21:31:32Z) - Fully Stochastic Trust-Region Sequential Quadratic Programming for
Equality-Constrained Optimization Problems [62.83783246648714]
目的と決定論的等式制約による非線形最適化問題を解くために,逐次2次プログラミングアルゴリズム(TR-StoSQP)を提案する。
アルゴリズムは信頼領域半径を適応的に選択し、既存の直線探索StoSQP方式と比較して不確定なヘッセン行列を利用することができる。
論文 参考訳（メタデータ） (2022-11-29T05:52:17Z) - Certifiable Outlier-Robust Geometric Perception: Exact Semidefinite
Relaxations and Scalable Global Optimization [29.738513596063946]
本稿では,外接点の存在下でのロバストな幾何学的知覚のためのアルゴリズム設計のための,最初の汎用フレームワークを提案する。
我々の実験では、SDP緩和はアプリケーション間で最大で外れ率で正確であることを実証した。
論文 参考訳（メタデータ） (2021-09-07T21:42:16Z) - STRIDE along Spectrahedral Vertices for Solving Large-Scale Rank-One
Semidefinite Relaxations [27.353023427198806]
我々は、制約のない最適化問題(POP)の高次半定値プログラミング緩和を考察する。
POPから独立してSDPを解く既存のアプローチは、そのようなSDPの典型的な非エネルギー性のため、大きな問題にスケールできないか、あるいは緩やかな収束に苦しむことができない。
我々は SpecTrahedral vErtices (STRIDE) と呼ばれる新しいアルゴリズムフレームワークを提案する。
論文 参考訳（メタデータ） (2021-05-28T18:07:16Z) - Towards Optimal Branching of Linear and Semidefinite Relaxations for Neural Network Robustness Certification [10.349616734896522]
本研究では,ReLUニューラルネットワークの逆入力摂動に対する堅牢性を検証する。
入力不確実性集合を分割し,各部分の緩和を個別に解くために,分岐とバウンドのアプローチをとる。
提案手法は緩和誤差を低減し,ReLUアクティベーションの性質を活かしたパーティションを用いてLP緩和を行うことによって完全に誤差を除去することを示す。
論文 参考訳（メタデータ） (2021-01-22T19:36:40Z) - Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
我々のアルゴリズムは、トレーニングセットのサイズとパラメータの数によらず、多くの評価勾配を必要とすることを証明している。
MNIST と ImageNet の実験により,本手法の 9-36 倍の効率性を持つアルゴリズムの理論的スケーリングが確認された。
論文 参考訳（メタデータ） (2020-10-12T17:41:44Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳（メタデータ） (2020-07-14T12:38:21Z) - Convex Geometry and Duality of Over-parameterized Neural Networks [70.15611146583068]
有限幅2層ReLUネットワークの解析のための凸解析手法を開発した。
正規化学習問題に対する最適解が凸集合の極点として特徴づけられることを示す。
高次元では、トレーニング問題は無限に多くの制約を持つ有限次元凸問題としてキャストできることが示される。
論文 参考訳（メタデータ） (2020-02-25T23:05:33Z) - TEASER: Fast and Certifiable Point Cloud Registration [30.19476775410544]
最初の高速かつ堅牢な3Dポイントの登録アルゴリズムは、大量の外れ値の存在下での3Dポイントの登録である。
TEASER++という名前の第二の高速で堅牢な認証翻訳は、大規模なサブプロブレムを解決するために、既成の非コンポーネントを使用する。
論文 参考訳（メタデータ） (2020-01-21T18:56:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。