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
 

Files


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



Details



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 :
UNILU:UL-CONFERENCE-2011-426
Author, co-author :
Tsakonas, Efthymios
Jaldén, Joakim
Ottersten, Björn ;  University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT)
Language :
English
Title :
Robust binary least squares: Relaxations and algorithms
Publication date :
2011
Event name :
Proceedings IEEE International Conference on Acoustics,Speech and Signal Processing (ICASSP)
Event place :
Prague, Czechia
Event date :
22-27 May 2011
Audience :
International
Main work title :
Acoustics, Speech and Signal Processing (ICASSP), 2011 IEEE International Conference on
Publisher :
IEEE
ISBN/EAN :
978-1-4577-0538-0
Pages :
3780-3783
Peer reviewed :
Peer reviewed

Statistics


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

Bibliography


Similar publications



Contact ORBilu