Abstract
Correspondence problems are often modeled as quadratic optimization problems over permutations. Common scalable methods for approximating solutions of these NP-hard problems are the spectral relaxation for non-convex energies and the doubly stochastic (DS) relaxation for convex energies. Lately, it has been demonstrated that semidefinite programming (SDP) relaxations can have considerably improved accuracy at the price of a much higher computational cost. We present DS++, a convex quadratic programming relaxation which is provably stronger than both DS and spectral relaxations, with the same scalability as the DS relaxation. The derivation of the relaxation also naturally suggests a projection method for achieving meaningful integer solutions which improves upon the standard closest-permutation projection. Our method can be easily extended to optimization over doubly stochastic matrices, partial or injective matching, and problems with additional linear constraints. We present experiments indicating that our method is more accurate than local minimization or competing relaxations for non-convex problems, successfully applying it to shape matching and image grid ordering.
Introduction
At the heart of many computer vision and graphics tasks—such as 3D shape alignment or organizing image galleries—is the matching problem. Mathematically, this is modeled as finding a permutation matrix that minimizes a quadratic energy function. Because this problem is NP-hard, researchers typically choose between two extremes: scalable but loose relaxations (like Spectral or Doubly Stochastic methods) that often produce inaccurate results, or tight but slow relaxations (like Semidefinite Programming) that are limited to very small problem sizes due to $O(n^4)$ complexity.
DS++ bridges this gap by providing a relaxation that is provably stronger than fast methods without losing their efficiency, allowing for high-quality correspondences in problems involving thousands of points.
Methodology
DS++ is a convex quadratic programming relaxation that hinges on a mathematical "shift" in the energy function. The authors consider a family of energy functions $E(X, a)$ that are equivalent when $X$ is a permutation matrix but behave differently when $X$ is relaxed to a doubly stochastic matrix. The goal is to find the largest value of a parameter $a$ that maintains the convexity of the energy function.
The key innovation lies in identifying that the variable $X$ is constrained to a specific affine subspace (where rows and columns sum to one). By calculating the minimal eigenvalue specifically over this subspace rather than the entire matrix space, the authors can choose a much larger $a$. This results in a tighter relaxation that stays closer to the true integer solution. To convert the resulting fuzzy matrix back into a valid permutation, the authors employ a homotopy-type projection, gradually deforming the energy from convex to concave to push the solution toward the corners of the search space.
Key Insights and Hierarchy
The most significant theoretical contribution is the establishment of a hierarchy of tightness among relaxations. By focusing on the doubly stochastic subspace, DS++ achieves a tighter bound for free compared to previous methods like DS+.
As illustrated above, DS++ sits in a unique position: it is the strongest relaxation achievable while remaining within the $O(n^2)$ variable limit. This allows it to handle large-scale problems that are impossible for SDP solvers while maintaining superior accuracy over classical spectral methods.
Experimental Results
The authors evaluated DS++ across diverse domains, including non-rigid shape matching using the FAUST dataset and image arrangement using the SUN Database and LFW.
- Accuracy: In non-rigid matching on FAUST, DS++ achieved the global minimum in approximately 80% of experiments, compared to only 11% for standard spectral methods.
- Image Organization: In arranging images in a grid based on visual similarity, DS++ outperformed previous state-of-the-art methods by over 50% in some cases, creating more intuitive visual layouts.
- Scalability: While SDP methods are capped at roughly 30 points, DS++ successfully handled matching problems with up to 1,000 points in approximately six minutes.
Conclusion
DS++ represents a significant advancement in quadratic optimization over permutations. By leveraging the specific geometry of the doubly stochastic subspace, it provides a flexible and scalable tool that outperforms traditional relaxations. While it does not guarantee a global optimum for all NP-hard instances, its provable tightness and efficient performance make it a compelling choice for modern computer vision and graphics applications. Future work may involve exploring even tighter quadratic relaxations that remain within the $O(n^2)$ complexity limit.
Summary updated