# Kissing to Find a Match: Efficient Low-Rank Permutation Representation

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 52 references that are in the map.
- First posted on arXiv 25 Aug 2023.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Learning from Synthetic Humans](https://mlsanity.com/paper/1701.01370/) (2017)
- [Learning Latent Permutations with Gumbel-Sinkhorn Networks](https://mlsanity.com/paper/1802.08665/) (2018)
- [3D-CODED : 3D Correspondences by Deep Deformation](https://mlsanity.com/paper/1806.05228/) (2018)
- [Deep Functional Maps: Structured Prediction for Dense Shape Correspondence](https://mlsanity.com/paper/1704.08686/) (2017)
- [FLOT: Scene Flow on Point Clouds Guided by Optimal Transport](https://mlsanity.com/paper/2007.11142/) (2020)
- [Stochastic Optimization of Sorting Networks via Continuous Relaxations](https://mlsanity.com/paper/1903.08850/) (2019)
- [Neural Graph Matching Network: Learning Lawler's Quadratic Assignment Problem with Extension to Hypergraph and Multiple-graph Matching](https://mlsanity.com/paper/1911.11308/) (2019)
- [NeuroMorph: Unsupervised Shape Interpolation and Correspondence in One Go](https://mlsanity.com/paper/2106.09431/) (2021)
- [Correspondence Learning via Linearly-invariant Embedding](https://mlsanity.com/paper/2010.13136/) (2020)
- [Isometric Multi-Shape Matching](https://mlsanity.com/paper/2012.02689/) (2020)
- [DeepPermNet: Visual Permutation Learning](https://mlsanity.com/paper/1704.02729/) (2017)
- [Q-Match: Iterative Shape Matching via Quantum Annealing](https://mlsanity.com/paper/2105.02878/) (2021)
- [Efficient Deformable Shape Correspondence via Kernel Matching](https://mlsanity.com/paper/1707.08991/) (2017)
- [Self-Supervised Learning for Multimodal Non-Rigid 3D Shape Matching](https://mlsanity.com/paper/2303.10971/) (2023)
- [DS*: Tighter Lifting-Free Convex Relaxations for Quadratic Matching Problems](https://mlsanity.com/paper/1711.10733/) (2017)
- [Implicit field supervision for robust non-rigid shape matching](https://mlsanity.com/paper/2203.07694/) (2022)
- [Accelerated Algorithms for Nonlinear Matrix Decomposition with the ReLU function](https://mlsanity.com/paper/2305.08687/) (2023)
- [Improving the semidefinite programming bound for the kissing number by exploiting polynomial symmetry](https://mlsanity.com/paper/1609.05167/) (2016)

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

- [Non-Rigid 3D Shape Correspondences: From Foundations to Open Challenges and Opportunities](https://mlsanity.com/paper/2604.01274/) (2026)
- [Creating Sorted Grid Layouts with Gradient-based Optimization](https://mlsanity.com/paper/2503.02730/) (2025)
- [Permutation Learning with Only N Parameters: From SoftSort to Self-Organizing Gaussians](https://mlsanity.com/paper/2503.13051/) (2025)
- [Learning to Solve the Quadratic Assignment Problem with Warm-Started MCMC Finetuning](https://mlsanity.com/paper/2604.20109/) (2026)
- [Subzero matrix completion for sparse data analysis: large-scale learning of latent low-rank structure](https://mlsanity.com/paper/2608.21607/) (2026)

## Abstract (arXiv)

Permutation matrices play a key role in matching and assignment problems across the fields, especially in computer vision and robotics. However, memory for explicitly representing permutation matrices grows quadratically with the size of the problem, prohibiting large problem instances. In this work, we propose to tackle the curse of dimensionality of large permutation matrices by approximating them using low-rank matrix factorization, followed by a nonlinearity. To this end, we rely on the Kissing number theory to infer the minimal rank required for representing a permutation matrix of a given size, which is significantly smaller than the problem size. This leads to a drastic reduction in computation and memory costs, e.g., up to 3 orders of magnitude less memory for a problem of size n=20000, represented using 8.4×105 elements in two small matrices instead of using a single huge matrix with 4× 108 elements. The proposed representation allows for accurate representations of large permutation matrices, which in turn enables handling large problems that would have been infeasible otherwise. We demonstrate the applicability and merits of the proposed approach through a series of experiments on a range of problems that involve predicting permutation matrices, from linear and quadratic assignment to shape matching problems.