Chapter Summary

Chapter Summary

Key Points

• 1.

  The passive RIS subproblem is a unit-modulus QCQP. Maximize $\boldsymbol{\tilde{\phi}}^H \mathbf{A} \boldsymbol{\tilde{\phi}}$ subject to $|\tilde{\phi}_n| = 1$ (PSD $\mathbf{A}$). The problem is NP-hard in general but tractable for RIS-relevant channel structures. Three canonical algorithms solve it: SDR, manifold optimization, element-wise BCD.

• 2.

  SDR: lift, relax, randomize. Lift $\boldsymbol{\tilde{\phi}}$ to $\mathbf{X} = \boldsymbol{\tilde{\phi}}\boldsymbol{\tilde{\phi}}^H$, drop the rank-1 constraint, solve the SDP, and recover a feasible solution via Gaussian randomization. The worst-case $(\pi/4)$-approximation guarantee is loose; in practice, randomization achieves $> 95\%$ of the SDR bound. Cost: $O(N^{6.5})$, limits $N \leq 128$.

• 3.

  Manifold: respect the geometry. The unit-modulus torus is a smooth $N$-dimensional manifold. Riemannian gradient descent projects the Euclidean gradient onto the tangent space and retracts back to the manifold. Cost: $O(N^2)$ per iteration, $\sim 50$-$200$ iterations. Scales to $N = 1024$ easily. The Manopt toolbox provides production-quality implementations.

• 4.

  Element-wise BCD: one coordinate at a time. Update each $\phi_n$ in closed form while holding others fixed. Optimal for rank-1 (single-user) problems; for higher rank, reaches a local optimum typically $1$-$3$ dB below SDR. Cost: $O(N)$ per coordinate, $\sim 5$-$10$ sweeps total. Fastest, deployment-ready, real-time friendly.

• 5.

  Pareto-frontier: quality vs. speed. Choose the algorithm based on the dominant constraint. Offline benchmark → SDR. Large-$N$ production → manifold (with warm-starting). Real-time or single-user → element-wise. The three algorithms are complementary, not competing: production systems often use all three in different contexts.