DS++: a flexible, scalable and provably tight relaxation for matching problems

Nadav Dym, Haggai Maron, Yaron Lipman

TL;DR

DS++ is a new convex quadratic programming relaxation for matching problems that is provably tighter than both classical spectral and doubly-stochastic (DS) relaxations. By optimizing over a specific affine subspace, the authors achieve near-semidefinite programming (SDP) accuracy while maintaining the scalability of simpler methods, allowing for high-quality correspondences in shapes and images with thousands of points.

What Problem Does This Paper Address?

At the heart of many computer vision and graphics tasks—like 3D shape alignment or organizing image galleries—is the matching problem. Mathematically, this is often modeled as finding a permutation matrix that minimizes a quadratic energy function.

The catch? This is an NP-hard problem. Researchers usually take one of two paths:

  1. Scalable but loose relaxations: Methods like "Spectral" or "Doubly Stochastic" (DS) relaxations are fast but often produce "fuzzy" or inaccurate results because they don't approximate the original problem tightly enough.
  2. Tight but slow relaxations: Semidefinite Programming (SDP) offers incredible accuracy but collapses under its own weight for large problems, often limited to just a few dozen points due to $O(n^4)$ complexity.

The authors of DS++ set out to bridge this gap: Can we build a relaxation that is provably stronger than the fast methods without losing their efficiency?

Methods

The authors introduce DS++, a convex quadratic programming relaxation. Their approach hinges on a clever mathematical "shift."

They consider a family of energy functions $E(X, a)$ that all look the same when $X$ is a permutation matrix but behave differently when $X$ is "relaxed" (allowed to be a fuzzy, doubly stochastic matrix). The goal is to find the largest value of a parameter $a$ that keeps the energy function convex.

The Key Innovation: While previous work (like DS+) chose $a$ based on the global minimal eigenvalue of the energy matrix, DS++ identifies that the variable $X$ is actually constrained to a specific affine subspace (the set of matrices where rows and columns sum to one). By calculating the minimal eigenvalue specifically over this subspace, they can choose a much larger $a$. This results in a "tighter" relaxation—one that stays closer to the true integer solution.

To turn the resulting fuzzy matrix back into a real permutation, they use a homotopy-type projection. They gradually deform the energy from convex to concave, "pushing" the solution toward the corners of the search space until it becomes a valid permutation.

Datasets

The authors evaluated DS++ across several diverse domains:

  • FAUST: A dataset of raw 3D scans of human bodies used for non-rigid shape matching.
  • SUN Database: Used for the "image arrangement" task, where thousands of images are organized into a 2D grid based on visual similarity.
  • LFW (Labeled Faces in the Wild): Used to test image arrangement using deep features from face recognition networks.
  • SHREC07 & SHREC: Used for 3D model arrangement and coarse-to-fine matching with sparse user constraints.

Key Insights and Ideas

  • The Subspace Matters: The most important "aha" moment is that the constraints of the problem (doubly stochastic matrices) define a much smaller space than the general matrix space. Ignoring this leads to "loose" relaxations. By focusing on the doubly stochastic subspace, DS++ gets a tighter bound for free.
  • The Hierarchy of Tightness: The paper proves a clear hierarchy: Spectral/DS < DS+ < DS++ < SDP. DS++ sits in the "sweet spot"—it’s the strongest relaxation you can get while still using only $n^2$ variables.
  • Convex-to-Concave is Better than Simple Projection: Instead of just snapping the fuzzy result to the nearest permutation (Euclidean projection), the homotopy method uses the energy landscape to find a better local minimum, significantly improving final accuracy.

Key Results

  • Accuracy: In non-rigid matching on the FAUST dataset, DS++ achieved the global minimum in approximately 80% of experiments, compared to only 11% for standard spectral methods.
  • Image Organization: In the task of arranging images in a grid (e.g., clustering similar faces or objects), DS++ outperformed the previous state-of-the-art by over 50% in some cases, creating much more intuitive visual layouts.
  • Scalability: While SDP methods are capped at around 15-30 points, DS++ handled matching problems with up to 1,000 points in about six minutes. For specific types of energy (like Gromov-Wasserstein), it can leverage $O(n^3)$ solvers to be even faster.

Limitations and Future Work

The primary limitation acknowledged is that DS++ is still a relaxation; it does not guarantee the global optimum of the original NP-hard problem. While it is much tighter than DS+, it is still not as accurate as the extremely expensive $O(n^4)$ SDP relaxations.

The authors suggest that a promising future direction is searching for the "best" possible quadratic programming relaxation that stays within the $O(n^2)$ variable limit, potentially closing the remaining gap with SDP methods.

Summary updated

Abstract

Correspondence problems are often modelled 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 relaxations can have considerably improved accuracy at the price of a much higher computational cost. We present 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, injective matching, and problems with additional linear constraints. We employ recent advances in optimization of linear-assignment type problems to achieve an efficient algorithm for solving the convex relaxation. We present experiments indicating that our method is more accurate than local minimization or competing relaxations for non-convex problems. We successfully apply our algorithm to shape matching and to the problem of ordering images in a grid, obtaining results which compare favorably with state of the art methods. We believe our results indicate that our method should be considered the method of choice for quadratic optimization over permutations.
BibTeX
@article{dym2017ds,
  author = {Nadav Dym and Haggai Maron and Yaron Lipman},
  title = {{DS++: a flexible, scalable and provably tight relaxation for matching problems}},
  journal = {ACM Trans. Graphics},
  year = {2017},
  url = {https://openreview.net/forum?id=3W4WQSCbJPz},
}

Loading related content...

Figure