Accelerated Inference in Markov Random Fields via Smooth Riemannian Optimization

作     者：Hu, Siyi Carlone, Luca 

作者机构：MIT Informat & Decis Syst Lab Cambridge MA 02139 USA 

出 版 物：《IEEE ROBOTICS AND AUTOMATION LETTERS》 (IEEE Robot. Autom.)

年 卷 期：2019年第4卷第2期

页      面：1295-1302页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0811[工学-控制科学与工程] 

基　　金：Army Research Laboratory's Distributed and Collaborative Intelligent Systems and Technology Collaborative Research Alliance [W911NF-17-2-0181] Office of Naval Research through Project "Resilient Actionable Intelligence for Distributed Environment understanding and Reasoning" [N00014-18-1-2828] MIT Lincoln Laboratory 

主　　题：Object detection segmentation and categorization optimization and optimal control recognition 

摘      要：Markov random fields (MRFs) are a popular model for several pattern recognition and reconstruction problems in robotics and computer vision. Inference in MRFs is intractable in general and related work resorts to approximation algorithms. Among those techniques, semidefinite programming (SDP) relaxations have been shown to provide accurate estimates, while scaling poorly with the problem size and being typically slow for practical applications. Our first contribution is to design a dual ascent method to solve standard SDP relaxations that takes advantage of the geometric structure of the problem to speed up computation. This technique, named dual ascent Riemannian staircase (DARS), is able to solve large problem instances in seconds. Our second contribution is to develop a second and faster approach. The backbone of this second approach is a novel SDP relaxation combined with a fast and scalable solver based on smooth Riemannian optimization. We show that this approach, named Fast Unconstrained SEmidefinite Solver (FUSES), can solve large problems in milliseconds. Contrarily to local MRF solvers, e.g., loopy belief propagation, our approaches do not require an initial guess. Moreover, we leverage recent results from optimization theory to provide per-instance sub-optimality guarantees. We demonstrate the proposed approaches in multi-class image segmentation problems. Extensive experimental evidence shows that: 1) FUSES and DARS produce near-optimal solutions, attaining an objective within 0.1% of the optimum;2) FUSES and DARS are remarkably faster than general-purpose SDP solvers, and FUSES is more than two orders of magnitude faster than DARS while attaining similar solution quality;and 3) FUSES is faster than local search methods while being a global solver.