Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Robust binary least squares: Relaxations and algorithms
KTH, School of Electrical Engineering (EES), Signal Processing. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.
KTH, School of Electrical Engineering (EES), Signal Processing. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.ORCID iD: 0000-0001-6630-243X
KTH, School of Electrical Engineering (EES), Signal Processing. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre. (Signal Processing)ORCID iD: 0000-0003-2298-6774
2011 (English)In: ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing, 2011, 3780-3783 p.Conference paper, Published paper (Refereed)
Abstract [en]

Finding the least squares (LS) solution s to a system of linear equations Hs = y where H, y are given and s is a vector of binary variables, is a well known NP-hard problem. In this paper, we consider binary LS problems under the assumption that the coefficient matrix H is also unknown, and lies in a given uncertainty ellipsoid. We show that the corresponding worst-case robust optimization problem, although NP-hard, is still amenable to semidefinite relaxation (SDR)-based approximations. However, the relaxation step is not obvious, and requires a certain problem reformulation to be efficient. The proposed relaxation is motivated using Lagrangian duality and simulations suggest that it performs well, offering a robust alternative over the traditional SDR approaches for binary LS problems.

Place, publisher, year, edition, pages
2011. 3780-3783 p.
Series
International Conference on Acoustics Speech and Signal Processing ICASSP, ISSN 1520-6149
Keyword [en]
Binary least squares, semidefinite relaxation, robustness, Lagrange duality
National Category
Signal Processing
Identifiers
URN: urn:nbn:se:kth:diva-46331DOI: 10.1109/ICASSP.2011.5947174ISI: 000296062404073Scopus ID: 2-s2.0-80051629343ISBN: 978-1-4577-0538-0 (print)ISBN: 978-1-4577-0537-3 (print)OAI: oai:DiVA.org:kth-46331DiVA: diva2:453672
Conference
36th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2011. Prague. 22 May 2011 through 27 May 2011
Note
QC 20111111Available from: 2011-11-03 Created: 2011-11-03 Last updated: 2012-01-22Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Authority records BETA

Jaldén, JoakimOttersten, Björn

Search in DiVA

By author/editor
Tsakonas, EfthymiosJaldén, JoakimOttersten, Björn
By organisation
Signal ProcessingACCESS Linnaeus Centre
Signal Processing

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 92 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf