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\nthe Stiefel manifold (matrices with mutually orthogonal columns of unit length)\nthat maximises (or minimises) a quadratic objective function. Optimisation\nproblems on the Stiefel manifold occur for example in spectral relaxations of\nvarious combinatorial problems, such as graph matching, clustering, or\npermutation synchronisation. Although sparsity is a desirable property in such\nsettings, it is mostly neglected in spectral formulations since existing\nsolvers, e.g. based on eigenvalue decomposition, are unable to account for\nsparsity while at the same time maintaining global optimality guarantees. We\nfill this gap and propose a simple yet effective sparsity-promoting\nmodification of the Orthogonal Iteration algorithm for finding the dominant\neigenspace of a matrix. By doing so, we can guarantee that our method finds a\nStiefel matrix that is globally optimal with respect to the quadratic objective\nfunction, while in addition being sparse. As a motivating application we\nconsider the task of permutation synchronisation, which can be understood as a\nconstrained clustering problem that has particular relevance for matching\nmultiple images or 3D shapes in computer vision, computer graphics, and beyond.\nWe demonstrate that the proposed approach outperforms previous methods in this\ndomain.\n