# Non-Negative Spherical Relaxations for Universe-Free Multi-Matching and Clustering

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 76 references that are in the map.
- First posted on arXiv 20 Oct 2023.

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

- [SpectralNet: Spectral Clustering using Deep Neural Networks](https://mlsanity.com/paper/1801.01587/) (2018)
- [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)
- [Near-Optimal Joint Object Matching via Convex Relaxation](https://mlsanity.com/paper/1402.1473/) (2014)
- [A Solution for Multi-Alignment by Transformation Synchronisation](https://mlsanity.com/paper/1410.8546/) (2014)
- [The Projected Power Method: An Efficient Algorithm for Joint Alignment from Pairwise Differences](https://mlsanity.com/paper/1609.05820/) (2016)
- [Synchronisation of Partial Multi-Matchings via Non-negative Factorisations](https://mlsanity.com/paper/1803.06320/) (2018)
- [Multi-Image Semantic Matching by Mining Consistent Features](https://mlsanity.com/paper/1711.07641/) (2017)
- [Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation](https://mlsanity.com/paper/2110.00053/) (2021)

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

- [Partial-to-Partial Shape Matching with Geometric Consistency](https://mlsanity.com/paper/2404.12209/) (2024)

## Abstract (arXiv)

We propose a novel non-negative spherical relaxation for optimization problems over binary matrices with injectivity constraints, which in particular has applications in multi-matching and clustering. We relax respective binary matrix constraints to the (high-dimensional) non-negative sphere. To optimize our relaxed problem, we use a conditional power iteration method to iteratively improve the objective function, while at same time sweeping over a continuous scalar parameter that is (indirectly) related to the universe size (or number of clusters). Opposed to existing procedures that require to fix the integer universe size before optimization, our method automatically adjusts the analogous continuous parameter. Furthermore, while our approach shares similarities with spectral multi-matching and spectral clustering, our formulation has the strong advantage that we do not rely on additional post-processing procedures to obtain binary results. Our method shows compelling results in various multi-matching and clustering settings, even when compared to methods that use the ground truth universe size (or number of clusters).