# A Linear Time Algorithm for the Optimal Discrete IRS Beamforming

arXiv: https://arxiv.org/abs/2211.04704 · HTML: https://mlsanity.com/paper/2211.04704/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Nov 2022.

## Built on by (most cited first, 3 of 3)

- [Optimal Beamforming of RIS-Aided Wireless Communications: An Alternating Inner Product Maximization Approach](https://mlsanity.com/paper/2405.06442/) (2024)
- [Optimal Configuration of Reconfigurable Intelligent Surfaces With Non-uniform Phase Quantization](https://mlsanity.com/paper/2405.06967/) (2024)
- [Discrete Beamforming Optimization for RISs with a Limited Phase Range and Amplitude Attenuation](https://mlsanity.com/paper/2507.07342/) (2025)

## Abstract (arXiv)

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).