Ferkans — Interactive Telecom Tutor

A Single Problem, Three Algorithms

Chapter 5 reduced the joint optimization to two coordinated subproblems, one of which was the passive subproblem: maximize a (ratio of) quadratic forms in $\boldsymbol{\phi}$ subject to $|\phi_n| = 1$ . This is a unit-modulus QCQP, a canonical non-convex problem that appears across signal processing — constellation shaping, radar waveform design, phase retrieval, and RIS. The same three algorithms (SDR, manifold, element-wise) are used in all these applications; mastering them once pays off many times.

Definition:
The Canonical Unit-Modulus QCQP

Consider the single-user MISO-RIS passive subproblem under fixed BS beamformer $\mathbf{v}$ . Using the diagonal-product identity, the objective is

$f(\boldsymbol{\phi}) = |\mathbf{h}_d^H \mathbf{v} + \boldsymbol{\phi}^T \mathbf{b}|^2,$

where $\mathbf{b} = \text{diag}(\mathbf{h}_2^*) \mathbf{H}_1 \mathbf{v}$ . Augmenting $\boldsymbol{\tilde{\phi}} = [\boldsymbol{\phi}; 1]$ and defining $\mathbf{c} = [\mathbf{b}; \mathbf{h}_d^H \mathbf{v}] \in \mathbb{C}^{N+1}$ , the objective becomes

$f(\boldsymbol{\tilde{\phi}}) = |\boldsymbol{\tilde{\phi}}^H \mathbf{c}|^2 = \boldsymbol{\tilde{\phi}}^H (\mathbf{c} \mathbf{c}^H) \boldsymbol{\tilde{\phi}}.$

Setting $\mathbf{A} = \mathbf{c} \mathbf{c}^H$ , the canonical unit-modulus QCQP is

$\boxed{\;\max_{\boldsymbol{\tilde{\phi}} \in \mathbb{C}^{N+1}}\; \boldsymbol{\tilde{\phi}}^H \mathbf{A} \boldsymbol{\tilde{\phi}} \quad \text{s.t.}\quad |\tilde{\phi}_n| = 1\;\forall n.\;}$

$\mathbf{A}$ is Hermitian PSD. For the single-user case, it is rank 1; for multi-user / multi-stream cases, $\mathbf{A}$ is higher rank but still PSD.

The QCQP in this form is known to be NP-hard in general (Zhang 2010). Polynomial-time exact solution is not possible; all three methods in this chapter are approximate — but in RIS-relevant regimes they are near-optimal.

,

Theorem: The Unit-Modulus QCQP Is NP-Hard

The problem $\max_{|\tilde{\phi}_n| = 1} \boldsymbol{\tilde{\phi}}^H \mathbf{A} \boldsymbol{\tilde{\phi}}$ with $\mathbf{A} \succeq 0$ is NP-hard in general. In particular, the subcase where $\mathbf{A}$ has 0/1 entries (Boolean quadratic programming) is equivalent to the MAX-CUT problem, which is NP-hard.

Proof

Reduction from MAX-CUT

MAX-CUT: given graph $G = (V, E)$ , find a subset $S \subseteq V$ maximizing $|E \cap (S \times V \setminus S)|$ . Encode as $x_n \in \{-1, +1\}$ with $x_n = 1$ iff $n \in S$ . The objective is $\frac{1}{4} \sum_{(i,j) \in E} (1 - x_i x_j)$ .

Map to unit-modulus QCQP

$\{-1, +1\}$ is a subset of $\{|\phi| = 1\}$ . Setting the imaginary part to zero, the unit-modulus QCQP restricted to real phases matches the MAX-CUT encoding with suitable $\mathbf{A}$ .

NP-hardness

Since MAX-CUT is NP-hard, the more general unit-modulus QCQP is at least as hard. $\blacksquare$

The Rank-1 Case Is Easy

When $\mathbf{A} = \mathbf{c}\mathbf{c}^H$ is rank 1 (e.g., the single-user MISO case), the QCQP has a closed-form solution by matched filtering: $\tilde{\phi}_n^\star = e^{-j\arg(c_n)}$ . Achieves objective $\|\mathbf{c}\|_1^2$ .

This is why single-user RIS beamforming has a clean closed form: the objective reduces to a rank-1 QCQP, which collapses to element-wise matching. The multi-user case is where rank goes above 1 and the three algorithms of this chapter become necessary.

Definition:
Multi-User Generalization: Rank- $K$ Objective

For the $K$ -user MU-MIMO case, the sum-rate objective has the form (under a sum-of-squares surrogate to avoid the $\log$ -ratio structure)

$f(\boldsymbol{\tilde{\phi}}) = \boldsymbol{\tilde{\phi}}^H \mathbf{A} \boldsymbol{\tilde{\phi}} - \boldsymbol{\tilde{\phi}}^H \mathbf{B} \boldsymbol{\tilde{\phi}},$

where $\mathbf{A}, \mathbf{B}$ are PSD matrices encoding the signal and interference contributions from each user, and $\text{rank}(\mathbf{A})$ can be up to $K$ . The unit-modulus QCQP is now indefinite: $\mathbf{A} - \mathbf{B}$ need not be PSD, which makes the feasible region's level sets non-convex and the problem harder.

Problem Difficulty: Rank of $\mathbf{A}$ vs. $N$

For fixed $N$ and different objective ranks (1, 2, 4, 8), plot the empirical gap of element-wise optimization to the SDR upper bound. Rank 1 (single user) has zero gap — the closed-form optimum; higher ranks have increasing gaps, showing that multi-stream/multi-user problems genuinely need better algorithms than element-wise.

Parameters

RIS elements

N

64

Max rank of

\mathbf{A}

8

Example: Closed-Form Solution for Rank-1 $\mathbf{A}$

Solve $\max_{|\tilde{\phi}_n| = 1} \boldsymbol{\tilde{\phi}}^H \mathbf{A} \boldsymbol{\tilde{\phi}}$ where $\mathbf{A} = \mathbf{c}\mathbf{c}^H$ for a given $\mathbf{c} \in \mathbb{C}^{N+1}$ .

Solution

Substitute rank-1 structure

$\boldsymbol{\tilde{\phi}}^H \mathbf{A} \boldsymbol{\tilde{\phi}} = \boldsymbol{\tilde{\phi}}^H \mathbf{c}\mathbf{c}^H \boldsymbol{\tilde{\phi}} = |\mathbf{c}^H \boldsymbol{\tilde{\phi}}|^2$ .

Triangle inequality

$|\mathbf{c}^H \boldsymbol{\tilde{\phi}}| = |\sum_n c_n^* \tilde{\phi}_n| \leq \sum_n |c_n| = \|\mathbf{c}\|_1$ , with equality iff all $c_n^* \tilde{\phi}_n$ have the same argument.

Match the phases

$\tilde{\phi}_n^\star = e^{j\arg(c_n)}$ , giving objective $\|\mathbf{c}\|_1^2$ .

Verification

Check: $\tilde{\phi}_n^\star c_n^* = |c_n|$ , so the sum is real and equal to $\|\mathbf{c}\|_1$ . Squared: $\|\mathbf{c}\|_1^2$ . ✓

The Three-Algorithm Menu

For rank- $r$ $\mathbf{A}$ with $r > 1$ , we have three choices:

SDR (Section 6.2): Lift to an SDP, get a tight polynomial-time upper bound, extract a feasible solution via Gaussian randomization. Quality: best; cost: highest ( $O(N^{6.5})$ ).
Manifold optimization (Section 6.3): View the constraint set as a Riemannian manifold; gradient descent in tangent space with retraction. Quality: second-best; cost: moderate ( $O(N^2)$ per iteration, $\sim 50$ - $200$ iterations).
Element-wise BCD (Section 6.4): Close-form update of one $\phi_n$ at a time. Quality: good but sometimes gap-to-SDR of $1$ - $3\text{ dB}$ ; cost: lowest ( $O(N)$ per sweep).

Section 6.5 benchmarks all three and gives deployment guidance.

The Unit-Modulus QCQP Landscape — Level sets of a rank-2 quadratic objective on the $N = 2$ unit-modulus torus (drawn as a 2-torus surface). Multiple local maxima (red) coexist with a single global maximum (gold). The three algorithms navigate this landscape differently: SDR lifts to the convex hull, manifold follows geodesic gradients, element-wise cycles coordinates.

The Unit-Modulus QCQP