A Caltech Library Service

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

Stojnic, M. and Vikalo, H. and Hassibi, B. (2005) An H-infinity based lower bound to speed up the sphere decoder. In: IEEE 6th Workshop on Signal Processing Advances in Wireless Communications. IEEE , Piscataway, NJ, pp. 751-755. ISBN 0-7803-8867-4.

[img] PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Additional Information:© 2005 IEEE. This work was supported in part by the National Science Foundation under grant no. CCR-0133818, by the Office of Naval Research under grant no. N00014-02-1-0578, and by Caltech's Lee Center for Advanced Networking.
Funding AgencyGrant Number
Office of Naval Research (ONR)N00014-02-1-0578
Caltech Lee Center for Advanced NetworkingUNSPECIFIED
Record Number:CaltechAUTHORS:20150210-071542063
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:54621
Deposited By: Shirley Slattery
Deposited On:11 Feb 2015 00:16
Last Modified:10 Nov 2021 20:36

Repository Staff Only: item control page