Ferkans — Interactive Telecom Tutor

Lift, Relax, Randomize

Semidefinite relaxation (SDR) is the most powerful polynomial-time approach for unit-modulus QCQPs. Its three-step structure — lift the vector to a PSD matrix, relax the rank-1 constraint, randomize to get a feasible solution — is a central optimization pattern that appears throughout signal processing. For RIS problems at moderate $N$ , SDR gives the tightest polynomial-time bound on the global optimum and the highest-quality feasible solution.

Definition:
The Lifting Transformation

The unit-modulus QCQP $\max_{|\tilde{\phi}_n| = 1} \boldsymbol{\tilde{\phi}}^H \mathbf{A} \boldsymbol{\tilde{\phi}}$ is rewritten in terms of the lifted variable $\mathbf{X} = \boldsymbol{\tilde{\phi}} \boldsymbol{\tilde{\phi}}^H \in \mathbb{C}^{(N+1) \times (N+1)}$ . Key identities:

$\boldsymbol{\tilde{\phi}}^H \mathbf{A} \boldsymbol{\tilde{\phi}} = \text{tr}(\mathbf{A} \mathbf{X})$ .
$\mathbf{X} = \boldsymbol{\tilde{\phi}} \boldsymbol{\tilde{\phi}}^H \succeq 0$ and $\text{rank}(\mathbf{X}) = 1$ .
The unit-modulus constraint $|\tilde{\phi}_n| = 1$ is equivalent to the diagonal constraint $[\mathbf{X}]_{nn} = 1$ .

The lifted QCQP is

$\max_{\mathbf{X} \succeq 0}\ \text{tr}(\mathbf{A} \mathbf{X}) \quad \text{s.t.}\quad [\mathbf{X}]_{nn} = 1 \forall n, \ \text{rank}(\mathbf{X}) = 1.$

The objective and feasibility are now linear in $\mathbf{X}$ — the only non-convexity is the rank constraint.

The rank constraint is the "secret source" of non-convexity. Without it, the problem is a standard SDP — solvable in polynomial time by interior-point methods. The SDR approach drops the rank constraint and solves the resulting SDP.

Theorem: SDR Provides a Tight Upper Bound

The SDR problem

$\mathbf{X}^{\text{SDR}} = \arg\max_{\mathbf{X} \succeq 0}\ \text{tr}(\mathbf{A}\mathbf{X}) \quad \text{s.t.}\ [\mathbf{X}]_{nn} = 1$

is a convex SDP with polynomial-time solution by interior-point methods ( $O(N^{6.5})$ ). Its optimal value $\text{tr}(\mathbf{A}\mathbf{X}^{\text{SDR}})$ provides an upper bound on the original QCQP optimum. When $\text{rank}(\mathbf{X}^{\text{SDR}}) = 1$ , the relaxation is tight: $\mathbf{X}^{\text{SDR}} = \boldsymbol{\tilde{\phi}}^\star {\boldsymbol{\tilde{\phi}}^\star}^H$ , and $\boldsymbol{\tilde{\phi}}^\star$ is extracted by eigendecomposition.

For $\text{rank}(\mathbf{A}) = 1$ , the SDR is always tight. For higher rank, tightness is not guaranteed, but the bound is typically close to the global optimum.

Dropping a constraint can only increase the feasible region, so the relaxed optimum is at least as large as the original optimum. Empirically, the relaxation gap is small for RIS-relevant $\mathbf{A}$ — usually $\leq 1\text{ dB}$ .

SDR with Gaussian Randomization

Complexity:

O(N^{6.5})

for the SDP +

O(L N^2)

for

L

randomizations; typical

L = 1000

Input: PSD matrix

\mathbf{A} \in \mathbb{C}^{(N+1) \times (N+1)}

; randomization count

L

.

Output: Unit-modulus

\boldsymbol{\tilde{\phi}}^\star

with objective

\geq

(\pi/4) \cdot

(SDR bound).

1. Solve the SDP

\mathbf{X}^{\text{SDR}} = \arg\max_{\mathbf{X}\succeq 0}\ \text{tr}(\mathbf{A}\mathbf{X})

s.t.

[\mathbf{X}]_{nn} = 1

.

2. If

\text{rank}(\mathbf{X}^{\text{SDR}}) = 1

: eigendecompose

\mathbf{X}^{\text{SDR}} = \mathbf{u}\mathbf{u}^H

; return

\tilde{\phi}_n = u_n/|u_n|

.

3. Otherwise (Gaussian randomization):

4.

\quad

Draw

L

random vectors

\mathbf{z}_\ell \sim \mathcal{CN}(\mathbf{0}, \mathbf{X}^{\text{SDR}})

for

\ell = 1, \ldots, L

.

5.

\quad

For each

\ell

: quantize to unit modulus,

\boldsymbol{\tilde{\phi}}_\ell = \mathbf{z}_\ell / |\mathbf{z}_\ell|

(element-wise).

6.

\quad

Evaluate objective

f(\boldsymbol{\tilde{\phi}}_\ell)

for each.

7.

\quad

Return

\boldsymbol{\tilde{\phi}}^\star = \arg\max_\ell f(\boldsymbol{\tilde{\phi}}_\ell)

.

The $L$ randomizations essentially "sample" the set of rank-1 approximations to $\mathbf{X}^{\text{SDR}}$ . The probability that one of $L$ samples achieves a $(\pi/4)$ -approximation of the SDR bound increases with $L$ .

Theorem: The $(\pi/4)$ Approximation Guarantee

For the unit-modulus QCQP with $\mathbf{A} \succeq 0$ , the expected objective of a single random rounding is

$\mathbb{E}_{\mathbf{z} \sim \mathcal{CN}(\mathbf{0}, \mathbf{X}^{\text{SDR}})}\big[f(\mathbf{z}/|\mathbf{z}|)\big] \geq \frac{\pi}{4}\, f_{\text{SDR}},$

where $f_{\text{SDR}} = \text{tr}(\mathbf{A} \mathbf{X}^{\text{SDR}})$ . Hence, taking the best of $L$ randomizations gives

$f(\boldsymbol{\tilde{\phi}}^\star) \geq \frac{\pi}{4}\, f_{\text{SDR}}$

with probability approaching 1 as $L \to \infty$ . For $L \geq 1000$ , this guarantee holds with $\geq 0.99$ confidence in practice.

Gaussian randomization preserves the "direction" of the SDR solution and perturbs by a controlled amount. In expectation the randomized objective is a fraction $(\pi/4)$ of the SDR objective — the bound arises from computing the expectation of $|\arg z|$ for complex Gaussian $z$ .

Proof

Single randomization bound

By Zhang and Huang (2006), for Hermitian PSD $\mathbf{A}$ : $\mathbb{E}_{\mathbf{z}}[\mathbf{z}^H \mathbf{A} \mathbf{z} / (\|\mathbf{z}\|^2)] = (\pi/4) \text{tr}(\mathbf{A} \mathbf{X}^{\text{SDR}}) + o(\ldots)$ under appropriate normalization of $\mathbf{z}$ .

Boost by maximum

With $L$ i.i.d. samples, the max of $L$ realizations converges to the supremum of the distribution. Under mild concentration assumptions, the max is within $O(\sqrt{\log L})$ of the supremum, so $L = 1000$ is effectively optimal.

Tight: for certain $\mathbf{A}$

For worst-case $\mathbf{A}$ (MAX-CUT instances), $(\pi/4)$ is tight — cannot be improved. For RIS-relevant $\mathbf{A}$ (rank-1 or nearly-rank-1), the actual approximation ratio approaches 1. $\blacksquare$

Empirically, Randomization Is Nearly Tight

The $(\pi/4)$ bound is a worst-case guarantee. In practice, for RIS problems with typical channels, Gaussian randomization achieves $> 95\%$ of the SDR objective, often $> 99\%$ . The theory is much more pessimistic than the practice. This is why SDR is the "gold standard" in RIS papers — it delivers near-optimal solutions at the cost of a heavy SDP solve.

SDR Lift and Gaussian Randomization

Visualization of the three-step SDR pipeline. First, the unit-modulus vector is lifted to a rank-1 PSD matrix. Second, the rank constraint is relaxed, and an SDP is solved yielding a (generally higher-rank)

\mathbf{X}^{\text{SDR}}

. Third, Gaussian samples are drawn from

\mathcal{CN}(\mathbf{0}, \mathbf{X}^{\text{SDR}})

and projected onto the unit-modulus torus; the best projection is returned.

SDR Approximation Gap vs. $L$

For a synthetic rank- $r$ problem, plot the normalized SDR approximation (best-of- $L$ over SDR upper bound) as a function of $L$ . At $L = 1$ the average is $\sim \pi/4 \approx 0.785$ ; by $L = 100$ nearly all instances achieve $> 0.95$ ; by $L = 1000$ practically optimal.

Parameters

RIS elements

N

32

Rank of

\mathbf{A}

2

Max randomizations500

Monte-Carlo trials20

Example: SDR on a $N = 2$ Toy Problem

Let $\mathbf{A} = \begin{pmatrix} 2 & 1 \\ 1 & 1 \end{pmatrix}$ (real and PSD). Find the unit-modulus maximizer and compare with SDR.

Solution

Set up SDR

Variables $\mathbf{X} = \begin{pmatrix} 1 & x \\ x^* & 1 \end{pmatrix}$ with $|x| \leq 1$ (implied by PSD constraint). Objective $\text{tr}(\mathbf{A}\mathbf{X}) = 2 + 1 + 2\text{Re}(x) = 3 + 2\text{Re}(x)$ .

Maximize

Maximum at $x = 1$ : objective $= 5$ . This corresponds to $\mathbf{X} = \mathbf{1}\mathbf{1}^H$ , rank 1 — the SDR is tight, and $\boldsymbol{\tilde{\phi}} = \mathbf{1}$ .

Verify against QCQP

Direct: $\boldsymbol{\tilde{\phi}}^H \mathbf{A} \boldsymbol{\tilde{\phi}} = |\tilde{\phi}_1|^2 \cdot 2 + 2 \text{Re}(\tilde{\phi}_1 \tilde{\phi}_2^*) + |\tilde{\phi}_2|^2 = 3 + 2\cos(\theta_1 - \theta_2)$ (with $|\tilde{\phi}_n| = 1$ ). Maximized at $\theta_1 = \theta_2$ : objective $= 5$ . Matches SDR. $\blacksquare$

Common Mistake: SDR Does Not Scale

Mistake:

"SDR is the gold standard, so I'll use it for my $N = 512$ panel."

Correction:

SDR's $O(N^{6.5})$ interior-point cost is prohibitive above $N \sim 128$ . For $N = 512$ : $512^{6.5} \approx 3 \times 10^{17}$ flops — hours of computation per AO iteration. Manifold optimization (Section 6.3) scales as $O(N^2)$ per iteration and is the only practical choice for large $N$ . Use SDR for benchmarking or small-to-medium deployments; use manifold or element-wise for production at scale.

🔧Engineering Note

SDP Solvers in Practice

Deploying SDR requires an SDP solver. Common choices:

CVX (MATLAB) or CVXPY (Python): Disciplined convex programming frameworks. Easy to express the problem; use MOSEK or SeDuMi as the back-end solver.
MOSEK: Commercial, fast, excellent for medium-size SDPs ( $N \leq 100$ ).
SCS: Open-source alternative, solver of choice for batch-mode Monte Carlo. Slightly less accurate, much faster.
Custom ADMM: For production, a custom implementation can exploit problem structure (low-rank $\mathbf{A}$ , Toeplitz $\mathbf{B}$ ) for $5$ - $10\times$ speedup over general-purpose SDP solvers.

Practical Constraints

•
CVX / MOSEK at $N = 100$ : $\sim 0.1$ s per SDP. $N = 200$ : $\sim 2$ s. $N = 400$ : $\sim 30$ s.
•
Memory requirement: $N^2$ doubles for the $\mathbf{X}$ variable; $N = 512$ needs 2 MB.
•
Randomization typically takes $< 1\%$ of the total SDR runtime.

Semidefinite Relaxation and Gaussian Randomization