Available on ORBilu since
03 October 2013
Paper published in a book (Scientific congresses, symposiums and conference proceedings)
Robust binary least squares: Relaxations and algorithms
Tsakonas, Efthymios; Jaldén, Joakim; Ottersten, Björn
2011In Acoustics, Speech and Signal Processing (ICASSP), 2011 IEEE International Conference on
Peer reviewed


Full Text
Robust binary least squares Relaxations and algorithms.pdf
Publisher postprint (197.16 kB)

All documents in ORBilu are protected by a user license.

Send to


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.
Disciplines :
Computer science
Computer science
Identifiers :
Author, co-author :
Tsakonas, Efthymios
Jaldén, Joakim
Ottersten, Björn ;  University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT)
Language :
Title :
Robust binary least squares: Relaxations and algorithms
Publication date :
Event name :
Proceedings IEEE International Conference on Acoustics,Speech and Signal Processing (ICASSP)
Event place :
Prague, Czechia
Event date :
22-27 May 2011
Audience :
Main work title :
Acoustics, Speech and Signal Processing (ICASSP), 2011 IEEE International Conference on
Publisher :
Pages :
Peer reviewed :
Peer reviewed


Number of views
110 (0 by Unilu)
Number of downloads
0 (0 by Unilu)


Similar publications

Contact ORBilu