Name
Title | ||
|---|---|---|
Success probability of the Babai estimators for box-constrained integer linear models. |
Abstract | ||
|---|---|---|
In many applications including communications, one may encounter a linear model where the parameter vector $\\hat { {x}}$ is an integer vector in a box. To estimate $\\hat { {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 $ {x}^ {\\scriptscriptstyle \\text {BB}}$ is commonly used as a suboptimal solution. In this paper, we first derive formulas for the success probability $P^ {\\scriptscriptstyle \\text {BB}}$ of $ {x}^ {\\scriptscriptstyle \\text {BB}}$ and the success probability $P^ {\\scriptscriptstyle \\text {OB}}$ of the ordinary Babai integer point $ {x}^ {\\scriptscriptstyle \\text {OB}}$ when $\\hat { {x}}$ is uniformly distributed over the constraint box. Some properties of $P^ {\\scriptscriptstyle \\text {BB}}$ and $P^ {\\scriptscriptstyle \\text {OB}}$ and the relationship between them are studied. Then, we investigate the effects of some column permutation strategies on $ {P}^ {\\scriptscriptstyle \\text {BB}}$ . 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 $P^ {\\scriptscriptstyle \\text {BB}}$ and argue why both V-BLAST and SQRD often increase $P^ {\\scriptscriptstyle \\text {BB}}$ ; and on the other hand, we show that when the noise is relatively large, LLL-P always decreases $P^ {\\scriptscriptstyle \\text {BB}}$ and argue why both V-BLAST and SQRD often decrease $P^ {\\scriptscriptstyle \\text {BB}}$ . We also derive a column permutation invariant bound on $P^ {\\scriptscriptstyle \\text {BB}}$ , 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 $ {x}^ {\\scriptscriptstyle \\text {OB}}$ proposed 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. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1109/TIT.2016.2627082 | IEEE Trans. Information Theory |
Keywords | Field | DocType |
Zinc,Search methods,Oils,Signal to noise ratio,Algorithm design and analysis,Complexity theory,Upper bound | Integer,Discrete mathematics,Combinatorics,Linear model,Upper and lower bounds,Permutation,Invariant (mathematics),Conjecture,Mathematics,Lattice reduction,Estimator | Journal |
Volume | Issue | ISSN |
abs/1410.5040 | 1 | 0018-9448 |
Citations | PageRank | References |
26 | 1.01 | 23 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jinming Wen | 1 | 26 | 1.01 |
| Xiao-Wen Chang | 2 | 208 | 24.85 |