Sparse Quadratic Optimisation over the Stiefel Manifold with Application
  to Permutation Synchronisation
  We address the non-convex optimisation problem of finding a sparse matrix on
the Stiefel manifold (matrices with mutually orthogonal columns of unit length)
that maximises (or minimises) a quadratic objective function. Optimisation
problems on the Stiefel manifold occur for example in spectral relaxations of
various combinatorial problems, such as graph matching, clustering, or
permutation synchronisation. Although sparsity is a desirable property in such
settings, it is mostly neglected in spectral formulations since existing
solvers, e.g. based on eigenvalue decomposition, are unable to account for
sparsity while at the same time maintaining global optimality guarantees. We
fill this gap and propose a simple yet effective sparsity-promoting
modification of the Orthogonal Iteration algorithm for finding the dominant
eigenspace of a matrix. By doing so, we can guarantee that our method finds a
Stiefel matrix that is globally optimal with respect to the quadratic objective
function, while in addition being sparse. As a motivating application we
consider the task of permutation synchronisation, which can be understood as a
constrained clustering problem that has particular relevance for matching
multiple images or 3D shapes in computer vision, computer graphics, and beyond.
We demonstrate that the proposed approach outperforms previous methods in this
domain.
