Ferkans — Interactive Telecom Tutor

Greedy Algorithms — Fast Sparse Recovery for RF Imaging

Greedy algorithms build the sparse solution iteratively, selecting one or a few atoms per iteration. They are typically much faster than convex relaxation methods (LASSO/FISTA/ADMM) but provide weaker theoretical guarantees. For RF imaging, greedy methods are attractive for real-time applications where the computational budget is tight.

Definition:
Orthogonal Matching Pursuit (OMP) for RF Imaging

OMP builds the support set one element at a time:

Initialize: $\mathbf{r}^{(0)} = \mathbf{y}$ , $S^{(0)} = \emptyset$ .
Select: $j^* = \arg\max_j |\mathbf{A}_{j}^{H}\mathbf{r}^{(t)}|$ — the pixel most correlated with the residual.
Update support: $S^{(t+1)} = S^{(t)} \cup \{j^*\}$ .
Project: $\hat{\mathbf{c}}^{(t+1)} = \mathbf{A}_{S^{(t+1)}}^\dagger \mathbf{y}$ — least squares on the current support.
Update residual: $\mathbf{r}^{(t+1)} = \mathbf{y} - \mathbf{A}_{S^{(t+1)}}\hat{\mathbf{c}}^{(t+1)}$ .
Repeat until $\|\mathbf{r}\|_2 \leq \epsilon$ or $|S| = s_{\max}$ .

Cost per iteration: $O(MN)$ for the correlation step, $O(M|S|)$ for the least-squares update. Total for $s$ iterations: $O(sMN + s^2 M)$ .

Definition:
CoSaMP (Compressive Sampling Matching Pursuit)

CoSaMP (Needell and Tropp, 2009) improves on OMP by selecting multiple atoms per iteration and pruning:

Initialize: $\hat{\mathbf{c}}^{(0)} = \mathbf{0}$ , $S^{(0)} = \emptyset$ .
Identify: Find the $2s$ largest entries of $|\mathbf{A}^{H}\mathbf{r}^{(t)}|$ . Let $\Omega$ be their indices.
Merge: $T = S^{(t)} \cup \Omega$ (at most $3s$ indices).
Estimate: $\hat{\mathbf{b}} = \mathbf{A}_{T}^\dagger\mathbf{y}$ — least squares on the merged support.
Prune: $S^{(t+1)} =$ indices of the $s$ largest entries of $\hat{\mathbf{b}}$ .
Update: $\hat{\mathbf{c}}^{(t+1)} = \hat{\mathbf{b}}_{S^{(t+1)}}$ .
Residual: $\mathbf{r}^{(t+1)} = \mathbf{y} - \mathbf{A}_{S^{(t+1)}}\hat{\mathbf{c}}^{(t+1)}$ .

Key advantage over OMP: CoSaMP can correct mistakes — atoms added in early iterations can be removed by pruning. OMP commits to each selection permanently.

Definition:
Iterative Hard Thresholding (IHT)

IHT (Blumensath and Davies, 2009) applies hard thresholding after a gradient step:

$\mathbf{c}^{(t+1)} = \mathcal{H}_s\!\left( \mathbf{c}^{(t)} + \mu\mathbf{A}^{H} (\mathbf{y} - \mathbf{A}\mathbf{c}^{(t)})\right),$

where $\mathcal{H}_s$ keeps the $s$ largest entries and zeros the rest (hard thresholding), and $\mu \leq 1/L_f$ .

IHT vs. ISTA:

ISTA uses soft thresholding ( $\ell_1$ penalty, convex).
IHT uses hard thresholding ( $\ell_0$ constraint, non-convex).
IHT has better amplitude accuracy (no shrinkage bias) but requires knowing $s$ .
IHT converges under $\delta_{3s} < 1/\sqrt{3}$ .

For RF imaging, IHT is a useful middle ground between OMP (very fast, committed selections) and FISTA (slower, convex).

OMP for RF Image Reconstruction

Complexity:

O(sMN + s^2 M)

total for

s

scatterers.

Input:

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

,

\mathbf{y} \in \mathbb{C}^M

, sparsity

s

or threshold

\epsilon

Initialize:

\mathbf{r} \gets \mathbf{y}

,

S \gets \emptyset

,

\hat{\mathbf{c}} \gets \mathbf{0}

for

t = 1, 2, \ldots, s

:

// Correlation (matched filter of residual)

\mathbf{h} \gets \mathbf{A}^{H} \mathbf{r}

j^* \gets \arg\max_j |h_j|

// Update support

S \gets S \cup \{j^*\}

// Least-squares projection

\hat{\mathbf{c}}_S \gets \mathbf{A}_{S}^\dagger \mathbf{y}

// Update residual

\mathbf{r} \gets \mathbf{y} - \mathbf{A}_{S} \hat{\mathbf{c}}_S

// Early stopping

if

\|\mathbf{r}\|_2 \leq \epsilon

: break

Output:

\hat{\mathbf{c}}

, support

S

The correlation step $\mathbf{A}^{H}\mathbf{r}$ is identical to computing the matched filter image of the residual — the same operation as one ISTA gradient step.

OMP vs. LASSO: Speed-Accuracy Tradeoff

Compares OMP, CoSaMP, and LASSO (FISTA) for RF image reconstruction.

Left: Reconstructed images for each algorithm. Right: NMSE vs. computation time, showing the Pareto frontier.

OMP: Fastest for small $s$ but degrades rapidly as sparsity increases.
CoSaMP: More robust than OMP with self-correction.
LASSO/FISTA: Slowest per iteration but most robust; best for large $s$ or compressible scenes.

Adjust sparsity to see the crossover point where convex methods outperform greedy ones.

Parameters

Algorithm

Scene sparsity

s

10

SNR (dB)20

Theorem: OMP Recovery Guarantee for RF Imaging

OMP exactly recovers an $s$ -sparse signal $\mathbf{c}$ from $\mathbf{y} = \mathbf{A}\mathbf{c}$ in $s$ iterations if the mutual coherence $\mu(\mathbf{A})$ satisfies:

$\mu(\mathbf{A}) < \frac{1}{2s - 1}.$

More precisely, exact recovery holds if the cumulative coherence function satisfies $\mu_1(s-1) + \mu_1(s) < 1$ (Tropp and Gilbert, 2007).

The condition ensures that each OMP step selects a correct atom: the correlation with the true atom exceeds the correlation with all incorrect atoms combined.

Proof

Exact recovery condition

At iteration $t$ , OMP selects $j^* = \arg\max_j |\mathbf{A}_{j}^{H}\mathbf{r}^{(t)}|$ . This selects a correct atom if the residual $\mathbf{r}^{(t)}$ has larger projection onto the remaining true atoms than any false atom.

Coherence bound

Using the Babel function $\mu_1(s) = \max_{|S|=s} \max_{j \notin S} \sum_{i \in S} |\langle \mathbf{A}_{i}, \mathbf{A}_{j} \rangle|$ , the condition $\mu_1(s-1) + \mu_1(s) < 1$ ensures the correct atom always dominates.

Noisy case

Under noise $\mathbf{w}$ with $\|\mathbf{w}\|_2 \leq \epsilon$ , OMP recovers the correct support provided the minimum nonzero amplitude exceeds $2\epsilon/(1 - \mu_1(2s-1))$ .

Example: OMP for Real-Time Radar Imaging

Setup: Automotive radar at 77 GHz. $N_t = 3$ , $N_r = 4$ , $N_f = 256$ ( $M = 3072$ ). Scene: $64 \times 64$ grid ( $N = 4096$ ). Budget: 50 ms per image (20 Hz update).

Method	Iterations	Time (ms)	NMSE (dB)
OMP ( $s = 15$ )	15	12	$-15.2$
CoSaMP ( $s = 15$ )	10	18	$-17.1$
FISTA ( $\lambda = 0.03$ )	30	45	$-19.8$
FISTA ( $\lambda = 0.03$ )	50	75	$-21.3$

OMP and CoSaMP meet the real-time requirement; FISTA needs early stopping to fit within the budget.

Solution

Practical approach

Use OMP for the initial real-time display, then refine with FISTA in a background thread. The user sees a quick preview that is progressively refined.

When greedy fails

For compressible scenes (many weak scatterers), OMP with a fixed $s$ misses the tail of the amplitude distribution. FISTA with the discrepancy principle adapts to the actual sparsity level.

Greedy vs. Convex Methods for RF Imaging

Criterion	Greedy (OMP/CoSaMP/IHT)	Convex (LASSO/FISTA/ADMM)
Speed	Very fast for small $s$	Slower but consistent
Robustness	Sensitive to $s$ estimate	Robust ( $\lambda$ controls sparsity)
Compressible signals	Poor	Good ( $\sigma_s$ bound)
Structured sparsity	Limited	TV, group LASSO, etc.
Amplitude accuracy	Exact (least squares)	Biased by $\lambda$ (debias needed)
Parameter requirement	Need $s$ or stopping criterion	Need $\lambda$
RIP guarantee	$\delta_{3s} < 1/\sqrt{3}$ (IHT)	$\delta_{2s} < \sqrt{2}-1$ (LASSO)

,

Common Mistake: Overestimating Sparsity in OMP

Mistake:

Running OMP with $s_{\max}$ much larger than the true sparsity. After all true atoms are selected, OMP begins selecting noise atoms, and the least-squares projection contaminates the amplitude estimates of the true atoms.

Correction:

Use the residual norm as a stopping criterion: stop when $\|\mathbf{r}^{(t)}\|_2 \leq \sqrt{M}\sigma$ . This avoids selecting noise atoms without requiring prior knowledge of $s$ .

Quick Check

For a radar imaging scene with $s = 5$ well-separated point scatterers at high $\text{SNR}$ , which algorithm is the best choice for real-time reconstruction?

OMP — the small $s$ and high SNR make it ideal, and it is the fastest option.

FISTA — it has stronger theoretical guarantees.

ADMM with TV — it produces the best image quality.

Correction:

OMP — the small

s

and high SNR make it ideal, and it is the fastest option.

With small $s$ and high SNR, OMP selects the correct atoms with high probability and completes in $O(5MN)$ operations — much faster than FISTA or ADMM.

⚠️Engineering Note

Practical Guidelines for Algorithm Selection

Decision tree for RF imaging algorithm selection:

Is $s$ small and known? $\to$ Use OMP or CoSaMP.
Is the scene compressible (power-law decay)? $\to$ Use FISTA.
Does the scene have extended targets? $\to$ Use ADMM with TV.
Is real-time required? $\to$ Use OMP, then refine with FISTA.
Is the scene a mix of point and extended? $\to$ Use ADMM with $\ell_1$ + TV.
Are multiple snapshots available? $\to$ Use MMV (§Group Sparsity and Joint Recovery (MMV)).

OMP (Orthogonal Matching Pursuit)

Greedy algorithm that builds the sparse support one atom at a time by selecting the atom most correlated with the current residual, then projecting onto the expanded support.

Related: CoSaMP

CoSaMP

Greedy algorithm that selects $2s$ candidates per iteration and prunes back to $s$ , allowing correction of earlier mistakes.

IHT (Iterative Hard Thresholding)

Gradient descent followed by hard thresholding to enforce exact $s$ -sparsity. No shrinkage bias (unlike ISTA) but requires knowledge of $s$ .

Key Takeaway

OMP selects one atom per iteration at $O(sMN)$ total cost — fastest for very sparse scenes. CoSaMP selects and prunes multiple atoms with self-correction capability. IHT applies hard thresholding for no shrinkage bias but needs $s$ . Greedy methods are fastest for small $s$ but degrade for compressible or structured scenes. Practical rule: greedy for real-time with small $s$ ; convex (FISTA/ADMM) for high-quality reconstruction with unknown or large $s$ .

Greedy Algorithms for Imaging