Iterative Tomographic Solution of Integer Least Squares Problems With Applications to MIMO Detection

Least squares (LS) fitting is one of the most fundamental techniques in science and engineering. It is used to estimate parameters from multiple noisy observations. In many problems the parameters are known a priori to be bounded integer valued, or they come from a finite set of values on an arbitrary finite lattice. Integer least squares is also an important problem in multichannel communication systems and GPS applications. In this case finding the closest vector becomes NP-hard problem. In this paper, we propose two novel algorithms, the Tomographic Least Squares Decoder (TLSD), that not only solves the ILS problem, better than other sub-optimal techniques, but can also provide the a posteriori probability distribution for each element in the solution vector and a belief propagation version termed two-dimensional belief propagation (2DBP). Both algorithms are based on reconstruction of the vector from multiple two-dimensional projections. The projections are carefully chosen to provide low computational complexity. We show that the projections are equivalent to the two-dimensional marginals of the soft zero forcing linear decoder. We also provide simulated experiments comparing the algorithm to other sub-optimal algorithms. We end with a discussion of possible extensions to coded systems and combinations with sphere decoding.