CaltechAUTHORS
  A Caltech Library Service

On the expected complexity of integer least-squares problems

Hassibi, Babak and Vikalo, Haris (2002) On the expected complexity of integer least-squares problems. In: 2002 IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP). Vol.2. IEEE , Piscataway, NJ, pp. 1497-1500. ISBN 0-7803-7402-9. https://resolver.caltech.edu/CaltechAUTHORS:20150212-073945154

[img] PDF - Published Version
See Usage Policy.

417kB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20150212-073945154

Abstract

The problem of finding the least-squares 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 NP-hard. 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 worst-case complexity of the integer-least-squares problem, we study its expected complexity, averaged over the noise and over the lattice. For the "sphere decoding" algorithm of Fincke and Pohst (1985) we find a closed-form expression for the expected complexity and show that for a wide range of noise variances the expected complexity is polynomial, in fact often sub-cubic. Since many communications systems operate at noise levels for which the expected complexity turns out to be polynomial, this suggests that maximum-likelihood decoding, which was hitherto thought to be computationally intractable, can in fact be implemented in realtime--a result with many practical implications.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1109/ICASSP.2002.5744897DOIArticle
Additional Information:© 2002 IEEE.
DOI:10.1109/ICASSP.2002.5744897
Record Number:CaltechAUTHORS:20150212-073945154
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20150212-073945154
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:54758
Collection:CaltechAUTHORS
Deposited By: Shirley Slattery
Deposited On:13 Feb 2015 22:48
Last Modified:10 Nov 2021 20:37

Repository Staff Only: item control page