# Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable Approach for Continuous Markov Random Fields

arXiv: https://arxiv.org/abs/2107.06028 · HTML: https://mlsanity.com/paper/2107.06028/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 40 of its 343 references that are in the map.
- First posted on arXiv 13 Jul 2021.

## Builds on (most cited first, 30 of 40)

- [Image-based localization using LSTMs for structured feature correlation](https://mlsanity.com/paper/1611.07890/) (2016)
- [Learning Proximal Operators: Using Denoising Networks for Regularizing Inverse Imaging Problems](https://mlsanity.com/paper/1704.03488/) (2017)
- [Lipschitz constant estimation of Neural Networks via sparse polynomial optimization](https://mlsanity.com/paper/2004.08688/) (2020)
- [NeuroMorph: Unsupervised Shape Interpolation and Correspondence in One Go](https://mlsanity.com/paper/2106.09431/) (2021)
- [The Double Sphere Camera Model](https://mlsanity.com/paper/1807.08957/) (2018)
- [Full Flow: Optical Flow Estimation By Global Optimization over Regular Grids](https://mlsanity.com/paper/1604.03513/) (2016)
- [Associative Domain Adaptation](https://mlsanity.com/paper/1708.00938/) (2017)
- [Product Manifold Filter: Non-Rigid Shape Correspondence via Kernel Density Estimation in the Product Space](https://mlsanity.com/paper/1701.00669/) (2017)
- [Multi-View Deep Learning for Consistent Semantic Mapping with RGB-D Cameras](https://mlsanity.com/paper/1703.08866/) (2017)
- [Variational Data Assimilation with a Learned Inverse Observation Operator](https://mlsanity.com/paper/2102.11192/) (2021)
- [Submodular Functions: from Discrete to Continous Domains](https://mlsanity.com/paper/1511.00394/) (2015)
- [q-Space Novelty Detection with Variational Autoencoders](https://mlsanity.com/paper/1806.02997/) (2018)
- [Learning by Association - A versatile semi-supervised training method for neural networks](https://mlsanity.com/paper/1706.00909/) (2017)
- [Non-Rigid Puzzles](https://mlsanity.com/paper/2011.13076/) (2020)
- [Variational Uncalibrated Photometric Stereo under General Lighting](https://mlsanity.com/paper/1904.03942/) (2019)
- [Efficient Online Surface Correction for Real-time Large-Scale 3D Reconstruction](https://mlsanity.com/paper/1709.03763/) (2017)
- [Sparse Surface Constraints for Combining Physics-based Elasticity Simulation and Correspondence-Free Object Reconstruction](https://mlsanity.com/paper/1910.01812/) (2019)
- [Point-wise Map Recovery and Refinement from Functional Correspondence](https://mlsanity.com/paper/1506.05603/) (2015)
- [From Monocular SLAM to Autonomous Drone Exploration](https://mlsanity.com/paper/1609.07835/) (2016)
- [Sparse-BSOS: a bounded degree SOS hierarchy for large scale polynomial optimization with sparsity](https://mlsanity.com/paper/1607.01151/) (2016)
- [Photometric Depth Super-Resolution](https://mlsanity.com/paper/1809.10097/) (2018)
- [Inferring Super-Resolution Depth from a Moving Light-Source Enhanced RGB-D Sensor: A Variational Approach](https://mlsanity.com/paper/1912.06501/) (2019)
- [Spectral Decompositions using One-Homogeneous Functionals](https://mlsanity.com/paper/1601.02912/) (2016)
- [Learning Monocular 3D Vehicle Detection without 3D Bounding Box Labels](https://mlsanity.com/paper/2010.03506/) (2020)
- [Unsupervised Dense Shape Correspondence using Heat Kernels](https://mlsanity.com/paper/2010.12682/) (2020)
- [A Variational Approach to Shape-from-shading Under Natural Illumination](https://mlsanity.com/paper/1709.10354/) (2017)
- [Collaborative Total Variation: A General Framework for Vectorial TV Models](https://mlsanity.com/paper/1508.01308/) (2015)
- [A Combinatorial Solution to Non-Rigid 3D Shape-to-Image Matching](https://mlsanity.com/paper/1611.05241/) (2016)
- [Dense Multi-view 3D-reconstruction Without Dense Correspondences](https://mlsanity.com/paper/1704.00337/) (2017)
- [Total variation regularization for manifold-valued data](https://mlsanity.com/paper/1312.7710/) (2013)

## Built on by (most cited first, 1 of 1)

- [SAM as an Optimal Relaxation of Bayes](https://mlsanity.com/paper/2210.01620/) (2022)

## Abstract (arXiv)

Dual decomposition approaches in nonconvex optimization may suffer from a duality gap. This poses a challenge when applying them directly to nonconvex problems such as MAP-inference in a Markov random field (MRF) with continuous state spaces. To eliminate such gaps, this paper considers a reformulation of the original nonconvex task in the space of measures. This infinite-dimensional reformulation is then approximated by a semi-infinite one, which is obtained via a piecewise polynomial discretization in the dual. We provide a geometric intuition behind the primal problem induced by the dual discretization and draw connections to optimization over moment spaces. In contrast to existing discretizations which suffer from a grid bias, we show that a piecewise polynomial discretization better preserves the continuous nature of our problem. Invoking results from optimal transport theory and convex algebraic geometry we reduce the semi-infinite program to a finite one and provide a practical implementation based on semidefinite programming. We show, experimentally and in theory, that the approach successfully reduces the duality gap. To showcase the scalability of our approach, we apply it to the stereo matching problem between two images.