Ferkans — Interactive Telecom Tutor

ex01-lasso-implementation

Easy

(a) Generate a 1D sparse signal $\mathbf{c}_{0} \in \mathbb{C}^{256}$ with $s = 10$ nonzero entries (random complex amplitudes). Create measurements $\mathbf{y} = \mathbf{A}\mathbf{c}_{0} + \mathbf{w}$ with Gaussian $\mathbf{A} \in \mathbb{C}^{100 \times 256}$ and $\text{SNR} = 25$ dB.

(b) Implement FISTA with complex soft-thresholding. Run for 200 iterations with step size $\mu = 1/L_f$ .

(c) Plot the objective function $F(\mathbf{c}^{(t)})$ vs. iteration and verify the $O(1/t^2)$ rate.

(d) Implement the debiasing step: restrict to the detected support and solve least-squares. Compare the amplitude error before and after debiasing.

Show Hint

Compute $L_f$ as the largest singular value squared of $\mathbf{A}$ via power iteration.

Complex soft-thresholding: $\mathcal{S}_\tau(z) = z \max(1 - \tau/|z|, 0)$ .

Solution

FISTA convergence

The convergence curve should show $F(\mathbf{c}^{(t)}) - F^* \propto 1/t^2$ . Plot on a log-log scale and verify the slope is approximately $-2$ .

Debiasing effect

Debiasing typically reduces the amplitude RMSE by 30--50% because it removes the $\lambda$ -dependent shrinkage.

ex02-lambda-selection

Easy

Using the setup from Exercise 1:

(a) Run FISTA for $\lambda \in \{10^{-4}, 10^{-3}, 10^{-2}, 10^{-1}, 1\}$ . For each, record the final NMSE and $\|\hat{\mathbf{c}}\|_0$ .

(b) Implement the discrepancy principle: find $\lambda$ such that $\|\mathbf{A}\hat{\mathbf{c}} - \mathbf{y}\|_2 = \sqrt{M}\sigma$ via bisection search.

(c) Implement 5-fold cross-validation on 20% held-out measurements.

(d) Compare the three methods (grid search, discrepancy, CV). Which yields the lowest NMSE?

Show Hint

For bisection, use log-scale search: $\lambda \in [10^{-5}, 10]$ .

Solution

Expected outcome

The discrepancy principle should yield NMSE within 1 dB of the optimal grid-search value because it directly matches the noise level. CV may be slightly worse due to the measurement splitting.

ex03-admm-lasso

Easy

(a) Implement ADMM for the LASSO with splitting $\mathbf{c} = \mathbf{z}$ , penalty $\rho = 1$ .

(b) Run for 100 iterations. Plot primal and dual residuals.

(c) Implement adaptive $\rho$ (residual balancing, $\tau = 2$ , $\mu = 10$ ). Compare convergence with fixed $\rho$ .

(d) Compare the final ADMM solution with FISTA. Verify they are identical up to numerical precision.

Show Hint

Precompute the Cholesky factorization of $\mathbf{A}^{H}\mathbf{A} + \rho\mathbf{I}$ for the $\mathbf{c}$ -update.

Solution

Adaptive $\rho$ advantage

Adaptive $\rho$ typically converges in 30--40% fewer iterations than fixed $\rho$ , because it balances the primal and dual convergence rates.

ex04-2d-imaging

Medium

(a) Create a 2D MIMO radar imaging setup: $N_t = 4$ , $N_r = 8$ , $N_f = 32$ at 10 GHz with 2 GHz bandwidth. Scene: $32 \times 32$ grid, 8 point scatterers. $\text{SNR} = 20$ dB.

(b) Compute the matched filter image $\hat{\mathbf{c}}_{\text{MF}} = \mathbf{A}^{H}\mathbf{y}$ .

(c) Run FISTA for 100 iterations. Compare MF and FISTA in NMSE, SSIM, and support F1-score.

(d) Apply debiasing. How much does it improve the amplitude RMSE?

(e) Vary $\text{SNR}$ from 5 to 40 dB. Plot NMSE vs. $\text{SNR}$ for MF, FISTA, and FISTA+debiasing.

Show Hint

Use Kronecker structure for fast matvec: $\mathbf{A} = \mathbf{A}_{1} \otimes \mathbf{A}_{2}$ .

Solution

Key result

FISTA should outperform MF by 10--15 dB in NMSE. Debiasing adds 1--3 dB improvement. The advantage grows with SNR because the LASSO can better separate signal from noise.

ex05-tv-imaging

Medium

(a) Create a 2D scene ( $64 \times 64$ ) with 3 extended targets: a rectangle, a circle, and an L-shape. All piecewise-constant.

(b) Generate compressed measurements ( $M/N = 0.3$ ) using a random sensing matrix. $\text{SNR} = 20$ dB.

(c) Reconstruct using: (i) $\ell_1$ (FISTA), (ii) isotropic TV (ADMM), (iii) anisotropic TV (ADMM).

(d) Compare NMSE, SSIM, and edge preservation.

(e) Add 5 point scatterers to the scene. Reconstruct with $\ell_1$ , TV, and $\ell_1$ + TV. Show that the combined penalty is superior for this mixed scene.

Show Hint

For TV ADMM, use CG with $\sim$ 10 inner iterations for the $\mathbf{c}$ -update.

Solution

Expected ranking

For pure extended targets: TV > anisotropic TV > $\ell_1$ . For mixed scenes: $\ell_1$ + TV > TV > $\ell_1$ . Isotropic TV preserves diagonal edges better than anisotropic.

ex06-group-lasso

Medium

(a) Create a radar imaging scene where each scatterer has a frequency-dependent reflectivity: $c_k(f) = \alpha_k(f/f_0)^\beta$ with random $\beta \in [-2, 2]$ . Grid: $32 \times 32$ , 4 frequency bands, $s = 6$ scatterers.

(b) Formulate as a group LASSO with groups = (pixel, all frequencies). Group size $d = 4$ .

(c) Solve with: (i) standard LASSO (independent per frequency), (ii) group LASSO (FISTA with block soft-thresholding).

(d) Compare support recovery F1-score and amplitude RMSE.

(e) Reduce measurements per band to 50% of Nyquist. How much does group LASSO improve over standard LASSO?

Show Hint

Block soft-thresholding: $\text{prox}_{\lambda\|\cdot\|_2}(\mathbf{z}) = \mathbf{z}\max(1 - \lambda/\|\mathbf{z}\|_2, 0)$ .

Solution

Expected improvement

Group LASSO should improve support F1 by 15--25% at moderate SNR because it borrows strength across frequencies. The improvement is largest at the 50% compression level.

ex07-omp-vs-lasso

Medium

(a) Generate 1D imaging problems with $N = 512$ , $M = 128$ , and varying sparsity $s \in \{5, 10, 20, 30, 40, 50\}$ . $\text{SNR} = 20$ dB.

(b) For each $s$ , run: OMP (stopping at $s$ iterations), CoSaMP ( $s$ target sparsity), and LASSO (FISTA, optimal $\lambda$ ).

(c) Plot NMSE vs. $s$ for all three methods. At what $s$ does each method start failing?

(d) Plot computation time vs. $s$ . At what $s$ is OMP faster than FISTA?

(e) Make the signal compressible (power-law decay with $q = 0.5$ ). How do the results change?

Show Hint

OMP fails when $s$ exceeds the coherence limit; FISTA handles compressible signals gracefully.

Solution

Crossover point

OMP is typically faster for $s \lesssim 20$ and fails for $s > M/(4\log(N/s))$ . FISTA is more robust and remains effective for compressible signals where $s$ is not well defined.

ex08-admm-composite

Hard

(a) Implement ADMM for the composite problem: $\min \frac{1}{2}\|\mathbf{A}\mathbf{c}-\mathbf{y}\|^2 + \lambda_1\|\mathbf{c}\|_1 + \lambda_2\|\mathbf{c}\|_{\text{TV}}$ . Use two splitting variables.

(b) Create a scene with 5 point scatterers and 2 extended targets. $N = 64 \times 64$ , $M = 2048$ , $\text{SNR} = 20$ dB.

(c) Sweep $(\lambda_1, \lambda_2)$ on a $10 \times 10$ grid. Plot the 2D NMSE surface.

(d) Find the optimal $(\lambda_1^*, \lambda_2^*)$ . How does the ratio $\lambda_1^*/\lambda_2^*$ relate to the scene composition?

(e) Compare pure $\ell_1$ , pure TV, and the optimal combination.

Show Hint

The $\mathbf{c}$ -update requires solving a linear system involving $\mathbf{A}^{H}\mathbf{A} + \rho_1\mathbf{I} + \rho_2\nabla_D^H\nabla_D$ .

Solution

Optimal ratio

The optimal $\lambda_1^*/\lambda_2^*$ ratio is typically proportional to the ratio of point scatterers to extended target edge pixels. More point targets favor larger $\lambda_2^*/\lambda_1^*$ .

ex09-gridless-refinement

Hard

(a) Generate a scene with 5 point scatterers at off-grid positions on a $64$ -point grid.

(b) Solve standard LASSO on the grid. Identify detected scatterers.

(c) Implement SPARROW-style refinement: parameterize $\mathbf{p}_{k} = \mathbf{p}_{n_k} + \delta_k$ and optimize $\delta_k$ by gradient descent on the data fidelity.

(d) Compare position error (RMSE) before and after refinement.

(e) Increase grid density to $N = 128, 256, 512$ . At what density does refinement become unnecessary?

Show Hint

The position gradient involves $\partial\mathbf{a}(\mathbf{p})/\partial\mathbf{p}$ .

Solution

Refinement benefit

SPARROW refinement typically reduces position RMSE by 5--10x for coarse grids. At $N = 512$ (fine grid), the improvement is marginal ( $< 1.5$ x).

ex10-mmv-radar

Hard

(a) Simulate radar observing $s = 10$ scatterers across $L = 1, 2, 4, 8, 16, 32$ snapshots. $M = 200$ , $N = 1024$ . $\text{SNR} = 10$ dB per snapshot. Swerling I amplitudes.

(b) For each $L$ , solve: (i) independent LASSO per snapshot then threshold the average support, (ii) MMV ( $\ell_{2,1}$ ).

(c) Plot support F1-score vs. $L$ for both methods.

(d) What is the minimum $L$ for 90% support detection?

(e) Compute the "snapshot gain" (dB equivalent of extra measurements from joint processing).

Show Hint

MMV primarily improves support detection; amplitude estimation benefits from averaging after support recovery.

Solution

Snapshot gain

MMV typically achieves the same support F1 with 2--4x fewer snapshots than independent LASSO. The equivalent SNR gain is $\sim 3$ -- $6$ dB.

ex11-pesavento

Hard

(a) Implement the Pesavento iteratively reweighted $\ell_{2,1}$ algorithm (IR- $\ell_{2,1}$ ) for the MMV problem.

(b) Compare with standard group LASSO on the multi-frequency imaging setup from Exercise 6.

(c) Run for 10 outer reweighting iterations. Plot the support F1-score vs. outer iteration.

(d) Does IR- $\ell_{2,1}$ converge to a sparser solution than standard group LASSO? Count the number of nonzero rows.

(e) Compare the computational cost per outer iteration with solving a single group LASSO from scratch.

Show Hint

Use the weight update $w_i^{(t+1)} = 1/(\|\mathbf{X}_{i,:}^{(t)}\|_2 + \epsilon)$ with $\epsilon = 10^{-6}$ .

Solution

Expected behavior

IR- $\ell_{2,1}$ typically converges in 5--8 outer iterations and produces 20--30% fewer false positives than standard group LASSO, because the reweighting approximates $\ell_{2,0}$ .

ex12-tgv

Hard

(a) Create a scene with a target whose reflectivity varies linearly (gradient from $c = 0.2$ to $c = 0.8$ across a $20 \times 20$ region) surrounded by zero background.

(b) Reconstruct with: (i) isotropic TV (ADMM), (ii) TGV order 2 (ADMM with two auxiliary variables).

(c) Compare visually: does TV produce staircase artifacts? Does TGV recover the smooth gradient?

(d) Sweep the TGV parameters $(\alpha_0, \alpha_1)$ and find the optimal ratio $\alpha_0/\alpha_1$ .

(e) Add sharp edges to the scene (a rectangular cutout inside the gradient region). Does TGV preserve both the edges and the smooth gradient?

Show Hint

TGV ADMM requires two splitting variables: $\mathbf{z}_1 = \nabla_D\mathbf{c} - \mathbf{p}$ and $\mathbf{z}_2 = \mathcal{E}(\mathbf{p})$ .

Solution

Staircase effect

TV approximates the linear gradient with 5--10 constant steps (staircase). TGV with appropriate $\alpha_0/\alpha_1 \approx 2$ recovers the smooth gradient with NMSE improvement of 5--8 dB.

ex13-algorithm-comparison

Hard

Build a systematic comparison of all algorithms on a standardized RF imaging benchmark:

(a) Setup: MIMO radar, $N_t = 4$ , $N_r = 8$ , $N_f = 64$ ( $M = 2048$ ). Scene: $32 \times 32$ ( $N = 1024$ ). Three sparsity levels: $s = 5, 15, 30$ . $\text{SNR} = 20$ dB.

(b) Algorithms: Matched filter, FISTA, ADMM, OMP, CoSaMP, IHT.

(c) Metrics: NMSE, support F1, computation time, iterations to $-15$ dB NMSE.

(d) Create a comparison table. For each $s$ , rank by NMSE and by speed.

(e) Plot Pareto fronts (NMSE vs. time) for each $s$ . Which algorithms are Pareto-optimal?

Show Hint

Use warm-starting (initialize from matched filter) for faster convergence.

Solution

Expected Pareto front

For $s = 5$ : OMP dominates the fast region, FISTA the accurate region. For $s = 30$ : FISTA dominates everywhere; greedy methods fail. ADMM with TV is Pareto-optimal for mixed scenes.

ex14-atomic-norm

Hard

(a) Implement the atomic norm SDP for a ULA with $M = 16$ elements. Use a standard SDP solver (e.g., CVXPY with SCS).

(b) Generate $K = 3$ point sources at off-grid angles. Solve the SDP and extract the source angles from the dual variable.

(c) Compare with grid-based LASSO on grids of $N = 36, 180, 1800$ points. Plot position error vs. grid density.

(d) Vary the source separation from $3\times$ to $0.5\times$ the Rayleigh limit. At what separation does the SDP fail?

(e) Compare computation time: SDP vs. LASSO vs. SPARROW.

Show Hint

The SDP variable is a $(M+1) \times (M+1)$ PSD matrix with Toeplitz structure in the top-left $M \times M$ block.

Solution

Super-resolution limit

The SDP typically resolves sources down to $\sim 0.7$ Rayleigh widths at $\text{SNR} = 30$ dB. Below $0.5$ Rayleigh, the SDP merges the sources into a single peak.

ex15-full-pipeline

Challenge

Build an end-to-end sparse RF imaging pipeline:

(a) System: MIMO radar at 77 GHz, $N_t = 8$ , $N_r = 16$ , 4 GHz bandwidth, $N_f = 128$ . Scene: $64 \times 64$ at 5 m range.

(b) Scene: Urban scenario — 10 vehicles (extended, 3--5 pixels each), 20 pedestrians (point-like), 5 buildings (large extended).

(c) Compression: Randomly subsample 30% of measurements.

(d) Pipeline: (i) Matched filter (fast preview). (ii) FISTA ( $\ell_1$ ) for sparse reconstruction. (iii) ADMM ( $\ell_1$ + TV) for final image. (iv) SPARROW refinement for the strongest 10 scatterers.

(e) Evaluation: NMSE, SSIM, target detection ( $P_d$ and $P_{fa}$ ), computation time per stage.

(f) Create a processing time vs. quality curve. What is the optimal stopping point at 100 ms? 500 ms? 5 s?

Show Hint

The pipeline should progressively refine: MF -> FISTA -> ADMM -> SPARROW.

Use Kronecker structure for fast computation throughout.

Solution

Expected pipeline performance

MF: 10 ms, NMSE $\approx -6$ dB. FISTA (30 iter): 150 ms, NMSE $\approx -18$ dB. ADMM (50 iter): 500 ms, NMSE $\approx -22$ dB. SPARROW: +50 ms, position RMSE $< 0.1$ pixel for strong targets.

Time budget allocation

At 100 ms budget: use FISTA with 20 iterations. At 500 ms: ADMM with $\ell_1$ + TV. At 5 s: full pipeline with SPARROW refinement.

Exercises

ex01-lasso-implementation

FISTA convergence

Debiasing effect

ex02-lambda-selection

Expected outcome

ex03-admm-lasso

Adaptive $\rho$ advantage

ex04-2d-imaging

Key result

ex05-tv-imaging

Expected ranking

ex06-group-lasso

Expected improvement

ex07-omp-vs-lasso

Crossover point

ex08-admm-composite

Optimal ratio

ex09-gridless-refinement

Refinement benefit

ex10-mmv-radar

Snapshot gain

ex11-pesavento

Expected behavior

ex12-tgv

Staircase effect

ex13-algorithm-comparison

Expected Pareto front

ex14-atomic-norm

Super-resolution limit

ex15-full-pipeline

Expected pipeline performance

Time budget allocation