On the Expected Complexity of Integer-Least-Squares Problems

Prof. Babak Hassibi, Department of Electrical Engineering, Caltech

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 most 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 talk, 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 a specific algorithm, referred to as ``sphere decoding'', 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-time, in fact often sub-cubic. Since many communications systems operate at noise levels for which the expected complexity turns out to be polynomial-time, this suggests that maximum-likelihood decoding, which was hitherto thought to be computationally intractable, can in fact be implemented in real-time---a result with many practical implications.

Our derivation has interesting connections with some classical work of Jacobi, Ramanujan and Hardy-Littlewood, which I will discuss. I will also point out a connection between computational complexity and Shannon capacity which our results seem to suggest.

This is joint work with H. Vikalo.