  We extend coordinate descent to manifold domains, and provide convergence
analyses for geodesically convex and non-convex smooth objective functions. Our
key insight is to draw an analogy between coordinate blocks in Euclidean space
and tangent subspaces of a manifold. Hence, our method is called tangent
subspace descent (TSD). The core principle behind ensuring convergence of TSD
is the appropriate choice of subspace at each iteration. To this end, we
propose two novel conditions, the gap ensuring and $C$-randomized norm
conditions on deterministic and randomized modes of subspace selection
respectively, that promise convergence for smooth functions and that are
satisfied in practical contexts. We propose two subspace selection rules of
particular practical interest that satisfy these conditions: a deterministic
one for the manifold of square orthogonal matrices, and a randomized one for
the Stiefel manifold. Our proof-of-concept numerical experiments on the
orthogonal Procrustes problem demonstrate TSD's efficacy.
