  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.
