論文の概要: Generalized Power Method for Generalized Orthogonal Procrustes Problem:
Global Convergence and Optimization Landscape Analysis
- arxiv url: http://arxiv.org/abs/2106.15493v1
- Date: Tue, 29 Jun 2021 15:19:25 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-30 19:28:09.943778
- Title: Generalized Power Method for Generalized Orthogonal Procrustes Problem:
Global Convergence and Optimization Landscape Analysis
- Title（参考訳）: 一般化直交問題に対する一般化パワー法:大域収束と最適化ランドスケープ解析
- Authors: Shuyang Ling
- Abstract要約: 多重点雲の集合を考えると、厳密性係数化緩和正方形を見つけるにはどうすればよいか。
信号-雑音比が比較的大きい場合、SDPは最小の刺激変換推定器と完全に等しいことを示す。
- 参考スコア（独自算出の注目度）: 1.5229257192293197
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Given a set of multiple point clouds, how to find the rigid transformations
(rotation, reflection, and shifting) such that these point clouds are well
aligned? This problem, known as the generalized orthogonal Procrustes problem
(GOPP), plays a fundamental role in several scientific disciplines including
statistics, imaging science and computer vision. Despite its tremendous
practical importance, it is still a challenging computational problem due to
the inherent nonconvexity. In this paper, we study the semidefinite programming
(SDP) relaxation of the generalized orthogonal Procrustes problems and prove
that the tightness of the SDP relaxation holds, i.e., the SDP estimator exactly
equals the least squares estimator, if the signal-to-noise ratio (SNR) is
relatively large. We also prove that an efficient generalized power method with
a proper initialization enjoys global linear convergence to the least squares
estimator. In addition, we analyze the Burer-Monteiro factorization and show
the corresponding optimization landscape is free of spurious local optima if
the SNR is large. This explains why first-order Riemannian gradient methods
with random initializations usually produce a satisfactory solution despite the
nonconvexity. One highlight of our work is that the theoretical guarantees are
purely algebraic and do not require any assumptions on the statistical property
of the noise. Our results partially resolve one open problem posed in
[Bandeira, Khoo, Singer, 2014] on the tightness of the SDP relaxation in
solving the generalized orthogonal Procrustes problem. Numerical simulations
are provided to complement our theoretical analysis.
- Abstract（参考訳）: 複数の点雲が与えられたとき、これらの点雲が整列しているような剛性変換(回転、反射、シフト)をどうやって見つけるか。
この問題はGOPP(Generalized orthogonal Procrustes problem)として知られ、統計学、画像科学、コンピュータビジョンなどいくつかの科学分野において基本的な役割を果たす。
非常に現実的な重要性があるにもかかわらず、本質的な非凸性のため、依然として難しい計算問題である。
本稿では,一般化直交プロクリスト問題の半定値プログラミング(SDP)緩和について検討し,信号-雑音比(SNR)が比較的大きい場合,SDP緩和の厳密性は最小二乗推定器と完全に等しいことを示す。
また,適切な初期化を持つ効率的な一般化解法が最小二乗推定器への大域的線形収束を享受できることを証明した。
さらに,Burer-Monteiro の分解を解析し,SNR が大きければ,対応する最適化ランドスケープが急激な局所最適化を伴わないことを示す。
これは、ランダム初期化を持つ一階リーマン勾配法が通常、非凸性にもかかわらず満足のいく解を生み出す理由を説明する。
我々の研究のハイライトは、理論的な保証は純粋に代数的であり、ノイズの統計的性質に関する仮定を必要としないことである。
一般化直交プロクリスト問題の解法におけるSDP緩和の厳密性について,[Bandeira, Khoo, Singer, 2014]で提起された1つのオープン問題を部分的に解決した。
理論的解析を補完する数値シミュレーションが提供される。
関連論文リスト
- A Unified Theory of Stochastic Proximal Point Methods without Smoothness [52.30944052987393]
近点法はその数値的安定性と不完全なチューニングに対する頑健性からかなりの関心を集めている。
本稿では,近位点法(SPPM)の幅広いバリエーションの包括的解析について述べる。
論文 参考訳（メタデータ） (2024-05-24T21:09:19Z) - On the Estimation Performance of Generalized Power Method for
Heteroscedastic Probabilistic PCA [21.9585534723895]
我々は,少なくとも幾何的にあるしきい値に束縛されたGPM間の適切な繰り返しを仮定すると,GPMは,ある「相対分解」の残余部分であるしきい値に減少することを示す。
そこで本研究では,PCA手法を用いて,ガウス以下の雑音設定による優れた性能を示す。
論文 参考訳（メタデータ） (2023-12-06T11:41:17Z) - Curvature-Independent Last-Iterate Convergence for Games on Riemannian
Manifolds [77.4346324549323]
本研究では, 多様体の曲率に依存しないステップサイズが, 曲率非依存かつ直線的最終点収束率を達成することを示す。
我々の知る限りでは、曲率非依存率や/または最終点収束の可能性はこれまでに検討されていない。
論文 参考訳（メタデータ） (2023-06-29T01:20:44Z) - Asymptotically Unbiased Instance-wise Regularized Partial AUC
Optimization: Theory and Algorithm [101.44676036551537]
One-way partial AUC (OPAUC) と Two-way partial AUC (TPAUC) はバイナリ分類器の平均性能を測定する。
既存の手法のほとんどはPAUCをほぼ最適化するしかなく、制御不能なバイアスにつながる。
本稿では,分散ロバスト最適化AUCによるPAUC問題の簡易化について述べる。
論文 参考訳（メタデータ） (2022-10-08T08:26:22Z) - Lattice partition recovery with dyadic CART [79.96359947166592]
我々は、$d$次元格子上の加法ガウス雑音によって破損したピースワイド定値信号について検討する。
この形式のデータは、多くのアプリケーションで自然に発生し、統計処理や信号処理の文献において、信号の検出やテスト、ノイズの除去、推定といったタスクが広く研究されている。
本稿では,未知の信号の一貫性領域によって誘導される格子の分割を推定する,分割回復の問題について考察する。
我々は、DCARTベースの手順が、下位分割を$sigma2 k*の順序で一貫して推定することを証明した。
論文 参考訳（メタデータ） (2021-05-27T23:41:01Z) - A Retrospective Approximation Approach for Smooth Stochastic
Optimization [0.2867517731896504]
グラディエント(グラディエント、英: Gradient、SG)とは、最適化(SO)問題をスムーズ(ノンフィクション)な目標値で解くための補足的反復手法である。
論文 参考訳（メタデータ） (2021-03-07T16:29:36Z) - Proximal and Federated Random Reshuffling [11.83842808044211]
ランダムリシャッフルのための2つの新しいアルゴリズムを提案する。
ProxRR と FedRR は複合凸有限和最小化問題を解く。
ProxRRは、各イテレーションの近位演算子を評価するアルゴリズムよりも高速です。
論文 参考訳（メタデータ） (2021-02-12T18:59:24Z) - Continuous Wasserstein-2 Barycenter Estimation without Minimax
Optimization [94.18714844247766]
ワッサーシュタイン・バリセンターは、最適輸送に基づく確率測度の重み付き平均の幾何学的概念を提供する。
本稿では,Wasserstein-2 バリセンタのサンプルアクセスを演算するスケーラブルなアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-02-02T21:01:13Z) - On Projection Robust Optimal Transport: Sample Complexity and Model
Misspecification [101.0377583883137]
射影ロバスト(PR)OTは、2つの測度の間のOTコストを最大化するために、射影可能な$k$次元部分空間を選択する。
私たちの最初の貢献は、PRワッサーシュタイン距離のいくつかの基本的な統計的性質を確立することである。
次に、部分空間を最適化するのではなく平均化することにより、PRW距離の代替として積分PRワッサーシュタイン距離(IPRW)を提案する。
論文 参考訳（メタデータ） (2020-06-22T14:35:33Z) - Fundamental Limits of Ridge-Regularized Empirical Risk Minimization in
High Dimensions [41.7567932118769]
経験的リスク最小化アルゴリズムは、様々な推定や予測タスクで広く利用されている。
本稿では,コンベックスEMMの統計的精度に関する基礎的限界を推論のために初めて特徴づける。
論文 参考訳（メタデータ） (2020-06-16T04:27:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。