Success Probability of the Babai Estimators for Box-Constrained Integer Linear Models
Success Probability of the Babai Estimators for Box-Constrained Integer Linear Models
复制标题
DOI：
10.1109/tit.2016.2627082
复制
发表时间：
2014-10
影响因子：
2.5
通讯作者：
Jinming Wen;X. Chang
中科院分区：
文献类型：
--
作者：
Jinming Wen;X. Chang
在包括通信在内的许多应用中，人们可能会遇到一个线性模型，其中参数向量$\hat{{x}}$是盒中的整数向量。要估计$HAT{{x}}$，一个典型的方法是求解一个盒子约束的整数最小二乘问题。然而，由于其高度的复杂性，盒约束的Babai整点${x}^{\ScriptScriptstyle\Text{bb}}$通常被用作次优解。本文首先给出了${x}^{\ScriptScriptstyle\Text{bb}}$的成功概率和一般Babai整点${x}^{\ScriptScriptstyle\Text{OB}}$均匀分布在约束框上时的成功概率$P^{\ScriptScriptstyle\Text{bb}}$的公式。研究了$P^{\ScriptScriptstyle\Text{bb}}$和$P^{\ScriptScriptstyle\Text{ob}}$的一些性质以及它们之间的关系。然后，我们研究了一些列置换策略对${P}^{\ScriptScriptstyle\Text{BB}}$的影响。除了V-BLAST和SQRD之外，我们还考虑了在LLL格子约简中所涉及的置换策略，称为LLL-P。一方面，我们证明了当噪声较小时，LLL-P总是增加$P^{\ScriptScriptstyle\Text{BB}}$，并讨论了为什么V-BLAST和SQRD经常增加$P^{\ScriptScriptstyle\Text{BB}}$；另一方面，我们证明了当噪声相对较大时，LLL-P总是减少$P^{\ScriptScriptstyle\Text{BB}}$，并论证了为什么V-BLAST和SQRD经常减少$P^{\ScriptScriptstyle\Text{BB}}$。我们还得到了$P^{\ScriptScriptStyle\Text{BB}}$上的一个列置换不变界，它分别是这两个相反条件下的上界和下界。数值结果验证了我们的发现。最后，我们考虑了Ma等人提出的关于${x}^{\ScriptScriptstyle\Text{ob}}$的一个猜想。我们首先构造一个例子来证明这个猜想在一般情况下不成立，然后证明在某些条件下它确实成立。
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.