Hassibi, Babak and Vikalo, Haris (2005) On the spheredecoding algorithm I. Expected complexity. IEEE Transactions on Signal Processing, 53 (8). pp. 28062818. ISSN 1053587X. http://resolver.caltech.edu/CaltechAUTHORS:HASieeetsp05

PDF
See Usage Policy. 475Kb 
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:HASieeetsp05
Abstract
The problem of finding the leastsquares solution to a system of linear equations where the unknown vector is comprised of integers, but the matrix coefficient and given vector are comprised of real numbers, arises in many applications: communications, cryptography, GPS, to name a few. The problem is equivalent to finding the closest lattice point to a given point and is known to be NPhard. In communications applications, however, the given vector is not arbitrary but rather is an unknown lattice point that has been perturbed by an additive noise vector whose statistical properties are known. Therefore, in this paper, rather than dwell on the worstcase complexity of the integer leastsquares problem, we study its expected complexity, averaged over the noise and over the lattice. For the "sphere decoding" algorithm of Fincke and Pohst, we find a closedform expression for the expected complexity, both for the infinite and finite lattice. It is demonstrated in the second part of this paper that, for a wide range of signaltonoise ratios (SNRs) and numbers of antennas, the expected complexity is polynomial, in fact, often roughly cubic. Since many communications systems operate at noise levels for which the expected complexity turns out to be polynomial, this suggests that maximumlikelihood decoding, which was hitherto thought to be computationally intractable, can, in fact, be implemented in real time  a result with many practical implications.
Item Type:  Article 

Additional Information:  © Copyright 2005 IEEE. Reprinted with permission. Manuscript received June 25, 2003; revised September 19, 2004. The associate editor coordinating the review of this manuscript and approving it for publication was Prof. Zhi Ding. 
Subject Keywords:  expected complexity; integer leastsquares problem; lattice problems; multipleantenna systems; NP hard; sphere decoding; wireless communications 
Record Number:  CaltechAUTHORS:HASieeetsp05 
Persistent URL:  http://resolver.caltech.edu/CaltechAUTHORS:HASieeetsp05 
Alternative URL:  http://dx.doi.org/10.1109/TSP.2005.850352 
Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided. 
ID Code:  1636 
Collection:  CaltechAUTHORS 
Deposited By:  Tony Diaz 
Deposited On:  08 Feb 2006 
Last Modified:  26 Dec 2012 08:45 
Repository Staff Only: item control page