# DS*: Tighter Lifting-Free Convex Relaxations for Quadratic Matching Problems

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Nov 2017.

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

- [A comprehensive survey on point cloud registration](https://mlsanity.com/paper/2103.02690/) (2021)
- [Q-Match: Iterative Shape Matching via Quantum Annealing](https://mlsanity.com/paper/2105.02878/) (2021)
- [Semi-relaxed Gromov-Wasserstein divergence with applications on graphs](https://mlsanity.com/paper/2110.02753/) (2021)
- [Adiabatic Quantum Graph Matching with Permutation Matrix Constraints](https://mlsanity.com/paper/2107.04032/) (2021)
- [A Scalable Combinatorial Solver for Elastic Geometrically Consistent 3D Shape Matching](https://mlsanity.com/paper/2204.12805/) (2022)
- [Fusion Moves for Graph Matching](https://mlsanity.com/paper/2101.12085/) (2021)
- [Partial-to-Partial Shape Matching with Geometric Consistency](https://mlsanity.com/paper/2404.12209/) (2024)
- [Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary Optimization](https://mlsanity.com/paper/2203.12633/) (2022)
- [FSW-GNN: A Bi-Lipschitz WL-Equivalent Graph Neural Network](https://mlsanity.com/paper/2410.09118/) (2024)
- [Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation](https://mlsanity.com/paper/2110.00053/) (2021)
- [Conjugate Product Graphs for Globally Optimal 2D-3D Shape Matching](https://mlsanity.com/paper/2211.11589/) (2022)
- [Kissing to Find a Match: Efficient Low-Rank Permutation Representation](https://mlsanity.com/paper/2308.13252/) (2023)
- [Structured Prediction Problem Archive](https://mlsanity.com/paper/2202.03574/) (2022)
- [SIGMA: Scale-Invariant Global Sparse Shape Matching](https://mlsanity.com/paper/2308.08393/) (2023)
- [Joint Deep Multi-Graph Matching and 3D Geometry Learning from Inhomogeneous 2D Image Collections](https://mlsanity.com/paper/2103.17229/) (2021)
- [Learning Universe Model for Partial Matching Networks over Multiple Graphs](https://mlsanity.com/paper/2210.10374/) (2022)
- [Optimizing Incomplete, Large-Scale and Sparse Multi-Graph Matching in Bioimaging](https://mlsanity.com/paper/2406.18215/) (2024)
- [Convex Joint Graph Matching and Clustering via Semidefinite Relaxations](https://mlsanity.com/paper/2110.11335/) (2021)
- [FRAM: Frobenius-Regularized Assignment Matching with Mixed-Precision Computing](https://mlsanity.com/paper/2508.00887/) (2025)
- [Towards Metric-Faithful Neural Graph Matching](https://mlsanity.com/paper/2605.06588/) (2026)

## Abstract (arXiv)

In this work we study convex relaxations of quadratic optimisation problems over permutation matrices. While existing semidefinite programming approaches can achieve remarkably tight relaxations, they have the strong disadvantage that they lift the original n × n-dimensional variable to an n2 × n2-dimensional variable, which limits their practical applicability. In contrast, here we present a lifting-free convex relaxation that is provably at least as tight as existing (lifting-free) convex relaxations. We demonstrate experimentally that our approach is superior to existing convex and non-convex methods for various problems, including image arrangement and multi-graph matching.