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:
- 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.
- 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