  Nonsmooth composite optimization with orthogonality constraints has a broad
spectrum of applications in statistical learning and data science. However,
this problem is generally challenging to solve due to its non-convex and
non-smooth nature. Existing solutions are limited by one or more of the
following restrictions: (i) they are full gradient methods that require high
computational costs in each iteration; (ii) they are not capable of solving
general nonsmooth composite problems; (iii) they are infeasible methods and can
only achieve the feasibility of the solution at the limit point; (iv) they lack
rigorous convergence guarantees; (v) they only obtain weak optimality of
critical points. In this paper, we propose \textit{\textbf{OBCD}}, a new Block
Coordinate Descent method for solving general nonsmooth composite problems
under Orthogonality constraints. \textit{\textbf{OBCD}} is a feasible method
with low computation complexity footprints. In each iteration, our algorithm
updates $k$ rows of the solution matrix ($k\geq2$ is a parameter) to preserve
the constraints. Then, it solves a small-sized nonsmooth composite optimization
problem under orthogonality constraints either exactly or approximately. We
demonstrate that any exact block-$k$ stationary point is always an approximate
block-$k$ stationary point, which is equivalent to the critical stationary
point. We are particularly interested in the case where $k=2$ as the resulting
subproblem reduces to a one-dimensional nonconvex problem. We propose a
breakpoint searching method and a fifth-order iterative method to solve this
problem efficiently and effectively. We also propose two novel greedy
strategies to find a good working set to further accelerate the convergence of
\textit{\textbf{OBCD}}. Finally, we have conducted extensive experiments on
several tasks to demonstrate the superiority of our approach.
