An H-infinity based lower bound to speed up the sphere decoder

It is well known that maximum-likelihood (ML) decoding in many digital communication schemes reduces to solving an integer least problem, which is NP hard in the worst-case. On the other hand, it has recently been shown that, over a wide range of dimensions and signal-to-noise ratios (SNR), the sphere decoder can be used to find the exact solution with an expected complexity that is roughly cubic in the dimension of the problem. However, the computational complexity of sphere decoding becomes prohibitive if the SNR is too low and/or if the dimension of the problem is too large. In recent work M. Stonjic et al. (2005), we have targeted these two regimes and attempted to find faster algorithms by employing a branch-and-bound technique based on convex relaxations of the original integer least-squares problem. In this paper, using ideas from H^∞ estimation theory, we propose new lower bounds that are generally tighter than the ones obtained in M. Stonjic et al. (2005). Simulation results snow the advantages, in terms of computational complexity, of the new H^∞-based branch-and-bound algorithm over the ones based on convex relaxation, as well as the original sphere decoder.