A Study of Lagrangean Decompositions and Dual Ascent Solvers for Graph Matching
We study the quadratic assignment problem, in computer vision also known as graph matching. Two leading solvers for this problem optimize the Lagrange decomposition duals with sub-gradient and dual ascent (also known as message passing) updates. We explore s direction further and propose several additional Lagrangean relaxations of the graph matching problem along with corresponding algorithms, which are all based on a common dual ascent framework. Our extensive empirical evaluation gives several theoretical insights and suggests a new state-of-the-art any-time solver for the considered problem. Our improvement over state-of-the-art is particularly visible on a new dataset with large-scale sparse problem instances containing more than 500 graph nodes each.
Code (1)
Tasks
Graph MatchingSimilar Papers 제목 키워드 기반
A Dual Ascent Framework for Lagrangean Decomposition of Combinatorial Problems
We propose a general dual ascent framework for Lagrangean decomposition of combinatorial problems. Although methods of this type have shown their efficiency for a number of problems, so far there was no general algorithm…
Graph MatchingTaxonomy of Dual Block-Coordinate Ascent Methods for Discrete Energy Minimization
We consider the maximum-a-posteriori inference problem in discrete graphical models and study solvers based on the dual block-coordinate ascent rule. We map all existing solvers in a single framework, allowing for a bett…
MAP inference via Block-Coordinate Frank-Wolfe Algorithm
We present a new proximal bundle method for Maximum-A-Posteriori (MAP) inference in structured energy minimization problems. The method optimizes a Lagrangean relaxation of the original energy minimization problem using …
Graph MatchingDual SVM Training on a Budget
We present a dual subspace ascent algorithm for support vector machine training that respects a budget constraint limiting the number of support vectors. Budget methods are effective for reducing the training time of ker…
MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical Models
Dense, discrete Graphical Models with pairwise potentials are a powerful class of models which are employed in state-of-the-art computer vision and bio-imaging applications. This work introduces a new MAP-solver, based o…
6D Pose Estimation using RGBCPUGPUPose Estimation