  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 semidefinite programming (SDP), each with their
own advantages and disadvantages. Spectral relaxation is simple and easy to
implement, but its bound is loose. Semidefinite 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.
