An efficient algorithm for clustered integer least squares problems

Abstract

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 Lovasz. 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 (C) 2011 John Wiley & Sons, Ltd.