论文标题
最佳离散IRS波束成形的线性时间算法
A Linear Time Algorithm for the Optimal Discrete IRS Beamforming
论文作者
论文摘要
在多项式时间内对智能反射表面（IRS）的离散约束下，找到相移的最佳配置仍然是一个开放的问题。以上问题被普遍认为是困难的，因为它与可以有效解决的任何已知组合问题没有联系。分支结合的算法和近似算法构成了该区域的最佳结果。但是，这项工作表明，就IRS的反射元素（RES）的数量而言，实际上可以在线性时间以线性时间达到全局最佳。主要思想是几何解释离散的波束形成问题是选择单位圆上的最佳点。尽管相移的可能组合数量随RES的数量呈指数增长，但事实证明，只有线性数量可能包含最佳点的圆弧。此外，所提出的算法可以被视为一种新型二次程序（QP）的新方法。
It remains an open problem to find the optimal configuration of phase shifts under the discrete constraint for intelligent reflecting surface (IRS) in polynomial time. The above problem is widely believed to be difficult because it is not linked to any known combinatorial problems that can be solved efficiently. The branch-and-bound algorithms and the approximation algorithms constitute the best results in this area. Nevertheless, this work shows that the global optimum can actually be reached in linear time on average in terms of the number of reflective elements (REs) of IRS. The main idea is to geometrically interpret the discrete beamforming problem as choosing the optimal point on the unit circle. Although the number of possible combinations of phase shifts grows exponentially with the number of REs, it turns out that there are only a linear number of circular arcs that possibly contain the optimal point. Furthermore, the proposed algorithm can be viewed as a novel approach to a special case of the discrete quadratic program (QP).
