A Linear Time Algorithm for the Optimal Discrete IRS Beamforming
- 26 December 2022
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Wireless Communications Letters
- Vol. 12 (3) , 496-500
Abstract
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 letter 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).Keywords
All Related Versions
Funding Information
- National Natural Science Foundation of China (92167202)
- NSFC (62001411)
- Huawei Technologies
- Guangdong Provincial Key Laboratory of Big Data Computing
This publication has 18 references indexed in Scilit:
- Learning to Reflect and to Beamform for Intelligent Reflecting Surface With Implicit Channel EstimationIEEE Journal on Selected Areas in Communications, 2021
- Energy Efficiency and Spectral Efficiency Tradeoff in RIS-Aided Multiuser MIMO Uplink TransmissionIEEE Transactions on Signal Processing, 2020
- Channel Estimation and Passive Beamforming for Intelligent Reflecting Surface: Discrete Phase Shift and Progressive RefinementIEEE Journal on Selected Areas in Communications, 2020
- Intelligent Reflecting Surface: Practical Phase Shift Model and Beamforming OptimizationIEEE Transactions on Communications, 2020
- Hybrid Beamforming for Reconfigurable Intelligent Surface based Multi-User Communications: Achievable Rates With Limited Discrete Phase ShiftsIEEE Journal on Selected Areas in Communications, 2020
- Optimal Beamforming for MISO Communications via Intelligent Reflecting Surfaces2020
- Beamforming Optimization for Wireless Network Aided by Intelligent Reflecting Surface With Discrete Phase ShiftsIEEE Transactions on Communications, 2019
- On linear conic relaxation of discrete quadratic programsOptimization Methods and Software, 2016
- Maximizing the Product of Two Linear Functions In 0-1 VariablesOptimization, 2002
- A polynomial case of unconstrained zero-one quadratic optimizationMathematical Programming, 2001