Ferkans — Interactive Telecom Tutor

ch17-ex01

Easy

(AMP Implementation and the Onsager Effect)

(a) Implement AMP with soft thresholding for $N = 500$ , $M = 200$ , i.i.d. Gaussian $\mathbf{A}$ , Bernoulli-Gaussian reflectivity with $\rho = 0.1$ , $\text{SNR} = 25\,\text{dB}$ .

(b) Plot NMSE vs. iteration for 50 iterations.

(c) Remove the Onsager correction and plot the resulting ISTA convergence alongside AMP.

(d) Quantify the NMSE gap at convergence.

Show Hint

Initialize with $\hat{\mathbf{c}}^0 = \mathbf{0}$ , $\mathbf{r}^{-1} = \mathbf{0}$ .

The average derivative for soft thresholding is the fraction of active components.

Solution

Implementation

The AMP iteration is: $\mathbf{r}^t = \mathbf{y} - \mathbf{A}\hat{\mathbf{c}}^t + \frac{N}{M}\langle\eta'_{t-1}\rangle\mathbf{r}^{t-1}$ , $\hat{\mathbf{c}}^{t+1} = \eta_t(\mathbf{A}^{\mathsf{T}} \mathbf{r}^t + \hat{\mathbf{c}}^t)$ .

Result

AMP converges to NMSE $\approx -20\,\text{dB}$ in $\sim$ 15 iterations. ISTA converges to NMSE $\approx -10\,\text{dB}$ in $\sim$ 40 iterations — a 10 dB gap demonstrating the power of the Onsager correction.

ch17-ex02

Easy

(State Evolution Verification)

(a) Implement the AMP state evolution recursion $\tau_{t+1} = \sigma^2 + \frac{1}{\delta} \mathbb{E}[|\eta_t(C_0 + \sqrt{\tau_t}Z) - C_0|^2]$ with numerical integration.

(b) Run AMP for $N = 2000$ and compare empirical MSE with SE.

(c) Repeat for $N = 100, 500, 5000$ . At what $N$ does the empirical MSE match SE to within 5%?

Show Hint

Evaluate the expectation by sampling $C_0 \sim p_0$ and $Z \sim \mathcal{N}(0,1)$ .

Solution

SE implementation

Sample $10^4$ draws of $(C_0, Z)$ . For each $\tau_t$ , compute the denoiser output $\eta_t(C_0 + \sqrt{\tau_t}Z)$ and average the squared error.

Convergence

For $N = 500$ , SE matches to within 10%. For $N = 2000$ , the match is within 3%. SE is essentially exact for $N \geq 1000$ .

ch17-ex03

Easy

(AMP Divergence on Structured Matrices)

(a) Generate three sensing matrices with $M = 400$ , $N = 1000$ : (i) i.i.d. Gaussian, (ii) partial DCT, (iii) Kronecker $\mathbf{A}_{1} \otimes \mathbf{A}_{2}$ with Gaussian factors.

(b) Run AMP with soft thresholding on each. Plot NMSE vs. iteration.

(c) Which matrices cause divergence?

(d) Compare the eigenvalue distributions of $\mathbf{A}^{H}\mathbf{A}$ for each.

Show Hint

The Marchenko-Pastur distribution describes eigenvalues of i.i.d. Gaussian matrices.

Solution

Results

(i) Gaussian: converges to NMSE $\approx -18\,\text{dB}$ . (ii) Partial DCT: oscillates and diverges. (iii) Kronecker: diverges after $\sim$ 5 iterations. The eigenvalue spread of (ii) and (iii) far exceeds the Marchenko-Pastur prediction.

ch17-ex04

Easy

(Basic OAMP Implementation)

(a) Implement OAMP with soft thresholding for $N = 500$ , $M = 200$ , i.i.d. Gaussian $\mathbf{A}$ .

(b) Compare OAMP and AMP on this Gaussian matrix. Verify they achieve the same NMSE.

(c) Replace $\mathbf{A}$ with a partial DCT matrix. Run both algorithms. Verify AMP diverges while OAMP converges.

(d) Report the SVD computation time for the $200 \times 500$ matrix.

Show Hint

Compute the SVD once and reuse singular values in the LMMSE step.

Solution

Gaussian matrix

Both AMP and OAMP converge to NMSE $\approx -20\,\text{dB}$ (within numerical precision), confirming they are equivalent for i.i.d. Gaussian matrices.

Partial DCT

AMP diverges; OAMP converges to NMSE $\approx -17\,\text{dB}$ in 20 iterations. The SVD takes $\sim$ 10 ms for $200 \times 500$ .

ch17-ex05

Easy

(Verifying the Orthogonality Condition)

(a) Run OAMP on a partial DCT matrix with $N = 500$ , $M = 200$ . At each iteration, compute $\rho^t = \frac{|\mathbf{e}_1^{t\,H}\mathbf{e}_2^{t-1}|} {\|\mathbf{e}_1^t\|\|\mathbf{e}_2^{t-1}\|}$ .

(b) Plot $\rho^t$ vs. iteration. Verify it stays near zero.

(c) Repeat for AMP (with and without Onsager) on the same matrix.

Show Hint

The orthogonality condition is the property that distinguishes OAMP from AMP for structured matrices.

Solution

Orthogonality verification

For OAMP, $\rho^t < 0.02$ at all iterations. For AMP with Onsager on the DCT matrix, $\rho^t$ grows to $> 0.5$ (correlation, not decorrelation). For ISTA (no Onsager), $\rho^t \approx 0.3$ – $0.5$ .

ch17-ex06

Medium

(OAMP State Evolution)

(a) Implement the two-step OAMP state evolution: $v_1^t = F(v_2^{t-1})$ (from singular values) and $v_2^t = \text{mmse}(\eta_t, v_1^t)$ .

(b) Run OAMP with BG-MMSE denoiser for $N = 1000$ , $\delta = 0.4$ , $\rho = 0.1$ , $\text{SNR} = 25\,\text{dB}$ on a Kronecker partial-DFT matrix.

(c) Compare empirical MSE with SE prediction at each iteration.

(d) Plot the SE fixed-point NMSE vs. $\delta$ for $\delta \in [0.2, 0.8]$ .

Show Hint

The LMMSE MSE depends on the singular values via $v_1^t = \frac{1}{N}\sum_i \frac{\sigma^2 v_2^{t-1}}{\sigma^2 + v_2^{t-1} s_i^2}$ .

Solution

SE accuracy

SE tracks empirical NMSE within 0.5 dB for $N = 1000$ . The fixed-point NMSE decreases monotonically with $\delta$ (more measurements improve reconstruction).

ch17-ex07

Medium

(BG-MMSE Denoiser Derivation and Implementation)

(a) Derive the Bayes-optimal denoiser for the Bernoulli-Gaussian prior $p_0(c) = (1-\rho)\delta(c) + \rho\,\mathcal{CN}(0, \sigma_c^2)$ .

(b) Implement the denoiser and verify on synthetic data.

(c) Compute the divergence analytically.

(d) Compare OAMP with BG-MMSE vs. soft thresholding at $\delta = 0.3$ , $\rho = 0.1$ , $\text{SNR} = 25\,\text{dB}$ .

(e) Repeat with Bernoulli-Rademacher prior.

Show Hint

The posterior mean is a weighted average of 0 (inactive) and the Gaussian posterior mean (active).

Solution

Derivation

$\eta_{\text{BG}}(r) = \pi(r) \cdot \frac{\sigma_c^2} {\sigma_c^2 + v} \cdot r$ , where $\pi(r) = \frac{\rho\,\mathcal{CN}(r; 0, \sigma_c^2 + v)} {(1-\rho)\mathcal{CN}(r; 0, v) + \rho\,\mathcal{CN}(r; 0, \sigma_c^2 + v)}$ is the posterior activity probability.

Comparison

BG-MMSE outperforms soft thresholding by $\sim$ 3 dB at $\delta = 0.3$ .

ch17-ex08

Medium

(Kronecker LMMSE Speedup)

(a) Implement the naive OAMP LMMSE step (forming $\mathbf{A}^{H}\mathbf{A}$ and inverting).

(b) Implement the Kronecker-factored LMMSE step.

(c) Verify both produce the same output (up to numerical precision).

(d) Benchmark both for $N_1 = N_2 \in \{16, 32, 64, 128\}$ . Plot wall-clock time vs. $N = N_1 N_2$ .

(e) At what $N$ does the Kronecker version become 100x faster?

Show Hint

Use the Kronecker SVD: $\text{svd}(\mathbf{A}_{1} \otimes \mathbf{A}_{2}) = (\mathbf{U}_1 \otimes \mathbf{U}_2)(\boldsymbol{\Sigma}_1 \otimes \boldsymbol{\Sigma}_2)(\mathbf{V}_1 \otimes \mathbf{V}_2)^H$ .

Solution

Verification

The outputs agree to machine precision ( $\sim 10^{-12}$ relative error).

Speedup

The 100x speedup is achieved at $N \approx 4096$ ( $N_1 = N_2 = 64$ ). At $N = 16384$ the speedup exceeds $10^4$ .

ch17-ex09

Medium

(Hutchinson Trace Estimator)

(a) Implement the Hutchinson estimator for the divergence of soft thresholding (where the true divergence is known).

(b) Plot estimation error vs. perturbation size $h$ for $h \in [10^{-8}, 10^{-1}]$ .

(c) For a black-box denoiser (use a small MLP), estimate the divergence with 1, 3, 5, 10 probe vectors. Plot the variance of the estimate vs. number of probes.

(d) Run OAMP with Hutchinson divergence estimation and compare with analytical divergence.

Show Hint

Use $h \approx N^{-1/3}$ for optimal bias-variance tradeoff.

Solution

Optimal $h$

For $N = 500$ , the optimal $h \approx 0.012$ . For $h < 10^{-6}$ , numerical cancellation dominates.

Probe vectors

A single probe vector gives $< 5\%$ relative error for $N \geq 500$ . For $N < 100$ , use 3–5 probes.

ch17-ex10

Medium

(Sparsity Mismatch Analysis)

(a) Generate a BG signal with $\rho_0 = 0.10$ . Run OAMP with BG-MMSE denoiser assuming $\tilde{\rho} \in \{0.01, 0.05, 0.10, 0.15, 0.20, 0.30\}$ .

(b) Plot converged NMSE vs. $\tilde{\rho}$ .

(c) Run mismatched state evolution and verify it predicts the empirical NMSE.

(d) Explain why underestimating $\rho$ is more harmful than overestimating.

Show Hint

The mismatched SE uses the true prior in the expectation but the assumed denoiser.

Solution

Asymmetry

Underestimating $\rho$ causes the denoiser to zero out true scatterers (false negatives), which is irreversible. Overestimating $\rho$ preserves noise components (false positives), which the LMMSE step partially corrects.

ch17-ex11

Medium

(Complex-Valued OAMP)

(a) Extend the OAMP algorithm to complex-valued signals $\mathbf{c} \in \mathbb{C}^N$ and measurements.

(b) Derive the complex BG-MMSE denoiser for $p_0(c) = (1-\rho)\delta(c) + \rho\,\mathcal{CN}(0, \sigma_c^2)$ .

(c) Implement and test on a complex Kronecker sensing matrix with $N = 1024$ , $M = 400$ .

(d) Compare with the real-valued case (same dimensions and SNR).

Show Hint

For complex Gaussian noise, the LMMSE formula is the same as the real case with $\sigma^2$ per complex dimension.

Solution

Complex denoiser

The complex BG-MMSE denoiser has the same structure as the real case but with $|r|^2$ and $\sigma_c^2 + v$ in place of $r^2$ and $\sigma_c^2 + v$ . The divergence uses the Wirtinger derivative.

Performance

Complex OAMP achieves comparable NMSE to the real case at the same effective SNR (per complex component).

ch17-ex12

Medium

(Comparison of Denoisers in OAMP)

(a) Implement OAMP with three denoisers: soft thresholding, BG-MMSE, and a small DnCNN (3-layer CNN).

(b) Train the DnCNN on 1000 BG images at various noise levels.

(c) Run all three on the same Kronecker sensing problem with $N = 1024$ , $\delta = 0.4$ , $\rho = 0.1$ , $\text{SNR} = 25\, \text{dB}$ .

(d) Plot NMSE vs. iteration for all three.

(e) Repeat with an extended-target scene (piecewise constant).

Show Hint

Train the DnCNN with noise levels $\sigma \in [0.01, 1.0]$ to cover the range of $\sqrt{v_1^t}$ values.

Solution

BG scene

BG-MMSE and DnCNN achieve similar NMSE ( $\sim -22\, \text{dB}$ ); soft thresholding is $\sim$ 3 dB worse.

Extended target

DnCNN outperforms BG-MMSE by $\sim$ 4 dB because the extended target violates the BG prior.

ch17-ex13

Hard

(Damped AMP vs OAMP)

(a) Implement damped AMP with damping parameter $\alpha \in \{0.1, 0.3, 0.5, 0.7, 1.0\}$ on a Kronecker partial-DFT matrix with $N = 1024$ , $M = 400$ .

(b) For each $\alpha$ , find the converged NMSE (if it converges).

(c) Compare the best damped-AMP result with OAMP.

(d) Explain why damping cannot match OAMP's performance even when it stabilizes convergence.

Show Hint

Damping replaces $\hat{\mathbf{c}}^{t+1} = \alpha\,\eta_t(\mathbf{q}^t) + (1-\alpha)\hat{\mathbf{c}}^t$ .

Solution

Damped AMP results

Best damped AMP ( $\alpha = 0.3$ ): NMSE $\approx -12\, \text{dB}$ . OAMP: NMSE $\approx -22\,\text{dB}$ . Damping stabilizes but loses the Gaussian-channel equivalence — the denoiser receives biased input.

ch17-ex14

Hard

(OAMP Phase Transition)

(a) For OAMP with BG-MMSE denoiser and Kronecker partial-DFT $\mathbf{A}$ , compute the SE-predicted phase transition in the $(\delta, \rho)$ plane.

(b) Define success as NMSE $< -20\,\text{dB}$ after 50 SE iterations. Plot the boundary.

(c) Compare with the AMP phase transition for i.i.d. Gaussian $\mathbf{A}$ at the same $(\delta, \rho)$ grid.

(d) How much does the Kronecker structure degrade the phase transition compared to i.i.d. Gaussian?

Show Hint

The OAMP phase transition depends on the singular value distribution of $\mathbf{A}$ , not just $\delta$ .

Solution

Phase transition comparison

The Kronecker partial-DFT phase transition is shifted rightward by $\Delta\delta \approx 0.05$ – $0.10$ compared to i.i.d. Gaussian. The degradation is due to the non-uniform singular value distribution: some directions are poorly measured.

ch17-ex15

Hard

(Variance Mismatch Analysis)

(a) Generate a BG signal with $\sigma_c^2 = 1.0$ . Run OAMP with BG-MMSE assuming $\tilde{\sigma}_c^2 \in \{0.1, 0.3, 0.5, 1.0, 2.0, 5.0, 10.0\}$ .

(b) Plot NMSE vs. $\tilde{\sigma}_c^2$ .

(c) Compare the sensitivity to variance mismatch with sparsity mismatch (Exercise 10).

(d) For a scene with unknown statistics, propose a strategy that is robust to both types of mismatch.

Show Hint

Variance mismatch affects the shrinkage factor in the BG-MMSE denoiser.

Solution

Sensitivity comparison

A 10x variance mismatch causes $\sim$ 6 dB degradation. A 3x sparsity mismatch causes $\sim$ 4 dB degradation. Variance mismatch is slightly more harmful.

Robust strategy

Use EM-OAMP to learn both $\rho$ and $\sigma_c^2$ from the data, or use a learned denoiser that does not assume a parametric prior.

ch17-ex16

Hard

(Near-Field Kronecker Approximation Error)

(a) For a near-field UPA geometry ( $d = 5\lambda$ , aperture $= 32\lambda$ ), compute the exact sensing matrix $\mathbf{A}$ and its best Kronecker approximation $\mathbf{A}_{1} \otimes \mathbf{A}_{2}$ .

(b) Compute the relative approximation error $\|\mathbf{A} - \mathbf{A}_{1} \otimes \mathbf{A}_{2}\|_F / \|\mathbf{A}\|_F$ .

(c) Run OAMP with the exact SVD and with the Kronecker-approximate SVD. How much NMSE does the approximation cost?

(d) At what distance does the Kronecker approximation become acceptable (< 1 dB NMSE penalty)?

Show Hint

The Kronecker approximation is equivalent to the best rank-1 approximation of the matricized sensing operator.

Solution

Near-field error

At $d = 5\lambda$ , the Kronecker approximation error is $\sim$ 8%, causing $\sim$ 2 dB NMSE degradation. At $d = 20\lambda$ , the error drops to $< 1\%$ and the NMSE penalty is $< 0.3\,\text{dB}$ .

ch17-ex17

Hard

(OAMP with Learned Denoiser)

(a) Train a noise-level-conditional DnCNN on 5000 BG scenes with $N = 32 \times 32$ at noise levels $\sigma \in [0.01, 1.0]$ .

(b) Plug the trained DnCNN into OAMP using the Hutchinson divergence estimator.

(c) Compare with BG-MMSE OAMP on: (i) BG scenes, (ii) piecewise- constant scenes, (iii) smooth Gaussian-process scenes.

(d) Plot NMSE vs. iteration for all three scene types.

(e) Discuss when the learned denoiser helps and when BG-MMSE is sufficient.

Show Hint

Feed $\sqrt{v_1^t}$ as a second input channel to the DnCNN.

Solution

Results

(i) BG: DnCNN $\approx$ BG-MMSE ( $-22\,\text{dB}$ ). (ii) Piecewise constant: DnCNN $-19\,\text{dB}$ , BG-MMSE $-14\,\text{dB}$ . (iii) GP: DnCNN $-17\,\text{dB}$ , BG-MMSE $-11\,\text{dB}$ . The learned denoiser excels on non-BG scenes.

ch17-ex18

Challenge

(Large-Scale Kronecker OAMP with GPU Acceleration)

(a) Implement Kronecker-factored OAMP on GPU (PyTorch or CuPy) for $N_1 = N_2 = 128$ ( $N = 16384$ ).

(b) Benchmark against CPU implementation. Report speedup.

(c) Profile memory usage. What is the memory bottleneck?

(d) Run OAMP for 30 iterations at $\delta = 0.4$ , $\text{SNR} = 25\,\text{dB}$ , $\rho = 0.05$ . Report wall-clock time and final NMSE.

(e) Push to $N_1 = N_2 = 256$ ( $N = 65536$ ). Does it still fit in GPU memory?

Show Hint

Use batched matrix multiplication for the Kronecker LMMSE step.

Solution

GPU speedup

GPU provides $\sim$ 20x speedup over CPU for $N = 16384$ . For $N = 65536$ ( $N_1 = N_2 = 256$ ), the singular value arrays and intermediate matrices require $\sim$ 4 GB; it fits on an A100 (40 GB) but not on consumer GPUs.

ch17-ex19

Challenge

(EM-OAMP for Unknown Prior Parameters)

(a) Implement EM-OAMP: alternate OAMP iterations with M-step updates of $\rho$ and $\sigma_c^2$ .

(b) Initialize with deliberately wrong parameters ( $\tilde{\rho} = 0.5$ , $\tilde{\sigma}_c^2 = 10$ ) and track the parameter estimates across EM iterations.

(c) Does EM-OAMP converge to the true parameters?

(d) Compare the final NMSE with oracle OAMP (true parameters known) and mismatched OAMP (fixed wrong parameters).

(e) Test robustness: repeat with non-BG scenes. Does EM-OAMP still find useful parameters?

Show Hint

The M-step update for $\rho$ : $\tilde{\rho}^{(k+1)} = \frac{1}{N}\sum_i \pi_i$ where $\pi_i$ is the posterior activity probability.

Solution

EM convergence

EM-OAMP converges to within 5% of the true parameters in 5–8 outer iterations. Final NMSE is within 0.5 dB of the oracle. For non-BG scenes, EM finds an effective BG approximation that outperforms random guessing but underperforms a learned denoiser.

ch17-ex20

Challenge

(Full RF Imaging Pipeline: From Measurements to Image)

(a) Set up a complete RF imaging scenario: 8-element ULA Tx, 8-element ULA Rx, 64 OFDM subcarriers, 2D scene with $32 \times 32$ voxels.

(b) Construct the Kronecker-structured sensing matrix from the array geometry and subcarrier frequencies.

(c) Generate a realistic scene with 5 point scatterers and a reflecting wall. Compute noiseless and noisy measurements.

(d) Reconstruct using: (i) backpropagation, (ii) LASSO via FISTA, (iii) OAMP with BG-MMSE, (iv) OAMP with a simple trained denoiser.

(e) Compare all methods in NMSE, visual quality, and computation time. Which is best and why?

Show Hint

The sensing matrix factors are partial DFT matrices weighted by the array steering vectors.

Solution

Pipeline

Construct $\mathbf{A}_{1}$ (frequency $\times$ range) and $\mathbf{A}_{2}$ (array $\times$ angle). Apply OAMP with Kronecker factorization.

Results

Backpropagation: $-5\,\text{dB}$ (severe sidelobes). FISTA: $-12\,\text{dB}$ (slow, 500 iterations). OAMP BG-MMSE: $-20\,\text{dB}$ (20 iterations). OAMP + denoiser: $-23\,\text{dB}$ (best for the wall). OAMP methods are fastest after SVD preprocessing.

Exercises

ch17-ex01

Implementation

Result

ch17-ex02

SE implementation

Convergence

ch17-ex03

Results

ch17-ex04

Gaussian matrix

Partial DCT

ch17-ex05

Orthogonality verification

ch17-ex06

SE accuracy

ch17-ex07

Derivation

Comparison

ch17-ex08

Verification

Speedup

ch17-ex09

Optimal $h$

Probe vectors

ch17-ex10

Asymmetry

ch17-ex11

Complex denoiser

Performance

ch17-ex12

BG scene

Extended target

ch17-ex13

Damped AMP results

ch17-ex14

Phase transition comparison

ch17-ex15

Sensitivity comparison

Robust strategy

ch17-ex16

Near-field error

ch17-ex17

Results

ch17-ex18

GPU speedup

ch17-ex19

EM convergence

ch17-ex20

Pipeline

Results