Success Probability of the Babai Estimators for Box-Constrained Integer Linear Models

In many applications including communications, one may encounter a linear model where the parameter vector x̂ is an integer vector in a box. To estimate x̂, a typical method is to solve a box-constrained integer least squares problem. However, due to its high complexity, the box-constrained Babai integer point xBBis commonly used as a suboptimal solution. In this paper, we first derive formulas for the success probability PBBof xBBand the success probability POB of the ordinary Babai integer point xOBwhen x̂ is uniformly distributed over the constraint box. Some properties of PBBand POBand the relationship between them are studied. Then, we investigate the effects of some column permutation strategies on PBB. In addition to V-BLAST and SQRD, we also consider the permutation strategy involved in the LLL lattice reduction, to be referred to as LLL-P. On the one hand, we show that when the noise is relatively small, LLL-P always increases PBBand argue why both V-BLAST and SQRD often increase PBB; and on the other hand, we show that when the noise is relatively large, LLL-P always decreases PBBand argue why both V-BLAST and SQRD often decrease PBB. We also derive a column permutation invariant bound on PBB, which is an upper bound and a lower bound under these two opposite conditions, respectively. Numerical results demonstrate our findings. Finally, we consider a conjecture concerning xOBproposed by Ma et al. We first construct an example to show that the conjecture does not hold in general, and then show that it does hold under some conditions.