New Convex Relaxations for MRF Inference with Unknown Graphs
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.
Cite
Text
Wang et al. "New Convex Relaxations for MRF Inference with Unknown Graphs." Proceedings of the IEEE/CVF International Conference on Computer Vision, 2019. doi:10.1109/ICCV.2019.01003Markdown
[Wang et al. "New Convex Relaxations for MRF Inference with Unknown Graphs." Proceedings of the IEEE/CVF International Conference on Computer Vision, 2019.](https://mlanthology.org/iccv/2019/wang2019iccv-new/) doi:10.1109/ICCV.2019.01003BibTeX
@inproceedings{wang2019iccv-new,
title = {{New Convex Relaxations for MRF Inference with Unknown Graphs}},
author = {Wang, Zhenhua and Liu, Tong and Shi, Qinfeng and Kumar, M. Pawan and Zhang, Jianhua},
booktitle = {Proceedings of the IEEE/CVF International Conference on Computer Vision},
year = {2019},
doi = {10.1109/ICCV.2019.01003},
url = {https://mlanthology.org/iccv/2019/wang2019iccv-new/}
}