Robust binary least squares: Relaxations and algorithms

Tsakonas, Efthymios; Jaldén, Joakim; Ottersten, Björn

doi:10.1109/ICASSP,2011.5947174

Reference : Robust binary least squares: Relaxations and algorithms


	Document type :	Scientific congresses, symposiums and conference proceedings : Paper published in a book
	Discipline(s) :	Engineering, computing & technology : Computer science Engineering, computing & technology : Computer science
	To cite this reference:	http://hdl.handle.net/10993/7511

Title :	Robust binary least squares: Relaxations and algorithms
Language :	English
Author, co-author :	Tsakonas, Efthymios [> >]
	Jaldén, Joakim [> >]
	Ottersten, Björn [University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > >]
Publication date :	2011
Main document title :	Acoustics, Speech and Signal Processing (ICASSP), 2011 IEEE International Conference on
Publisher :	IEEE
Pages :	3780-3783
Peer reviewed :	Yes
Audience :	International
ISBN :	978-1-4577-0538-0
Event name :	Proceedings IEEE International Conference on Acoustics,Speech and Signal Processing (ICASSP)
Event date :	22-27 May 2011
Event place (city) :	Prague
Event country :	Czech Republic
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.
Target :	Others
Permalink :	http://hdl.handle.net/10993/7511
DOI :	10.1109/ICASSP,2011.5947174

File(s) associated to this reference

Fulltext file(s):

	File	Commentary	Version	Size	Access
Limited access	Robust binary least squares Relaxations and algorithms.pdf		Publisher postprint	192.54 kB	Request a copy

All documents in ORBi^lu are protected by a user license.

University of Luxembourg Library | Feedback | Legal notices