Generalized Orthogonal Procrustes Problem under Arbitrary Adversaries
This provides theoretical guarantees for solving a fundamental problem in statistics, imaging, and computer vision, applicable to various adversarial settings without statistical priors.
The paper tackles the NP-hard generalized orthogonal Procrustes problem (GOPP) by analyzing semidefinite relaxation (SDR) and a generalized power method (GPM), showing that SDR exactly recovers the least squares estimator and GPM converges linearly to the global minimizer under high signal-to-noise ratio conditions.
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 generally an NP-hard problem to find the least squares estimator. We study the semidefinite relaxation (SDR) and an iterative method named generalized power method (GPM) to find the least squares estimator, and investigate the performance under a signal-plus-noise model. We show that the SDR recovers the least squares estimator exactly and moreover the generalized power method with a proper initialization converges linearly to the global minimizer to the SDR, provided that the signal-to-noise ratio is large. The main technique follows from showing the nonlinear mapping involved in the GPM is essentially a local contraction mapping and then applying the well-known Banach fixed-point theorem finishes the proof. In addition, we analyze the low-rank factorization algorithm and show the corresponding optimization landscape is free of spurious local minimizers under nearly identical conditions that enables the success of SDR approach. The highlight of our work is that the theoretical guarantees are purely algebraic and do not assume any statistical priors of the additive adversaries, and thus it applies to various interesting settings.