Premium
An efficient algorithm for clustered integer least squares problems
Author(s) -
Chun Joohwan,
Park Jaehyun
Publication year - 2012
Publication title -
numerical linear algebra with applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.02
H-Index - 53
eISSN - 1099-1506
pISSN - 1070-5325
DOI - 10.1002/nla.768
Subject(s) - decoupling (probability) , integer (computer science) , algorithm , decoding methods , mathematics , computer science , control engineering , engineering , programming language
SUMMARY The integer least squares problem is known to be NP‐hard, and the algorithms such as the sphere decoding algorithm, which give the optimal solution, are usually too slow. To obtain a solution efficiently one may use one of the suboptimal algorithms such as the ordered successive interference cancellation (OSIC) algorithm or the LLL‐aided OSIC algorithm that first modifies the system of equations using the LLL algorithm due to Lenstra, Lenstra, and Lovász. However, these suboptimal algorithms still may not be fast enough depending on the applications. In this paper we present two decoupling techniques to speed‐up the LLL‐aided OSIC algorithm. Our LLL‐aided decoupled OSIC algorithm, which is applicable to clustered integer least squares problems, has the accuracy comparable to the ordinary LLL‐aided OSIC algorithm (without decoupling), but is much faster than the OSIC algorithm or the LLL‐aided OSIC algorithm. Copyright © 2011 John Wiley & Sons, Ltd.