Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1109/ICASSP.2011.5947174 | ICASSP |
Keywords | Field | DocType |
approximation algorithms,robust optimization,signal processing,np hard problem,linear equations,robustness,uncertainty,least square,least squares approximation,optimization | Least squares,Approximation algorithm,Mathematical optimization,Ellipsoid,Coefficient matrix,System of linear equations,Robust optimization,Algorithm,Robustness (computer science),Mathematics,Binary number | Conference |
ISSN | ISBN | Citations |
1520-6149 E-ISBN : 978-1-4577-0537-3 | 978-1-4577-0537-3 | 0 |
PageRank | References | Authors |
0.34 | 6 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Efthymios Tsakonas | 1 | 15 | 3.50 |
| Joakim Jalden | 2 | 243 | 21.59 |
| Björn E. Ottersten | 3 | 6418 | 575.28 |