Non-smooth Optimization over Stiefel Manifolds with
Applications to Dimensionality Reduction and Graph Clustering
Abstract
This paper is concerned with the class of nonconvex optimization problems with orthogonality constraints. We develop computationally effi-
cient relaxations that transform non-convex orthogonality constrained problems into polynomial-time
solvable surrogates. A novel penalization technique is used to enforce feasibility and derive certain conditions under which the constraints of the
original non-convex problem are guaranteed to be
satisfied. Moreover, we extend our approach to a
feasibility-preserving sequential scheme that solves
penalized relaxation to obtain near-globally optimal points. Experimental results on synthetic and
real datasets demonstrate the effectiveness of the
proposed approach on two practical applications in
machine learning