  Block majorization-minimization (BMM) is a simple iterative algorithm for
nonconvex optimization that sequentially minimizes a majorizing surrogate of
the objective function in each block coordinate while the other block
coordinates are held fixed. We consider a family of BMM algorithms for
minimizing smooth nonconvex objectives, where each parameter block is
constrained within a subset of a Riemannian manifold. We establish that this
algorithm converges asymptotically to the set of stationary points, and attains
an $\epsilon$-stationary point within $\widetilde{O}(\epsilon^{-2})$
iterations. In particular, the assumptions for our complexity results are
completely Euclidean when the underlying manifold is a product of Euclidean or
Stiefel manifolds, although our analysis makes explicit use of the Riemannian
geometry. Our general analysis applies to a wide range of algorithms with
Riemannian constraints: Riemannian MM, block projected gradient descent,
optimistic likelihood estimation, geodesically constrained subspace tracking,
robust PCA, and Riemannian CP-dictionary-learning. We experimentally validate
that our algorithm converges faster than standard Euclidean algorithms applied
to the Riemannian setting.
