Ferkans — Interactive Telecom Tutor

Skip the Continuous Detour

Projection works well but takes a continuous-phase detour. Direct discrete optimization works natively in $\mathcal{M}_B$ , potentially saving compute and recovering the small multi-user penalty of Section 8.2. The workhorse method is discrete BCD: update one $\phi_n$ at a time by choosing the best level from $\Theta_B$ . This reduces to solving an $L$ -way discrete optimization per coordinate — trivial at $L \leq 16$ . For very small $N$ ( $\leq 16$ ), branch-and-bound gives provable global optima. For very large $N$ with tight pilot budget, tabu search and simulated annealing serve as escape heuristics.

Discrete Block Coordinate Descent

Complexity:

O(S \cdot L \cdot N^2) = O(S N^2)

for

L

-level grid;

S \sim 5

-

10

sweeps.

Input: PSD

\mathbf{A} \in \mathbb{C}^{N \times N}

, bit-depth

B

, initial

\boldsymbol{\phi}^{(0)} \in \mathcal{M}_B

,

tolerance

\epsilon

, max sweeps

S_{\max}

.

Output: local discrete optimum

\boldsymbol{\phi}^\star \in \mathcal{M}_B

.

1. For

s = 0, 1, \ldots, S_{\max}

:

2.

\quad

For

n = 1, \ldots, N

:

3.

\quad\quad

Compute

\alpha_n = \sum_{m \neq n} A_{n,m}^* \phi_m^*

.

4.

\quad\quad

For each

\vartheta \in \Theta_B

:

5.

\quad\quad\quad

Evaluate

\phi_n = e^{j\vartheta}

; compute objective contribution

\Re(\phi_n \alpha_n) = |\alpha_n|\cos(\vartheta + \arg\alpha_n)

.

6.

\quad\quad

Pick

\vartheta^\star = \arg\max_{\vartheta \in \Theta_B}

; update

\phi_n \leftarrow e^{j\vartheta^\star}

.

7.

\quad

If no

\phi_n

changed: break.

8. return

\boldsymbol{\phi}

.

Step 5 is a closed-form maximization of a cosine over $L$ points; in fact, $\vartheta^\star$ is the nearest grid point to $-\arg \alpha_n$ . So the discrete BCD update is simply "continuous BCD result projected to the nearest grid level" — identical in the single-user case to Section 8.2.

Discrete BCD = Projected Continuous BCD

The closed-form continuous-BCD update is $\phi_n^\star = e^{j\arg\alpha_n}$ . The discrete-BCD update is $\phi_n^\star = e^{j \mathcal{P}_{\Theta_B}(\arg\alpha_n)}$ . For single-user (where one full continuous sweep already reaches the global optimum), this is just projection of the continuous sweep's output — no different from Section 8.2. Discrete BCD yields benefits over projection only in multi-user scenarios where multiple continuous-BCD sweeps are needed and the coupling between coordinates evolves across sweeps — the discrete update at sweep $s$ uses the already-quantized phases from the previous coordinate, not continuous values. This tracks the discrete feasibility at every step and recovers $\sim 0.1$ - $0.5\text{ dB}$ relative to projection-after-convergence.

Theorem: Monotone Convergence of Discrete BCD

Discrete BCD produces a monotone non-decreasing sequence of objective values $f(\boldsymbol{\phi}^{(s)})$ . Since $\mathcal{M}_B$ is finite and the iterates visit at most $|\mathcal{M}_B| = L^N$ distinct points, the algorithm terminates in at most $L^N$ iterations. In practice, 3-10 sweeps suffice for $\epsilon = 10^{-3}$ convergence.

At termination, the output is a coordinate-stationary point: no single-element update can improve the objective.

Same monotonicity argument as continuous BCD (Chapter 6), adapted to finite $\mathcal{M}_B$ . Each coordinate update picks the best discrete level, so the objective is non-decreasing. Since $\mathcal{M}_B$ has finitely many points and the objective is bounded, the sequence must eventually stabilize.

Proof

Monotonicity

By the $\arg\max$ definition, each coordinate update satisfies $f(\phi_n = \vartheta^\star) \geq f(\phi_n = \phi_n^{\text{old}})$ .

Termination

$\mathcal{M}_B$ is finite. Monotone non-decreasing sequence on a finite set must stabilize. $\blacksquare$

Branch-and-Bound for Small $N$

Complexity:

O(L^N)

worst case;

O(L^N \cdot \text{bound overhead})

typical but much faster with good bounds.

Input:

\mathbf{A}

, bit-depth

B

, current best

f^\star

.

Output: global optimum (for small

N

).

Branch-and-bound traverses the tree of partial solutions:

1. Root: no phases fixed. Upper bound via SDR relaxation on

\mathcal{M}_B

continuous relaxation.

2. Branch on element $n$ : try all

L = 2^B

values of

\phi_n \in \{e^{j k \Delta\theta}\}_{k=0}^{L-1}

, recurse.

3. Bound: at each node, compute the SDR upper bound for the remaining free phases.

Prune if the bound

<

current best

f^\star

.

4. Leaf: all phases fixed. Update

f^\star

if objective exceeds it.

Feasible for $N \leq 20$ or so in practice. The SDR upper bound at each node is the workhorse — it prunes most branches, giving orders-of-magnitude speedup over naive exhaustive search.

Example: Discrete BCD for a $N = 4$ , $B = 2$ Problem

For $\mathbf{A} = \mathbf{c}\mathbf{c}^H$ with $\mathbf{c} = [1, e^{j\pi/4}, j, -1]^T$ , initialize $\boldsymbol{\phi}^{(0)} = \mathbf{1}$ and perform one discrete BCD sweep with $B = 2$ ( $\Theta_2 = \{0, \pi/2, \pi, 3\pi/2\}$ ).

Solution

Continuous optimum for reference

$\theta_n^\star = -\arg c_n$ : $[-0, -\pi/4, -\pi/2, -\pi] = [0, -\pi/4, -\pi/2, \pi]$ . In $[0, 2\pi)$ : $[0, 7\pi/4, 3\pi/2, \pi]$ .

Discrete BCD: element 1

$\alpha_1 = \sum_{m > 1} A_{1,m}^* \phi_m^* = c_1^* \sum_{m>1} c_m$ (since $A_{1,m} = c_1 c_m^*$ ). Compute $\sum_{m>1} c_m = e^{j\pi/4} + j + (-1) = (\cos\pi/4 - 1, \sin\pi/4 + 1) \approx (-0.293, 1.707)$ . $\arg \alpha_1 \approx \pi - \arg((-0.293, 1.707)) = -1.739$ rad. Nearest level in $\{0, \pi/2, \pi, 3\pi/2\}$ : $3\pi/2 \approx 4.712$ ; equivalently $-\pi/2 \approx -1.571$ (closest to -1.739). Update $\phi_1 = e^{-j\pi/2}$ .

Elements 2, 3, 4

Continue similarly. After one sweep, all four phases are at their discrete matched-filter values (since this is a rank-1 / single-user problem, one sweep suffices). The result converges to the projection of the continuous optimum.

Verify

After one sweep, $\boldsymbol{\phi}^\star \approx [e^{-j\pi/2}, e^{-j\pi/4 \approx} e^{-j\pi/4 \to 0}, e^{-j\pi/2}, e^{j\pi}]$ (rounding each continuous to the nearest grid). Objective is close to $\eta_2 \|\mathbf{c}\|_1^2$ — the discrete-loss formula. $\blacksquare$

Discrete BCD vs. Projection

Compare discrete BCD and projection (with refinement) for the multi-user passive subproblem. At small $K$ the two coincide; at $K \geq 4$ discrete BCD recovers a small edge by tracking quantized coordinates during the iteration.

Parameters

RIS elements

N

64

Users

K

4

Bits per element

B

2

Monte-Carlo trials30

Discrete BCD: Rotating Through Phase Levels

Animation of one discrete-BCD sweep for

N = 8, B = 2

. Each element tries all 4 phase levels and picks the best; the chosen level is highlighted. After one full sweep, all phases have converged to their near-optimal grid points.

Common Mistake: Don't Over-Engineer: Projection Is Usually Enough

Mistake:

"I need the absolute best discrete solution, so I'll use branch-and-bound with SDR bounds."

Correction:

For most RIS problems ( $N \geq 16, K \leq 8, B \geq 2$ ), projection and discrete BCD produce essentially the same answer — within $0.1$ - $0.5\text{ dB}$ of each other. Branch-and-bound is only worth the complexity for very small $N$ (research comparison studies). In deployment, projection-then-refine is the pragmatic choice: 99% of the quality at 1% of the compute.

Direct Discrete Optimization