Ferkans — Interactive Telecom Tutor

Total Variation — Preserving Edges in Imaging

Total variation (TV) regularization promotes piecewise-constant images — ideal for scenes with extended targets that have sharp boundaries. TV penalizes the $\ell_1$ norm of the image gradient, encouraging sparsity in the gradient domain rather than the image domain. This section develops TV reconstruction for RF imaging, building on the optimization framework of RFI Ch 04 and Telecom Ch 03.

Definition:
Total Variation for 2D Images

For a 2D image $\mathbf{c} \in \mathbb{R}^{N_x \times N_y}$ (vectorized as $\mathbf{c} \in \mathbb{R}^N$ ), the isotropic TV semi-norm is:

$\|\mathbf{c}\|_{\text{TV}} = \sum_{i,j} \sqrt{(c_{i+1,j} - c_{i,j})^2 + (c_{i,j+1} - c_{i,j})^2},$

and the anisotropic TV is:

$\|\mathbf{c}\|_{\text{ATV}} = \sum_{i,j} \left(|c_{i+1,j} - c_{i,j}| + |c_{i,j+1} - c_{i,j}|\right).$

In operator notation: $\|\mathbf{c}\|_{\text{TV}} = \|\nabla_D \mathbf{c}\|_{2,1}$ and $\|\mathbf{c}\|_{\text{ATV}} = \|\nabla_D \mathbf{c}\|_1$ , where $\nabla_D$ is the discrete gradient operator.

TV-regularized RF imaging:

$\hat{\mathbf{c}}_{\text{TV}} = \arg\min_{\mathbf{c}} \frac{1}{2}\|\mathbf{y} - \mathbf{A}\mathbf{c}\|_2^2 + \lambda\|\mathbf{c}\|_{\text{TV}}.$

Theorem: ADMM for TV-Regularized Imaging

The TV-regularized imaging problem can be solved efficiently by ADMM with the auxiliary variable $\mathbf{z} = \nabla_D\mathbf{c}$ :

$\mathbf{c}^{(t+1)} = (\mathbf{A}^{H}\mathbf{A} + \rho\nabla_D^H\nabla_D)^{-1} (\mathbf{A}^{H}\mathbf{y} + \rho\nabla_D^H (\mathbf{z}^{(t)} - \mathbf{u}^{(t)})),$

$\mathbf{z}^{(t+1)} = \text{prox}_{\lambda/\rho\,\|\cdot\|_{2,1}} (\nabla_D\mathbf{c}^{(t+1)} + \mathbf{u}^{(t)}),$

$\mathbf{u}^{(t+1)} = \mathbf{u}^{(t)} + \nabla_D\mathbf{c}^{(t+1)} - \mathbf{z}^{(t+1)}.$

ADMM decouples the data fidelity (involving $\mathbf{A}$ ) from the TV penalty (involving $\nabla_D$ ). Each subproblem is simpler: the $\mathbf{c}$ -update is a linear system, the $\mathbf{z}$ -update is block soft-thresholding.

Proof

ADMM splitting

Introduce $\mathbf{z} = \nabla_D\mathbf{c}$ :

$\min_{\mathbf{c}, \mathbf{z}} \; \frac{1}{2}\|\mathbf{y} - \mathbf{A}\mathbf{c}\|_2^2 + \lambda\|\mathbf{z}\|_{2,1} \quad \text{s.t.} \quad \mathbf{z} = \nabla_D\mathbf{c}.$

Efficient $\ntn{refl}$-update

The matrix $\mathbf{A}^{H}\mathbf{A} + \rho\nabla_D^H\nabla_D$ can be inverted via FFT when $\mathbf{A}^{H}\mathbf{A}$ is circulant (periodic boundary conditions):

$\mathbf{c}^{(t+1)} = \mathcal{F}^{-1}\left\{ \frac{\mathcal{F}\{\mathbf{b}\}} {\mathcal{F}\{\mathbf{A}^{H}\mathbf{A}\} + \rho\mathcal{F}\{\nabla_D^H\nabla_D\}}\right\},$

where division is element-wise. Cost: $O(N\log N)$ .

General $\ntn{sens}$ case

For non-circulant $\mathbf{A}$ (general sensing matrix), use conjugate gradient (CG) for the $\mathbf{c}$ -update — typically converges in $\sim$ 10 CG iterations because $\mathbf{A}^{H}\mathbf{A} + \rho\nabla_D^H\nabla_D$ is well-conditioned for moderate $\rho$ .

Definition:
TV for Complex-Valued RF Images

RF images are complex-valued (magnitude + phase). For complex TV, we have two options:

Option 1: Magnitude TV. Apply TV to $|\mathbf{c}|$ — ignores phase structure.

Option 2: Complex TV (recommended).

$\|\mathbf{c}\|_{\text{CTV}} = \sum_{i,j} \sqrt{|c_{i+1,j} - c_{i,j}|^2 + |c_{i,j+1} - c_{i,j}|^2},$

where $|\cdot|$ denotes the complex modulus. This penalizes variations in both magnitude and phase simultaneously.

For most RF imaging applications, complex TV provides the best results because magnitude and phase transitions co-occur at scatterer boundaries.

Definition:
Total Generalized Variation (TGV)

Standard TV promotes piecewise-constant images but produces staircase artifacts on smooth gradients. The Total Generalized Variation (TGV) of order 2 addresses this:

$\text{TGV}^2_{\alpha_0, \alpha_1}(\mathbf{c}) = \min_{\mathbf{p}} \; \alpha_1 \|\nabla_D \mathbf{c} - \mathbf{p}\|_1 + \alpha_0 \|\mathcal{E}(\mathbf{p})\|_1,$

where $\mathbf{p}$ is an auxiliary vector field and $\mathcal{E}(\mathbf{p})$ is the symmetrized gradient.

TGV promotes piecewise-smooth images:

Constant regions: $\nabla_D \mathbf{c} \approx \mathbf{p} \approx 0$ .
Linear gradients: $\nabla_D \mathbf{c} \approx \mathbf{p}$ (constant), $\mathcal{E}(\mathbf{p}) \approx 0$ .
Edges: sharp transitions penalized by $\alpha_1$ .

RF imaging use case: Scenes with smooth reflectivity variations (e.g., dielectric objects with gradual permittivity changes) in addition to sharp edges.

ADMM for TV-Regularized RF Imaging

Complexity:

O(T_{\max}(N\log N + MN_{\text{CG}}))

where

N_{\text{CG}} \approx 10

is the number of CG iterations for the linear system.

Input:

\mathbf{A}

,

\mathbf{y}

,

\lambda

,

\rho

,

T_{\max}

Initialize:

\mathbf{c}^{(0)} = \mathbf{A}^{H}\mathbf{y}

,

\mathbf{z}^{(0)} = \mathbf{0}

,

\mathbf{u}^{(0)} = \mathbf{0}

for

t = 0, 1, \ldots, T_{\max}-1

:

// Scene update (CG or FFT solve)

\mathbf{b} \gets \mathbf{A}^{H}\mathbf{y} + \rho\nabla_D^H(\mathbf{z}^{(t)} - \mathbf{u}^{(t)})

\mathbf{c}^{(t+1)} \gets (\mathbf{A}^{H}\mathbf{A} + \rho\nabla_D^H\nabla_D)^{-1}\mathbf{b}

// Gradient update (block soft-thresholding)

\mathbf{v} \gets \nabla_D\mathbf{c}^{(t+1)} + \mathbf{u}^{(t)}

for each pixel

(i,j)

:

\mathbf{z}_{i,j}^{(t+1)} \gets \text{prox}_{\lambda/\rho\,\|\cdot\|_2}(\mathbf{v}_{i,j})

// Dual update

\mathbf{u}^{(t+1)} \gets \mathbf{u}^{(t)} + \nabla_D\mathbf{c}^{(t+1)} - \mathbf{z}^{(t+1)}

// Adaptive

\rho

(optional)

if primal residual

> 10 \times

dual residual:

\rho \gets 2\rho

if dual residual

> 10 \times

primal residual:

\rho \gets \rho/2

Output:

\hat{\mathbf{c}}_{\text{TV}} = \mathbf{c}^{(T_{\max})}

When $\mathbf{A}^{H}\mathbf{A}$ admits FFT diagonalization (e.g., circulant or Kronecker with DFT factors), the $\mathbf{c}$ -update reduces to $O(N\log N)$ , making each ADMM iteration very fast.

TV vs. $\ell_1$ Regularization for Imaging

Compares $\ell_1$ , TV, and $\ell_1$ +TV regularization on a scene with both point scatterers and extended targets.

$\ell_1$ : Recovers point scatterers well but breaks extended targets into isolated points.
TV: Preserves edges of extended targets but may smooth point scatterers.
$\ell_1$ + TV: Best of both worlds.

Adjust $\lambda$ to balance data fidelity and regularization.

Parameters

Regularizer

\lambda

0.05

Example: TV Reconstruction for Through-Wall Imaging

Setup: Through-wall radar imaging of a room interior. Radar: ULA with $M = 512$ measurements. Scene: $64 \times 64$ grid. Targets: 2 humans (extended, piecewise-constant) and 3 furniture items (rectangular shapes).

Results ( $\text{SNR} = 15$ dB):

Method	NMSE (dB)	SSIM	Edge preservation
Matched filter	$-4.1$	0.31	Poor
$\ell_1$ (FISTA)	$-12.3$	0.72	Moderate
TV (ADMM)	$-17.8$	0.88	Excellent
$\ell_1$ + TV (ADMM)	$-18.5$	0.91	Excellent

TV dramatically outperforms $\ell_1$ for scenes with extended targets.

Solution

Why TV wins for extended targets

Extended targets have many nonzero pixels but few edges. $\ell_1$ penalizes every nonzero pixel equally, so it struggles. TV penalizes only the edges, allowing constant-amplitude interiors for free.

Combined $\ell_1$ + TV

The combination $\lambda_{1}\|\mathbf{c}\|_1 + \lambda_{2}\|\mathbf{c}\|_{\text{TV}}$ handles mixed scenes: $\ell_1$ catches point scatterers, TV preserves extended target edges.

TV Variants for RF Imaging

Variant	Penalizes	Best for	Artifacts
Anisotropic TV	$\\|\nabla_D\mathbf{c}\\|_1$	Axis-aligned edges	Blocky corners on diagonal edges
Isotropic TV	$\\|\nabla_D\mathbf{c}\\|_{2,1}$	Edges at any angle	Staircase on smooth gradients
TGV (order 2)	$\alpha_1\\|\nabla-\mathbf{p}\\|+\alpha_0\\|\mathcal{E}(\mathbf{p})\\|$	Smooth + sharp regions	More parameters to tune
$\ell_1$ + TV	$\lambda_{1}\\|\mathbf{c}\\|_1 + \lambda_{2}\\|\mathbf{c}\\|_{\text{TV}}$	Mixed scenes	Two parameters to tune

Common Mistake: TV Staircase Artifacts

Mistake:

Applying isotropic TV to scenes with smooth reflectivity gradients (e.g., dielectric objects with varying permittivity). TV promotes piecewise-constant reconstructions, so smooth gradients are approximated by staircase-like steps.

Correction:

Use TGV (Total Generalized Variation) for scenes with both sharp edges and smooth regions. TGV allows linear and higher-order polynomial variations within regions while preserving edge sharpness.

Quick Check

A scene consists of a single rectangular target with uniform reflectivity. Which regularizer will produce the best reconstruction?

TV (isotropic) — the scene is piecewise-constant with sharp edges.

$\ell_1$ — the scene has many nonzero pixels.

TGV — the scene has smooth variations.

Correction:

TV (isotropic) — the scene is piecewise-constant with sharp edges.

A uniform rectangular target has zero gradient everywhere except at the edges. TV penalizes only the edges, so the penalty is minimal for the true scene.

Historical Note: Total Variation from Image Denoising to RF Imaging

1992--2011

Total variation regularization was introduced by Rudin, Osher, and Fatemi (1992) for image denoising — the ROF model. The key insight was that natural images often have sparse gradients (piecewise-constant regions separated by edges). Chambolle (2004) provided efficient algorithms, and the ADMM framework (Boyd et al., 2011) made TV tractable for large-scale inverse problems. Cetin and Karl (2001) pioneered the application of TV to SAR imaging, demonstrating its superiority over $\ell_1$ for extended targets.

,

Total Variation (TV)

Semi-norm measuring the $\ell_1$ norm of the image gradient. Promotes piecewise-constant images by penalizing edge magnitude while leaving constant regions free.

Total Generalized Variation (TGV)

Higher-order extension of TV that promotes piecewise-smooth (not just piecewise-constant) images by penalizing the second derivative of the image.

Key Takeaway

TV regularization is the natural choice for RF scenes with extended targets and sharp boundaries. ADMM splits the problem into an FFT-solvable linear system and block soft-thresholding. For mixed scenes (point + extended targets), $\ell_1$ + TV via ADMM handles both structures. Use TGV when smooth gradients are present to avoid staircase artifacts. Complex TV penalizes both magnitude and phase variations and is recommended for coherent imaging.

Total Variation Reconstruction