Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Conference paper
Title: A fast semidefinite approach to solving binary quadratic problems
Author: Wang, P.
Shen, C.
Van Den Hengel, A.
Citation: Proceedings, 2013 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2013, 23-28 June 2013, Portland, Oregon, USA: pp. 1312-1319
Publisher: IEEE
Publisher Place: United States
Issue Date: 2013
Series/Report no.: IEEE Conference on Computer Vision and Pattern Recognition
ISBN: 9780769549897
ISSN: 1063-6919
Conference Name: IEEE Conference on Computer Vision and Pattern Recognition (26th : 2013 : Portland, Oregon)
Statement of
Peng Wang, Chunhua Shen, Anton van den Hengel
Abstract: Many computer vision problems can be formulated as binary quadratic programs (BQPs). Two classic relaxation methods are widely used for solving BQPs, namely, spectral methods and semi definite programming (SDP), each with their own advantages and disadvantages. Spectral relaxation is simple and easy to implement, but its bound is loose. Semi definite relaxation has a tighter bound, but its computational complexity is high for large scale problems. We present a new SDP formulation for BQPs, with two desirable properties. First, it has a similar relaxation bound to conventional SDP formulations. Second, compared with conventional SDP methods, the new SDP formulation leads to a significantly more efficient and scalable dual optimization approach, which has the same degree of complexity as spectral methods. Extensive experiments on various applications including clustering, image segmentation, co-segmentation and registration demonstrate the usefulness of our SDP formulation for solving large-scale BQPs.
Rights: © 2013 IEEE
RMID: 0020132970
DOI: 10.1109/CVPR.2013.173
Description (link):
Appears in Collections:Computer Science publications

Files in This Item:
File Description SizeFormat 
RA_hdl_82691.pdfRestricted Access1.31 MBAdobe PDFView/Open

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