  Given multiple point clouds, how to find the rigid transform (rotation,
reflection, and shifting) such that these point clouds are well aligned? This
problem, known as the generalized orthogonal Procrustes problem (GOPP), has
found numerous applications in statistics, computer vision, and imaging
science. While one commonly-used method is finding the least squares estimator,
it is generally an NP-hard problem to obtain the least squares estimator
exactly due to the notorious nonconvexity. In this work, we apply the
semidefinite programming (SDP) relaxation and the generalized power method to
solve this generalized orthogonal Procrustes problem. In particular, we assume
the data are generated from a signal-plus-noise model: each observed point
cloud is a noisy copy of the same unknown point cloud transformed by an unknown
orthogonal matrix and also corrupted by additive Gaussian noise. We show that
the generalized power method (equivalently alternating minimization algorithm)
with spectral initialization converges to the unique global optimum to the SDP
relaxation, provided that the signal-to-noise ratio is high. Moreover, this
limiting point is exactly the least squares estimator and also the maximum
likelihood estimator. In addition, we derive a block-wise estimation error for
each orthogonal matrix and the underlying point cloud. Our theoretical bound is
near-optimal in terms of the information-theoretic limit (only loose by a
factor of the dimension and a log factor). Our results significantly improve
the state-of-the-art results on the tightness of the SDP relaxation for the
generalized orthogonal Procrustes problem, an open problem posed by Bandeira,
Khoo, and Singer in 2014.
