To meet the throughput demands of next-generation wireless networks, technologies like Massive MIMO, Reconfigurable Intelligent Surfaces (RIS), and Holographic MIMO utilize arrays with hundreds or thousands of antenna elements. However, directing signals precisely toward users requires solving complex optimization problems to determine the active beamforming vectors at the base station and the passive phase shifts at the reflective surfaces.
Traditionally, these problems are solved using Semidefinite Relaxation (SDR) or interior-point methods. These algorithms "lift" vector variables into higher-dimensional matrix spaces, resulting in computational complexities that scale cubically ($O(N^3)$) or even up to the sixth power ($O(N^6)$) of the number of elements $N$ (as noted by Sadeghi et al.). Because wireless channels fluctuate on millisecond timescales, these polynomial-complexity algorithms are too slow for real-time deployment.
Linear-complexity beamforming solves this bottleneck. By redesigning optimization workflows to scale linearly ($O(N)$) with the number of elements, these techniques enable real-time signal steering in massive aperture systems.
Decoupling via Fractional Programming and Alternating Updates
The primary reason traditional beamforming optimization scales poorly is the highly non-convex, coupled nature of the objective functions. For example, in an RIS-assisted network, the received signal strength depends on the product of the base station's active beamforming vector and the surface's passive phase-shift matrix. Optimizing both simultaneously is computationally prohibitive.
Linear-complexity frameworks bypass this by decoupling the variables through alternating optimization (AO) and fractional programming. Instead of solving a massive joint problem, the algorithm breaks it into smaller subproblems and cycles through them, updating one variable while holding the others constant.
┌────────────────────────────────────────────────────────┐
│ Joint Non-Convex Problem │
│ Maximize Sum-Rate(Active Precoding, Passive Phases) │
└───────────────────────────┬────────────────────────────┘
│
Fractional Programming & AO
▼
┌───────────────────────────┴────────────────────────────┐
│ Subproblem 1: Active Precoding (Closed-Form Update) │
└───────────────────────────┬────────────────────────────┘
│
▼
┌───────────────────────────┴────────────────────────────┐
│ Subproblem 2: Passive Phases (Linear O(N) Scaling) │
└────────────────────────────────────────────────────────┘
As Ma et al. and Ma et al. demonstrate, fractional programming can transform non-convex sum-rate expressions into quadratic forms that admit exact, closed-form analytical updates. Because each subproblem is solved analytically rather than through iterative numerical toolboxes, the computational complexity drops to a linear relationship with the number of reflecting elements.
Similarly, Zhu et al. and Zhu et al. show that deriving closed-form surrogate expressions within the alternating loop eliminates the need for heavy iterative quadratic solvers entirely. This mathematical restructuring allows systems to maintain user fairness and high data rates while scaling efficiently to massive array sizes.
Avoiding Matrix Lifting and Inversion
Traditional optimization methods often rely on matrix lifting, transforming a vector optimization problem of size $N$ into a matrix problem of size $N \times N$. While this convexifies the problem, it introduces a massive computational penalty.
To achieve linear complexity, modern algorithms operate directly within the original beamforming vector space. By avoiding the high-dimensional lifting characteristic of traditional optimization, they generate naturally valid solutions without requiring expensive post-processing or rank-one reductions. For instance, Attiah et al. leverage uplink-downlink duality to design iterative algorithms that operate strictly within the vector space, matching the accuracy of semidefinite relaxation at a fraction of the overhead.
Another computational bottleneck is the inversion of large channel covariance matrices. Ju et al. address this by exploiting the predictable linear or conjugate linear structures of complex matrix derivatives under specific constraints. By solving a small system of linear equations based on a few feasible solutions, the optimal updates can be determined without executing full matrix inversions, drastically reducing the per-iteration complexity.
Element-Wise Optimization and First-Order Gradients
When dealing with thousands of passive phase shifters, updating the entire array simultaneously can still be costly. A highly effective alternative is element-wise sequential optimization, where the phase shift of a single element is tuned while keeping all other elements fixed.
Li et al. show that an element-wise iterative approach using a simple bisection method can configure massive arrays with strict linear complexity. Because each element's optimal phase shift can be calculated sequentially using basic scalar operations, the system avoids the cubic overhead associated with global penalty-based algorithms.
Simultaneous Update (Traditional):
[ Δθ₁, Δθ₂, ..., Δθₙ ] ──► Requires High-Dimensional Matrix Operations O(N³)
Element-Wise Update (Low-Complexity):
[ θ₁ ] ──► [ θ₂ ] ──► ... ──► [ θₙ ] ──► Scalar Operations Per Element O(N)
For applications where simultaneous updates are preferred, first-order gradient methods offer a lightweight alternative to second-order interior-point methods. Ma et al. demonstrate that a first-order gradient descent approach with a tailored step-size rule achieves performance parity with complex manifold optimization. This confirms that simpler, first-order optimization strategies are sufficient for high-dimensional passive element arrays.
Reducing Search Spaces and Eliminating CSI Overhead
A common assumption in wireless communications was that optimizing discrete or binary phase shifts for an RIS is an NP-hard combinatorial problem. Zhang et al. disproved this by showing that the global optimum for binary phase shifts can be achieved with an $O(N)$ linear-time algorithm, providing a provable performance guarantee for quadrature beamforming. In a similar vein, Fan et al. proved that the optimal solution space for over-the-air data aggregation can be reduced to a simple linear search, allowing edge intelligence servers to determine optimal parameters in real time.
Finally, linear complexity can be extended to scenarios where Channel State Information (CSI) is completely unavailable. Acquiring CSI in massive RIS systems typically introduces massive pilot-signal overhead. To bypass this, Xu et al. and Lai et al. introduce blind beamforming frameworks based on statistical sampling.
By taking random samples of received signal power and calculating conditional sample means, their algorithms optimize reflective elements via a voting and search mechanism. This data-driven approach scales linearly with the number of elements and completely eliminates the protocol overhead and hardware complexity of traditional channel estimation.
Key Foundational Work
Robust Cognitive Beamforming With Partial Channel State Information (2008) — contributed 1 concept elements to this direction.
A fast-converging adaptive frequency-domain MVDR beamformer for speech enhancement (2012) — contributed 1 concept elements to this direction.