mlsanityData to 14 Oct 2026

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

arXiv 1711.10733 ↗First posted 29 Nov 2017math.OC cs.CV stat.MLcited by 20

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 8; 2022: 5; 2023: 2; 2024: 3; 2025: 1; 2026: 1.

20 papers.

Sort:

  1. 2021A comprehensive survey on point cloud registrationcited by 84
  2. 2021Q-Match: Iterative Shape Matching via Quantum Annealingcited by 27
  3. 2021Semi-relaxed Gromov-Wasserstein divergence with applications on graphscited by 21
  4. 2021Adiabatic Quantum Graph Matching with Permutation Matrix Constraintscited by 20
  5. 2022A Scalable Combinatorial Solver for Elastic Geometrically Consistent 3D Shape Matchingcited by 19
  6. 2021Fusion Moves for Graph Matchingcited by 16
  7. 2024Partial-to-Partial Shape Matching with Geometric Consistencycited by 16
  8. 2022Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary Optimizationcited by 8
  9. 2024FSW-GNN: A Bi-Lipschitz WL-Equivalent Graph Neural Networkcited by 8
  10. 2021Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisationcited by 6
  11. 2022Conjugate Product Graphs for Globally Optimal 2D-3D Shape Matchingcited by 6
  12. 2023Kissing to Find a Match: Efficient Low-Rank Permutation Representationcited by 5
8 more
  1. 2022Structured Prediction Problem Archivecited by 4
  2. 2023SIGMA: Scale-Invariant Global Sparse Shape Matchingcited by 4
  3. 2021Joint Deep Multi-Graph Matching and 3D Geometry Learning from Inhomogeneous 2D Image Collectionscited by 3
  4. 2022Learning Universe Model for Partial Matching Networks over Multiple Graphscited by 2
  5. 2024Optimizing Incomplete, Large-Scale and Sparse Multi-Graph Matching in Bioimagingcited by 2
  6. 2021Convex Joint Graph Matching and Clustering via Semidefinite Relaxationscited by 1
  7. 2025FRAM: Frobenius-Regularized Assignment Matching with Mixed-Precision Computingcited by 0
  8. 2026Towards Metric-Faithful Neural Graph Matchingcited by 0