Robust binary least squares: Relaxations and algorithms
2011 (English)In: ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing, 2011, 3780-3783 p.Conference paper (Refereed)
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.
, International Conference on Acoustics Speech and Signal Processing ICASSP, ISSN 1520-6149
Binary least squares, semideﬁnite relaxation, robustness, Lagrange duality
IdentifiersURN: urn:nbn:se:kth:diva-46331DOI: 10.1109/ICASSP.2011.5947174ISI: 000296062404073ScopusID: 2-s2.0-80051629343ISBN: 978-1-4577-0538-0ISBN: 978-1-4577-0537-3OAI: oai:DiVA.org:kth-46331DiVA: diva2:453672
36th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2011. Prague. 22 May 2011 through 27 May 2011
QC 201111112011-11-032011-11-032012-01-22Bibliographically approved