# Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation

arXiv: https://arxiv.org/abs/2110.00053 · HTML: https://mlsanity.com/paper/2110.00053/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 52 references that are in the map.
- First posted on arXiv 30 Sep 2021.

## Builds on (most cited first, 16 of 16)

- [Manopt, a Matlab toolbox for optimization on manifolds](https://mlsanity.com/paper/1308.5200/) (2013)
- [Multi-Image Matching via Fast Alternating Minimization](https://mlsanity.com/paper/1505.04845/) (2015)
- [Isometric Multi-Shape Matching](https://mlsanity.com/paper/2012.02689/) (2020)
- [Quantum Permutation Synchronization](https://mlsanity.com/paper/2101.07755/) (2021)
- [Learning Transformation Synchronization](https://mlsanity.com/paper/1901.09458/) (2019)
- [Probabilistic Permutation Synchronization using the Riemannian Structure of the Birkhoff Polytope](https://mlsanity.com/paper/1904.05814/) (2019)
- [Higher-order Projected Power Iterations for Scalable Multi-Matching](https://mlsanity.com/paper/1811.10541/) (2018)
- [DS*: Tighter Lifting-Free Convex Relaxations for Quadratic Matching Problems](https://mlsanity.com/paper/1711.10733/) (2017)
- [Finding a sparse vector in a subspace: Linear sparsity using alternating directions](https://mlsanity.com/paper/1412.4659/) (2014)
- [A Solution for Multi-Alignment by Transformation Synchronisation](https://mlsanity.com/paper/1410.8546/) (2014)
- [Synchronisation of Partial Multi-Matchings via Non-negative Factorisations](https://mlsanity.com/paper/1803.06320/) (2018)
- [Structured Local Optima in Sparse Blind Deconvolution](https://mlsanity.com/paper/1806.00338/) (2018)
- [Convex Sparse Spectral Clustering: Single-view to Multi-view](https://mlsanity.com/paper/1511.06860/) (2015)
- [Finding the Sparsest Vectors in a Subspace: Theory, Algorithms, and Applications](https://mlsanity.com/paper/2001.06970/) (2020)
- [Sparse Generalized Eigenvalue Problem via Smooth Optimization](https://mlsanity.com/paper/1408.6686/) (2014)
- [Blind Data Detection in Massive MIMO via ℓ3-norm Maximization over the Stiefel Manifold](https://mlsanity.com/paper/2004.12301/) (2020)

## Built on by (most cited first, 6 of 6)

- [C2M3: Cycle-Consistent Multi-Model Merging](https://mlsanity.com/paper/2405.17897/) (2024)
- [Beyond Complete Shapes: A Benchmark for Quantitative Evaluation of 3D Shape Surface Matching Algorithms](https://mlsanity.com/paper/2411.03511/) (2024)
- [Kernelized multi-graph matching](https://mlsanity.com/paper/2210.05206/) (2022)
- [Optimizing Incomplete, Large-Scale and Sparse Multi-Graph Matching in Bioimaging](https://mlsanity.com/paper/2406.18215/) (2024)
- [Non-Negative Spherical Relaxations for Universe-Free Multi-Matching and Clustering](https://mlsanity.com/paper/2310.13311/) (2023)
- [Normalized Matching Transformer](https://mlsanity.com/paper/2503.17715/) (2025)

## Abstract (arXiv)

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.