论文标题
重新粘贴
Rephased CLuP
论文作者
论文摘要
在\ cite {stojnicclupint19，stojnicclupcmpl19，stojnicclupplt19}中，我们介绍了粘贴，a \ bl {\ bl {\ textbf {随机二元理论（rdt）}}}}}}}}基于算法的机制，该机制可用于求解硬性优化问题。由于其介绍性质，\ cite {stojnicclupint19，stojnicclupcmpl19，stojnicclupplt19}讨论了最基本的结合概念。另一方面，在我们的同伴论文中\ cite {stojniccluplargesc20}}我们开始了一个更深入的细节的故事，这些细节与许多其他出色的笨拙属性有关，其中一些属性远远超出了基本基础。也就是说，\ cite {stojniccluplargesc20}讨论了如何利用某种沉默的RDT功能（其算法功率）来确保在非常大的问题实例上也可以运行粘贴。特别是，将粘贴应用于我们在\ cite {stojniccluplargesc20}中显示的著名MIMO ML检测问题，它是一个大规模的变体，$ \ text {clup}^{r_0} $，可以通过\ textbf {\ emph {\ emph {emph emph {矩阵矢量乘法就足够了）。在本文中，我们重新访问MIMO ML检测，并讨论粘结结构内出现的另一个显着现象，即所谓的\ bl {\ textbf {\ emph {\ emph {rephasing}}}}。随着MIMO ML进入所谓的低美元$α$制度（脂肪系统矩阵的行与行数和列的比例，$α$，速度低于$ 1 $）也变得越来越困难，即使对于基本标准校正而言处理它也变得越来越困难。但是，重新播放的发现确保了粘贴保持正轨并保持其实现ML性能的能力。为了证明重新播放的力量，我们还进行了许多数值实验，将我们通过它们获得的结果与理论预测进行了比较，并观察到了出色的一致性。
In \cite{Stojnicclupint19,Stojnicclupcmpl19,Stojnicclupplt19} we introduced CLuP, a \bl{\textbf{Random Duality Theory (RDT)}} based algorithmic mechanism that can be used for solving hard optimization problems. Due to their introductory nature, \cite{Stojnicclupint19,Stojnicclupcmpl19,Stojnicclupplt19} discuss the most fundamental CLuP concepts. On the other hand, in our companion paper \cite{Stojniccluplargesc20} we started the story of going into a bit deeper details that relate to many of other remarkable CLuP properties with some of them reaching well beyond the basic fundamentals. Namely, \cite{Stojniccluplargesc20} discusses how a somewhat silent RDT feature (its algorithmic power) can be utilized to ensure that CLuP can be run on very large problem instances as well. In particular, applying CLuP to the famous MIMO ML detection problem we showed in \cite{Stojniccluplargesc20} that its a large scale variant, $\text{CLuP}^{r_0}$, can handle with ease problems with \textbf{\emph{several thousands}} of unknowns with theoretically minimal complexity per iteration (only a single matrix-vector multiplication suffices). In this paper we revisit MIMO ML detection and discuss another remarkable phenomenon that emerges within the CLuP structure, namely the so-called \bl{\textbf{\emph{rephasing}}}. As MIMO ML enters the so-called low $α$ regime (fat system matrix with ratio of the number of rows and columns, $α$, going well below $1$) it becomes increasingly difficult even for the basic standard CLuP to handle it. However, the discovery of the rephasing ensures that CLuP remains on track and preserves its ability to achieve the ML performance. To demonstrate the power of the rephasing we also conducted quite a few numerical experiments, compared the results we obtained through them to the theoretical predictions, and observed an excellent agreement.
