Ferkans — Interactive Telecom Tutor

DOA Estimation Is a Sparse-Inverse Problem

A uniform linear array with $N_a$ antennas observes signals arriving from $K$ directions $\theta_1, \ldots, \theta_K$ . The classical subspace methods — MUSIC, ESPRIT — rely on the eigenstructure of the sample covariance and need $K < N_a$ . They also need many snapshots to estimate the covariance reliably, and they break down at low SNR, with coherent sources, or when sources move between snapshots. The point is that the directions $\theta_k$ are sparse on the angular domain: we have $K$ active angles in a potentially dense grid. Posing DOA as a CS problem lets us work with single snapshots, handle coherent sources, and exploit structure across frequencies.

Definition:
Sparse DOA Model on an Angular Grid

Let $\mathbf{a}(\theta) \in \mathbb{C}^{N_a}$ denote the ULA steering vector at angle $\theta$ , with $[\mathbf{a}(\theta)]_n = e^{j\pi n \sin\theta}$ (half-wavelength spacing). Fix a grid $\{\theta_g\}_{g=1}^G$ on $[-90^\circ, 90^\circ]$ and stack the steering vectors into $\mathbf{A} = [\mathbf{a}(\theta_1) \cdots \mathbf{a}(\theta_G)] \in \mathbb{C}^{N_a \times G}$ . A $T$ -snapshot observation from $K$ sources obeys $\mathbf{Y} = \mathbf{A}\,\mathbf{X} + \mathbf{W},\qquad \mathbf{Y} \in \mathbb{C}^{N_a \times T},$ where the rows of $\mathbf{X} \in \mathbb{C}^{G \times T}$ are row-sparse with exactly $K$ nonzero rows — one per source. The sensing matrix here is $\mathbf{A}$ (the steering dictionary), and $G \gg K$ .

With $T = 1$ the problem reduces to standard single-measurement CS. With $T > 1$ we exploit the fact that all snapshots see the same sources — a joint-sparsity (MMV) problem.

Theorem: $\ell_{2,1}$ Recovery for Joint-Sparse DOA

Consider the MMV model $\mathbf{Y} = \mathbf{A}\mathbf{X} + \mathbf{W}$ with $K$ nonzero rows. The $\ell_{2,1}$ regularization $\hat{\mathbf{X}} = \arg\min_{\mathbf{X}}\ \tfrac{1}{2}\|\mathbf{Y} - \mathbf{A}\mathbf{X}\|_F^2 + \lambda \sum_{g=1}^G \|\mathbf{x}_g\|_2$ enjoys the same RIP-based recovery guarantees as single-measurement LASSO, with the number of required snapshots replaced by effective measurements $N_a\cdot T$ in the concentration analysis. In particular, if $\mathbf{A}$ has RIP of order $2K$ and $\delta_{2K} < \sqrt{2}-1$ , then $\|\hat{\mathbf{X}} - \mathbf{X}\|_F \leq C_0\, \|\mathbf{W}\|_F / \sqrt{N_a}.$

The key observation is that averaging across snapshots reduces noise by $\sqrt{T}$ , so joint sparsity trades snapshots for angular resolution. A single snapshot of MUSIC fails; a single snapshot of $\ell_{2,1}$ still recovers the sources.

Proof

Joint-sparsity RIP

Eldar & Mishali (2009) extend the standard RIP proof to MMV: the restricted isometry of the block operator $\mathbf{X} \mapsto \mathbf{A}\mathbf{X}$ coincides with the single-vector RIP because the block norm is a Euclidean tensor norm.

Error decomposition

Optimality of $\hat{\mathbf{X}}$ and KKT conditions of the $\ell_{2,1}$ problem yield $\|\hat{\mathbf{X}} - \mathbf{X}\|_F \leq 2\|\mathbf{W}\|_F/(1-\delta_{2K})$ on the true support, which combines with the RIP bound on the off-support part.

Plug in noise

For $\mathbf{W}$ with i.i.d.\ $\mathcal{CN}(0,\sigma^2)$ entries, $\mathbb{E}\|\mathbf{W}\|_F^2 = N_a T \sigma^2$ . Normalising by $\sqrt{N_a}$ and tracking constants yields the stated bound. $\blacksquare$

Definition:
Atomic Norm for Gridless DOA

Define the set of atoms $\mathcal{A} = \{\mathbf{a}(\theta)\,e^{j\varphi} : \theta \in [-90^\circ, 90^\circ],\ \varphi \in [0, 2\pi)\}.$ The atomic norm of a vector $\mathbf{u} \in \mathbb{C}^{N_a}$ is $\|\mathbf{u}\|_\mathcal{A} = \inf\Big\{ \sum_k |c_k| : \mathbf{u} = \sum_k c_k \mathbf{a}(\theta_k) e^{j\varphi_k}\Big\}.$ A gridless DOA estimator solves $\min_{\mathbf{u}}\ \tfrac{1}{2}\|\mathbf{y} - \mathbf{u}\|_2^2 + \lambda\, \|\mathbf{u}\|_\mathcal{A}.$

Unlike on-grid CS, atomic-norm minimization places sources at arbitrary continuous angles, eliminating basis mismatch and achieving "super-resolution" beyond the Rayleigh limit when sources are well separated.

Theorem: SDP Characterization of Atomic Norm

For $\mathbf{u} \in \mathbb{C}^{N_a}$ and Vandermonde atoms, the atomic norm equals the optimum of $\|\mathbf{u}\|_\mathcal{A} = \inf_{\mathbf{T},\,t}\ \tfrac{1}{2}\!\left(t + \tfrac{1}{N_a}\mathrm{tr}(\mathbf{T})\right) \quad \text{s.t.} \quad \begin{pmatrix}\mathbf{T} & \mathbf{u} \\ \mathbf{u}^H & t\end{pmatrix} \succeq 0,\quad \mathbf{T}\text{ Hermitian Toeplitz}.$

A seemingly infinite-dimensional optimization over $\theta$ becomes a finite semidefinite program. The Vandermonde decomposition lemma (Carathéodory) recovers the angles from the optimal $\mathbf{T}$ .

Proof

Primal-dual pairing

The atomic norm's dual is $\|\mathbf{q}\|_\mathcal{A}^* = \sup_{\theta,\varphi} |\langle \mathbf{q}, \mathbf{a}(\theta)e^{j\varphi}\rangle| = \sup_\theta |\mathbf{q}^H \mathbf{a}(\theta)|$ , i.e.\ the maximum modulus of a trigonometric polynomial.

Bounded-real lemma

Trigonometric polynomials bounded by 1 are characterised by a PSD Toeplitz-Gram representation (Fejér-Riesz / Schur). This yields the LMI constraint.

Lagrangian

Weak and strong duality hold (Slater's condition is satisfied), so the primal SDP matches the atomic-norm value. The angles are read off as generalised eigenvalues of the matrix pencil associated with $\mathbf{T}$ . $\blacksquare$

DOA Spectrum: Sparse Matched Filter vs MUSIC

Sparse matched-filter recovery and MUSIC both exhibit sharp peaks at true angles. Vary SNR and snapshots: MUSIC degrades when $T$ is small or sources coherent; sparse recovery is more robust.

Parameters

Array size

N_a

16

Snapshots

T

50

SNR (dB)15

DOA 1 (°)-25

DOA 2 (°)10

DOA 3 (°)35

Example: Single-Snapshot DOA Recovery

A ULA with $N_a = 16$ antennas observes two coherent sources at $-20^\circ$ and $+15^\circ$ in a single snapshot ( $T=1$ ). Explain why MUSIC fails but sparse recovery succeeds.

Solution

MUSIC failure

MUSIC estimates the source subspace from the sample covariance $\widehat{\mathbf{R}} = \mathbf{y}\mathbf{y}^H$ . With $T = 1$ this matrix has rank 1: we cannot separate two sources from a rank-1 estimate, and MUSIC returns a single peak at the dominant superposition direction. Coherence makes this worse: even with many snapshots, coherent sources produce a rank-deficient covariance.

Sparse recovery success

The $\ell_1$ estimator $\hat{\mathbf{x}} = \arg\min \|\mathbf{y} - \mathbf{A}\mathbf{x}\|_2^2 + \lambda\|\mathbf{x}\|_1$ treats the snapshot as $N_a = 16$ measurements of a 2-sparse $\mathbf{x}$ . As long as $16 \gtrsim 2 \log(G/2)$ (satisfied for $G \leq 1000$ ) and the grid is fine enough, recovery succeeds with a single snapshot. Coherence is irrelevant because we never form a covariance matrix.

Tradeoffs

Sparse recovery is computationally heavier per snapshot but excels in snapshot-limited, coherent-source scenarios (passive radar, pulse-compression DOA).

⚠️Engineering Note

Joint Communication and Sensing (JCAS)

Integrated sensing and communication (ISAC / JCAS) in 6G uses the same waveform to transmit data and estimate target angles/ranges. The sensing channel is typically sparse — few targets in a large angular-range cell. Atomic-norm DOA estimation is the algorithm of choice for off-grid targets because grid mismatch otherwise limits angular accuracy. In 3GPP RAN1 ISAC discussions, gridless estimators are proposed as a benchmark for target localisation performance.

📋 Ref: 3GPP TR 22.837 (Sensing Use Cases), TR 38.837

Common Mistake: Basis Mismatch Dominates at High SNR

Mistake:

Refining the angular grid indefinitely to resolve off-grid sources.

Correction:

As the grid $G \to \infty$ , the columns of $\mathbf{A}$ become increasingly correlated and CS recovery becomes ill-conditioned — RIP deteriorates, and $\ell_1$ fails to be selective. Grid-mismatch error $\sim \Delta\theta^2$ (Malioutov et al.) eventually dominates the noise error. Use atomic-norm minimization or iterative grid refinement instead of blindly shrinking $\Delta\theta$ .

Historical Note: From MUSIC to Atomic Norm

1986-2013

Schmidt introduced MUSIC in 1986; Roy and Kailath introduced ESPRIT in 1989. These eigenstructure methods dominated array processing for two decades. Malioutov, Cetin, and Willsky (2005) were the first to formulate DOA as a sparse recovery problem, opening the CS-for-DOA research line. Tang, Bhaskar, Shah, and Recht (2013) gave the atomic-norm framework that made gridless super-resolution rigorous, building on the continuous-time super-resolution results of Candès and Fernandez-Granda.

Atomic norm

The gauge function of the convex hull of an atomic set $\mathcal{A}$ . Generalises $\ell_1$ (atoms = signed standard basis) and nuclear norm (atoms = rank-1 matrices) to arbitrary parametric dictionaries — crucially, continuous ones like $\{\mathbf{a}(\theta)\}$ .

Steering vector

The array response to a plane wave from angle $\theta$ . For a ULA with half-wavelength spacing, $[\mathbf{a}(\theta)]_n = e^{j\pi n \sin\theta}$ , a Vandermonde vector.

DOA Methods Compared

Property	MUSIC	$\ell_{2,1}$ -MMV CS	Atomic Norm (Gridless)
Single-snapshot	fails	works	works
Coherent sources	fails (subspace)	works	works
$K \geq N_a$ sources	fails	works if RIP holds	works
Off-grid bias	none (continuous)	$O(\Delta\theta^2)$	none
Complexity	$O(N_a^3)$ eig	$O(N_a G)$ /iter	SDP: $O(N_a^{6.5})$
SNR threshold	high	moderate	low (best)

Key Takeaway

DOA estimation is sparse recovery on an angular grid. $\ell_{2,1}$ joint-sparsity handles multiple snapshots and coherent sources; atomic-norm minimization removes the grid altogether at the cost of solving an SDP. Both outperform classical subspace methods in the snapshot-limited, coherent-source, or low-SNR regimes that dominate ISAC and integrated sensing workloads.

Why This Matters: mmWave Beam Training

At mmWave frequencies, narrow beams must be steered toward a handful of scattering clusters. Beam training is exactly sparse DOA estimation: the UE sweeps a few directions and the BS recovers the cluster angles via on-grid or atomic-norm CS. This is why 5G NR beam-management procedures (SSB, CSI-RS) align naturally with CS dictionaries.

Quick Check

Why can $\ell_1$ -based DOA estimation resolve $K$ coherent sources from a single snapshot while MUSIC cannot?

MUSIC needs orthogonal sources

MUSIC estimates the covariance matrix, which has rank at most equal to the number of snapshots; CS uses the snapshot directly.

CS uses more antennas

CS assumes known DOAs