Advanced

Solving large scale binary quadratic problems: Spectral methods vs. Semidefinite programming

Olsson, Carl LU ; Eriksson, Anders P LU and Kahl, Fredrik LU (2007) IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2007 In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition p.1776-1783
Abstract
In this paper we introduce two new methods for solving binary quadratic problems. While spectral relaxation methods have been the workhorse subroutine for a wide variety of computer vision problems - segmentation, clustering, image restoration to name a few - it has recently been challenged by semidefinite programming (SDP) relaxations. In fact, it can be shown that SDP relaxations produce better lower bounds than spectral relaxations on binary problems with a quadratic objective junction. On the other hand, the computational complexity for SDP increases rapidly as the number of decision variables grows making them inapplicable to large scale problems. Our methods combine the merits of both spectral and SDP relaxations - better (lower)... (More)
In this paper we introduce two new methods for solving binary quadratic problems. While spectral relaxation methods have been the workhorse subroutine for a wide variety of computer vision problems - segmentation, clustering, image restoration to name a few - it has recently been challenged by semidefinite programming (SDP) relaxations. In fact, it can be shown that SDP relaxations produce better lower bounds than spectral relaxations on binary problems with a quadratic objective junction. On the other hand, the computational complexity for SDP increases rapidly as the number of decision variables grows making them inapplicable to large scale problems. Our methods combine the merits of both spectral and SDP relaxations - better (lower) bounds than traditional spectral methods and considerably faster execution times than SDP The first method is based on spectral subgradients and can be applied to large scale SDPs with binary decision variables and the second one is based on the trust region problem. Both algorithms have been applied to several large scale vision problems with good performance.<sup>1</sup> © 2007 IEEE. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
Semidefinite programming, Quadratic objective junctions, Binary problems
in
Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition
pages
1776 - 1783
publisher
IEEE--Institute of Electrical and Electronics Engineers Inc.
conference name
IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2007
external identifiers
  • wos:000250382803046
  • other:CODEN: PIVRE9
  • scopus:34948830670
ISSN
1063-6919
DOI
10.1109/CVPR.2007.383202
language
English
LU publication?
yes
id
07961d1b-072a-4f5e-b220-1c0adc8abd3f (old id 643507)
alternative location
http://www.maths.lth.se/matematiklth/personal/fredrik/olsson_cvpr07.pdf
date added to LUP
2007-12-04 11:45:02
date last changed
2017-10-22 04:35:37
@inproceedings{07961d1b-072a-4f5e-b220-1c0adc8abd3f,
  abstract     = {In this paper we introduce two new methods for solving binary quadratic problems. While spectral relaxation methods have been the workhorse subroutine for a wide variety of computer vision problems - segmentation, clustering, image restoration to name a few - it has recently been challenged by semidefinite programming (SDP) relaxations. In fact, it can be shown that SDP relaxations produce better lower bounds than spectral relaxations on binary problems with a quadratic objective junction. On the other hand, the computational complexity for SDP increases rapidly as the number of decision variables grows making them inapplicable to large scale problems. Our methods combine the merits of both spectral and SDP relaxations - better (lower) bounds than traditional spectral methods and considerably faster execution times than SDP The first method is based on spectral subgradients and can be applied to large scale SDPs with binary decision variables and the second one is based on the trust region problem. Both algorithms have been applied to several large scale vision problems with good performance.&lt;sup&gt;1&lt;/sup&gt; © 2007 IEEE.},
  author       = {Olsson, Carl and Eriksson, Anders P and Kahl, Fredrik},
  booktitle    = {Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition},
  issn         = {1063-6919},
  keyword      = {Semidefinite programming,Quadratic objective junctions,Binary problems},
  language     = {eng},
  pages        = {1776--1783},
  publisher    = {IEEE--Institute of Electrical and Electronics Engineers Inc.},
  title        = {Solving large scale binary quadratic problems: Spectral methods vs. Semidefinite programming},
  url          = {http://dx.doi.org/10.1109/CVPR.2007.383202},
  year         = {2007},
}