Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Conference paper
Title: New convex relaxations for MRF inference with unknown graphs
Author: Wang, Z.
Liu, T.
Shi, Q.
Kumar, M.
Zhang, J.
Citation: Proceedings: 2019 International Conference on Computer Vision, 2019 / vol.2019-October, pp.9934-9942
Publisher: IEEE
Publisher Place: Los Alamitos, California
Issue Date: 2019
Series/Report no.: IEEE International Conference on Computer Vision
ISBN: 9781728148038
ISSN: 1550-5499
Conference Name: IEEE International Conference on Computer Vision (ICCV) (27 Oct 2019 - 02 Nov 2019 : Seoul, South Korea)
Statement of
Zhenhua Wang, Tong Liu, Qinfeng Shi, M. Pawan Kumar, Jianhua Zhang
Abstract: Treating graph structures of Markov random fields as unknown and estimating them jointly with labels have been shown to be useful for modeling human activity recognition and other related tasks. We propose two novel relaxations for solving this problem. The first is a linear programming (LP) relaxation, which is provably tighter than the existing LP relaxation. The second is a non-convex quadratic programming (QP) relaxation, which admits an efficient concave-convex procedure (CCCP). The CCCP algorithm is initialized by solving a convex QP relaxation of the problem, which is obtained by modifying the diagonal of the matrix that specifies the non-convex QP relaxation. We show that our convex QP relaxation is optimal in the sense that it minimizes the L1 norm of the diagonal modification vector. While the convex QP relaxation is not as tight as the existing and the new LP relaxations, when used in conjunction with the CCCP algorithm for the non-convex QP relaxation, it provides accurate solutions. We demonstrate the efficacy of our new relaxations for both synthetic data and human activity recognition.
Rights: © 2019 IEEE
RMID: 1000020938
DOI: 10.1109/ICCV.2019.01003
Grant ID:
Appears in Collections:Computer Science publications

Files in This Item:
There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.