Comparing SDR, Manifold, and Element-wise

One Problem, Three Answers

We have three algorithms for the same unit-modulus QCQP. This section quantifies the quality and runtime tradeoffs across realistic RIS sizes, helping you pick the right tool for your deployment.

Algorithm Comparison for Unit-Modulus QCQP

Property	SDR (Section 6.2)	Manifold (Section 6.3)	Element-wise (Section 6.4)
Complexity per call	$O(N^{6.5})$	$O(T N^2)$ , $T \sim 50$	$O(S N^2)$ , $S \sim 5$
Quality guarantee	$(\pi/4)$ -optimal, tight in practice	Stationary point (typically near-optimal)	Coordinate stationary (local)
Single-user optimal?	Yes (rank-1 case)	Yes	Yes (one sweep)
Scalability	$N \leq 128$ practical	$N \leq 1024$ practical	$N \leq 4096$ practical
Warm-start friendly?	Yes	Yes	Very yes (1-2 sweeps)
Real-time suitable?	No ( $> 1$ s)	Moderate ( $\sim 100$ ms)	Yes ( $< 1$ ms)
Typical gap to global	$< 1\%$	$1$ - $3\%$	$1$ - $10\%$
Implementation effort	High (SDP solver)	Medium (Manopt recommended)	Low (closed-form sweep)

Theorem: Algorithm Quality Hierarchy

For the unit-modulus QCQP with PSD $\mathbf{A}$ , the three algorithms have the quality ordering

$f_{\text{SDR}}^{\text{ub}} \geq f_{\text{SDR}}^{\text{rand}} \geq f_{\text{manifold}} \geq f_{\text{elementwise}}.$

The leftmost is an upper bound (not achievable in general); the right three are lower bounds (achieved by the respective algorithms). The gaps are:

$f_{\text{SDR}}^{\text{ub}} - f_{\text{SDR}}^{\text{rand}}$ : Gaussian randomization sub-optimality, typically $< 1\%$ for $L = 1000$ .
$f_{\text{SDR}}^{\text{rand}} - f_{\text{manifold}}$ : small, typically $< 1\%$ .
$f_{\text{manifold}} - f_{\text{elementwise}}$ : small at rank 1 (zero), larger at high rank.

Equality holds for rank-1 problems: all three algorithms achieve the global optimum.

SDR, Manifold, Element-wise Benchmark

Benchmark all three algorithms on the same problem instance. Plot achieved objective and runtime across $N$ from 16 to 256. Element-wise has the lowest runtime across the board but the largest gap; SDR becomes impractical at $N > 128$ .

Parameters

RIS elements

N

Rank of

\mathbf{A}

Monte-Carlo trials15

Include SDR (slow at large

N

)

🎓CommIT Contribution(2023)

Fast Manifold Optimization for Array-Fed RIS

G. Caire, I. Atzeni — IEEE Trans. Signal Process. (preprint)

Caire and collaborators (2023) adapt manifold optimization to the array-fed RIS architecture, exploiting the low-rank structure of the BS-RIS near-field channel. The key insight: the RIS aperture only needs to support $r \leq K$ eigenmodes (one per user), so the manifold optimization can be restricted to an $r$ -dimensional submanifold of the full torus. This reduces the per-iteration cost from $O(N^2)$ to $O(Nr)$ and converges in 10-20 iterations instead of 50-100. The algorithmic contribution enables real-time AO at $N = 2048$ and $K = 8$ with $\sim 5$ ms total optimization time — a $10\times$ speedup over generic Manopt. The result is directly instantiated in Chapter 11's array-fed architecture.

manifoldarray-fed-risreal-timecaire-2023

Example: Choosing the Algorithm: Three Scenarios

Recommend the best algorithm for each scenario:

(a) Research benchmark: $N = 64$ , $K = 4$ , goal: tightest possible bound on achievable rate. (b) Real-time deployment: $N = 512$ , $K = 8$ , coherence block $20\,\text{ms}$ , goal: best rate within 10 ms. (c) Ultra-low-power IoT RIS: $N = 32$ , $K = 1$ , goal: minimal compute, "good enough" rate.

Solution

Scenario (a) — benchmark

SDR with $L = 10\,000$ randomizations. Runtime $\sim 1$ s is acceptable offline. Provides tightest achievable rate bound for comparison with other methods. Manifold double-checks the result.

Scenario (b) — real-time

Manifold for initial cold start (5 ms on modern CPU for $N = 512, r = 8$ ), then element-wise for warm-start updates across coherence blocks (< 1 ms per block). Total budget $< 10$ ms achievable. SDR is infeasible at $N = 512$ .

Scenario (c) — IoT

Element-wise is optimal for single-user ( $K = 1$ , rank-1 $\mathbf{A}$ ). One sweep of $O(N) = 32$ complex ops; total compute $< 1\,\mu\text{s}$ on any microcontroller. No need for more sophisticated methods.

Takeaway

Algorithm choice is scenario-driven. Know the dominant constraint (compute time, solution quality, warm-start quality) and pick accordingly. $\blacksquare$

Key Takeaway

The three algorithms form a quality-speed Pareto frontier. SDR for quality, element-wise for speed, manifold for a balanced middle ground. At production scale ( $N \geq 256$ ), manifold with warm-starting is the typical choice; SDR is reserved for offline benchmarking; element-wise is the fallback for compute-constrained IoT or low-power scenarios. Rank-1 (single-user) problems are special: all three achieve the global optimum, and element-wise's speed wins unambiguously.

Common Mistake: Don't Use SDR Where It Doesn't Scale

Mistake:

"SDR has the best guarantees, so I'll use it even at $N = 1024$ ."

Correction:

SDR's $O(N^{6.5})$ complexity makes $N = 1024$ absolutely infeasible: $1024^{6.5} \approx 10^{19}$ flops, essentially intractable. Even $N = 256$ takes minutes per SDP solve. For $N > 128$ , use manifold. The quality loss vs. SDR is typically $< 1\%$ — negligible compared to the $1000\times$ speedup. Never force SDR onto a problem where it can't run in a reasonable time; the right choice is always the algorithm that fits the time budget.

Historical Note: The Three Traditions

2000s–2020s

The three algorithms trace to different mathematical traditions:

SDR: From convex optimization and operations research. Goemans–Williamson (1995) introduced $(\pi/4)$ -style approximations for MAX-CUT; Luo, Ma, and others extended to signal processing in the 2000s.
Manifold optimization: From differential geometry. Absil, Mahony, Sepulchre (2008) codified the unified framework; Manopt (Boumal et al. 2014) made it accessible to signal-processing researchers.
Element-wise BCD: From classical numerical analysis. Gauss-Seidel dates to 1823; its generalization to non-convex problems was matured by Powell (1970s) and Bertsekas (1990s).

All three converged on the RIS QCQP in $\sim 2019$ – $2020$ as the unified algorithmic toolkit for passive beamforming. The fact that three independent mathematical traditions all land on the same problem is a sign the problem is fundamental — and that the answer will generalize to future programmable-environment paradigms.

Quick Check

For an $N = 512$ RIS panel running in a real-time deployment (10 ms coherence block), which passive-beamforming algorithm is most appropriate?

SDR with Gaussian randomization

Manifold optimization with warm-starting

Grid search over 3-bit phases

Exhaustive brute force

Correction:

Manifold optimization with warm-starting

SDR's $O(N^{6.5})$ complexity is infeasible at $N=512$ . Manifold optimization with warm-starting scales as $O(N^2)$ per iteration and can complete within the 10 ms budget. Element-wise is also viable but gives a larger optimality gap at high rank.

Semidefinite Relaxation (SDR)

A convex relaxation technique: lift the vector variable $\boldsymbol{\phi}$ to a PSD matrix $\mathbf{X} = \boldsymbol{\phi}\boldsymbol{\phi}^H$ , relax the rank-1 constraint, solve the resulting SDP, and recover a feasible solution via Gaussian randomization. Provides a tight upper bound on the non-convex QCQP optimum but has $O(N^{6.5})$ complexity, limiting practical use to $N \leq 128$ .

Riemannian Manifold Optimization

Iterative optimization that respects the geometry of a constraint manifold (here, the complex unit-modulus torus). The Euclidean gradient is projected onto the tangent space; after a step, a retraction maps back to the manifold. Scales as $O(N^2)$ per iteration, making it the workhorse algorithm for large- $N$ RIS optimization.

Why This Matters: Same Algorithms, Other Problems

The unit-modulus QCQP reappears in many wireless contexts: radar waveform design (minimize sidelobe level subject to constant envelope), sensor array beamforming, phase retrieval (recover signal from $|\mathbf{A}\mathbf{x}|^2$ ), and hybrid analog-digital beamforming (phase shifters in RF chains). The algorithms of this chapter apply unchanged. The RIS community is a major user of these algorithms, but the tools are not RIS-specific — understanding them gives you a toolkit usable across wireless signal processing. Chapter 13 (RIS-ISAC) shows a direct transfer of these tools to the joint comm-radar objective.

See full treatment in Joint Sensing-Communication Signal Model

Element-wise Block Coordinate Descent Chapter Summary