The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

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

På svenska

Author

Summary, in English

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.

Publishing year

2007

Language

English

Pages

1776-1783

Publication/Series

Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition

Document type

Conference paper

Publisher

IEEE - Institute of Electrical and Electronics Engineers Inc.

Topic

  • Mathematics

Keywords

  • Semidefinite programming
  • Quadratic objective junctions
  • Binary problems

Conference name

IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2007

Conference date

2007-06-17 - 2007-06-22

Conference place

Minneapolis, MN, United States

Status

Published

ISBN/ISSN/Other

  • ISSN: 1063-6919
  • CODEN: PIVRE9