A Caltech Library Service

Speeding up the Sphere Decoder With ℋ∞ and SDP Inspired Lower Bounds

Stojnic, Mihailo and Vikalo, Haris and Hassibi, Babak (2008) Speeding up the Sphere Decoder With ℋ∞ and SDP Inspired Lower Bounds. IEEE Transactions on Signal Processing, 56 (2). pp. 712-726. ISSN 1053-587X. doi:10.1109/TSP.2007.906697.

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-squares 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 (SNRs), the sphere decoding algorithm can be used to find the exact ML solution with an expected complexity that is often less than N^3. 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 this paper, we target these two regimes and attempt to find faster algorithms by pruning the search tree beyond what is done in the standard sphere decoding algorithm. The search tree is pruned by computing lower bounds on the optimal value of the objective function as the algorithm proceeds to descend down the search tree. We observe a tradeoff between the computational complexity required to compute a lower bound and the size of the pruned tree: the more effort we spend in computing a tight lower bound, the more branches that can be eliminated in the tree. Using ideas from semidefinite program (SDP)-duality theory and H∞ estimation theory, we propose general frameworks for computing lower bounds on integer least-squares problems. We propose two families of algorithms, one that is appropriate for large problem dimensions and binary modulation, and the other that is appropriate for moderate-size dimensions yet high-order constellations. We then show how in each case these bounds can be efficiently incorporated in the sphere decoding algorithm, often resulting in significant improvement of the expected complexity of solving the ML decoding problem, while maintaining the exact ML-performance.

Item Type:Article
Related URLs:
URLURL TypeDescription
Alternate Title:Speeding up the Sphere Decoder With H∞ and SDP Inspired Lower Bounds
Additional Information:© 2008 IEEE. Manuscript received September 3, 2006; revised May 11, 2007. This work was supported in part by the National Science Foundation under grant CCR-0133818, by the David and Lucille Packard Foundation, and by Caltech’s Lee Center for Advanced Networking.
Funding AgencyGrant Number
David and Lucile Packard FoundationUNSPECIFIED
Caltech Lee Center for Advanced NetworkingUNSPECIFIED
Subject Keywords:Branch-and-bound algorithm, H∞ estimation, convex optimization, expected complexity, integer least-squares, maximum-likelihood (ML) detection, sphere decoding
Issue or Number:2
Record Number:CaltechAUTHORS:STOieeetsp08
Persistent URL:
Official Citation:M. Stojnic, H. Vikalo and B. Hassibi, "Speeding up the Sphere Decoder With H∞ and SDP Inspired Lower Bounds," in IEEE Transactions on Signal Processing, vol. 56, no. 2, pp. 712-726, Feb. 2008. doi: 10.1109/TSP.2007.906697
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:9567
Deposited By: Archive Administrator
Deposited On:05 Feb 2008
Last Modified:08 Nov 2021 21:00

Repository Staff Only: item control page