Ferkans — Interactive Telecom Tutor

Super-Resolution via Gridless Methods

All methods in the previous sections discretize the scene onto a pixel grid. When scatterers are not aligned with the grid, basis mismatch degrades recovery. Gridless methods recover scatterer positions and amplitudes directly in the continuous domain, avoiding the grid entirely. This section introduces atomic norm minimization, the SPARROW framework, and the connection to subspace methods like MUSIC.

Definition:
The Basis Mismatch Problem

Consider $K$ point scatterers at positions $\{\mathbf{p}_{k}\}_{k=1}^K$ , not necessarily on the grid $\{\mathbf{p}_{n}\}_{n=1}^N$ . The grid-based model approximates:

$y_m \approx \sum_{n=1}^{N} c_n\, A_{mn},$

but the true model is:

$y_m = \sum_{k=1}^{K} \alpha_k\, a_m(\mathbf{p}_{k}) + w_m.$

The mismatch error is:

$\delta = \|\mathbf{A}\mathbf{c}_{\text{grid}} - \mathbf{A}_{\text{true}}\boldsymbol{\alpha}\|_2,$

which is nonzero even in the noiseless case.

Consequences (Chi et al., 2011):

The recovery error is lower-bounded by $\delta / \sigma_{\min}(\mathbf{A})$ .
Refining the grid (smaller $\Delta$ ) reduces $\delta$ but increases $N$ and the coherence of $\mathbf{A}$ .
A dense grid can make $\mathbf{A}$ ill-conditioned, defeating the purpose of compressed sensing.

Definition:
Atomic Norm Minimization

The atomic norm approach (Chandrasekaran et al., 2012; Tang et al., 2013) lifts the problem to a continuous domain.

For a signal that is a superposition of atoms $\mathbf{a}(\mathbf{p})$ at continuous positions $\mathbf{p}$ :

$\|\mathbf{x}\|_{\mathcal{A}} := \inf\left\{ \sum_k |\alpha_k| : \mathbf{x} = \sum_k \alpha_k \mathbf{a}(\mathbf{p}_{k}),\; \mathbf{p}_{k} \in D\right\}.$

Atomic norm minimization:

$\hat{\mathbf{x}} = \arg\min_{\mathbf{x}} \|\mathbf{x}\|_{\mathcal{A}} \quad \text{s.t.} \quad \|\mathbf{y} - \mathbf{x}\|_2 \leq \epsilon.$

For single-dimensional problems (1D DOA, 1D range), this can be reformulated as a semidefinite program (SDP) via the Vandermonde decomposition theorem.

Theorem: SDP Reformulation of Atomic Norm Minimization

For a uniform linear array (ULA) with atom $\mathbf{a}(\theta) = [1, e^{j\pi\sin\theta}, \ldots, e^{j(M-1)\pi\sin\theta}]^T$ , the atomic norm $\|\mathbf{x}\|_{\mathcal{A}}$ equals the optimal value of the SDP:

$\min_{t, \mathbf{u}} \; \frac{1}{2}(t + \text{tr}(\text{Toep}(\mathbf{u}))) \quad \text{s.t.} \quad \begin{bmatrix} \text{Toep}(\mathbf{u}) & \mathbf{x} \\ \mathbf{x}^H & t \end{bmatrix} \succeq 0,$

where $\text{Toep}(\mathbf{u})$ is the Hermitian Toeplitz matrix with first column $\mathbf{u}$ .

The Vandermonde decomposition theorem guarantees that any positive semidefinite Toeplitz matrix can be written as a sum of rank-1 outer products of steering vectors at arbitrary angles. This connection allows the continuous atomic norm to be computed exactly via finite-dimensional semidefinite programming.

Proof

Vandermonde decomposition

A PSD Hermitian Toeplitz matrix $\mathbf{T} \in \mathbb{C}^{M \times M}$ admits the decomposition $\mathbf{T} = \sum_{k=1}^K p_k \mathbf{a}(\theta_k)\mathbf{a}(\theta_k)^H$ with $p_k \geq 0$ and distinct $\theta_k \in [-\pi/2, \pi/2)$ .

SDP equivalence

By the Schur complement, the matrix inequality $\begin{bmatrix} \mathbf{T} & \mathbf{x} \\ \mathbf{x}^H & t \end{bmatrix} \succeq 0$ holds if and only if $\mathbf{x} = \sum_k \alpha_k \mathbf{a}(\theta_k)$ with $\sum_k |\alpha_k|^2/p_k \leq t$ . Minimizing $\frac{1}{2}(t + \text{tr}(\mathbf{T}))$ under this constraint yields $\sum_k |\alpha_k|$ .

Recovering scatterer locations

After solving the SDP, the scatterer locations $\{\theta_k\}$ are recovered by finding the roots of the polynomial whose coefficients are the first column of $\text{Toep}(\mathbf{u}^*)$ .

Definition:
SPARROW — Practical Gridless Recovery

SPARROW (SPARse Recovery Over Weighted atoms) provides a practical gridless workflow for RF imaging:

Coarse-grid initialization: Solve the standard LASSO on a grid to identify approximate scatterer locations.
Position refinement: For each detected scatterer at grid point $n_k$ , parameterize $\mathbf{p}_{k} = \mathbf{p}_{n_k} + \delta_k$ and optimize $\delta_k$ by gradient descent on the data fidelity.
Amplitude update: Solve least squares for the refined positions: $\hat{\boldsymbol{\alpha}} = \mathbf{A}(\{\mathbf{p}_{k}\})^\dagger\mathbf{y}$ .
Pruning: Remove scatterers with $|\alpha_k| < \epsilon$ .

Advantage: SPARROW runs in $O(KMN + K \cdot \text{GD iterations})$ , much faster than the full SDP for large $M$ .

Gridless Super-Resolution via Atomic Norm

Demonstrates off-grid scatterer recovery using atomic norm minimization (SDP) vs. grid-based LASSO.

Left: True scatterer locations (off-grid) and grid-based LASSO reconstruction showing basis mismatch artifacts (split peaks, amplitude errors).

Right: Atomic norm recovery showing exact position recovery without grid artifacts.

Increase the number of scatterers or decrease the separation to approach the super-resolution limit.

Parameters

Number of scatterers3

Min separation (Rayleigh units)1.5

SNR (dB)30

Example: Gridless Recovery for Radar DOA Estimation

Setup: ULA with $M = 16$ elements. $K = 3$ sources at angles $12.3°, 15.7°, 42.1°$ (not on any standard grid).

Grid-based LASSO ( $N = 180$ , 1 degree grid):

Nearest grid points: $12°, 16°, 42°$ .
Bias: $0.3°, 0.3°, 0.1°$ .
LASSO splits the $12.3°$ source into two grid points ( $12°$ and $13°$ ) — a classic basis mismatch artifact.

Grid-based LASSO ( $N = 1800$ , 0.1 degree grid):

Reduced bias: $< 0.05°$ .
But $\mu(\mathbf{A})$ increases from 0.31 to 0.89 — near the Welch bound. Recovery becomes unstable.

Atomic norm (SDP):

Exact recovery: $12.30°, 15.70°, 42.10°$ .
No grid artifacts.
Computation: 0.5 s (SDP solver).

SPARROW (grid + refinement):

Recovery: $12.31°, 15.69°, 42.10°$ .
Computation: 0.05 s.

Solution

Why atomic norm wins

The SDP searches over the continuous angle domain, so there is no grid discretization error. The Vandermonde structure of the ULA steering vectors enables exact SDP reformulation.

SPARROW as a practical alternative

SPARROW achieves near-SDP accuracy at 10x lower computation by using the grid-based LASSO as a warm start and refining positions by gradient descent. The position gradient is $\partial a_m / \partial \theta = jm\pi\cos\theta \cdot e^{jm\pi\sin\theta}$ .

Connection to MUSIC and Vandermonde Structure

Atomic norm minimization and MUSIC both exploit the Vandermonde structure of the array manifold, but from different perspectives:

Aspect	MUSIC	Atomic norm
Input	Sample covariance $\hat{\mathbf{R}}$	Raw measurements $\mathbf{y}$
Requires	Known $K$ , high $\text{SNR}$	Neither
Guarantees	Asymptotic consistency	Finite-sample (RIP-like)
Computation	Eigendecomposition + peak search	SDP
Multi-dimensional	Straightforward (2D MUSIC)	Computationally challenging

Key insight: MUSIC is a noise-subspace method that requires estimating the number of scatterers $K$ . Atomic norm minimization is a sparsity-promoting method that automatically determines $K$ through the regularization parameter. Both reduce to analyzing the roots of a polynomial defined by the Toeplitz structure.

Common Mistake: Scalability of Gridless Methods

Mistake:

Attempting to use full atomic norm (SDP) for large-scale 2D or 3D RF imaging problems. The SDP has $O(M^3)$ complexity per iteration and the Toeplitz structure only holds for 1D arrays. For a $64 \times 64$ image grid, the SDP variables are prohibitively large.

Correction:

Use SPARROW for practical large-scale problems: coarse-grid LASSO followed by continuous position refinement via gradient descent. Reserve full atomic norm for small 1D problems (DOA, range estimation) or theoretical benchmarking.

🔧Engineering Note

SPARROW Workflow for Practical RF Imaging

Recommended gridless workflow:

Coarse LASSO on an $N$ -point grid (standard resolution). Output: approximate locations $\{n_k\}$ and amplitudes.
Position refinement via gradient descent on $\min_{\delta_k} \|\mathbf{y} - \sum_k \alpha_k \mathbf{a}(\mathbf{p}_{n_k} + \delta_k)\|^2$ . Typical convergence: 20--50 gradient steps.
Amplitude re-estimation by least squares on the refined steering vectors.
Quality check: Compare the refined residual with the grid-based residual. If improvement is $< 1$ dB, the grid resolution was adequate and refinement was unnecessary.

This workflow is standard in radar parameter estimation and adds minimal computation to the existing LASSO pipeline.

Quick Check

A radar system uses a ULA with half-wavelength spacing. Two scatterers are separated by 0.8 Rayleigh widths (below the diffraction limit). Which method can resolve them?

Atomic norm minimization — it achieves super-resolution by exploiting sparsity and the Vandermonde structure.

Grid-based LASSO with a very fine grid.

Matched filter with Hamming window.

Correction:

Atomic norm minimization — it achieves super-resolution by exploiting sparsity and the Vandermonde structure.

Atomic norm minimization can resolve scatterers below the Rayleigh limit because it exploits the known parametric structure (Vandermonde) rather than relying on Fourier resolution. The SDP effectively performs deconvolution in the continuous domain.

Historical Note: From Line Spectral Estimation to Atomic Norm

1795--2013

The problem of estimating frequencies from a finite number of samples (line spectral estimation) has a long history: Prony's method (1795), Pisarenko (1973), MUSIC (Schmidt, 1986), ESPRIT (Roy and Kailath, 1989). The atomic norm framework (Tang et al., 2013) unified these classical approaches with modern compressed sensing theory, showing that sparsity in the continuous domain can be promoted via semidefinite programming. This connection bridges 200 years of spectral estimation with 21st-century optimization.

Atomic Norm

The gauge function of the convex hull of an atom set: the tightest convex relaxation of the $\ell_0$ norm over continuous parameterizations. For ULA steering vectors, it can be computed via semidefinite programming.

Related: SPARROW

SPARROW

Practical gridless recovery method: coarse-grid LASSO initialization followed by continuous position refinement via gradient descent on the data fidelity.

Related: Atomic Norm

Basis Mismatch

The error introduced when the true continuous-domain signal is approximated on a discrete grid, causing spectral leakage and amplitude bias in sparse recovery.

Key Takeaway

Basis mismatch from grid discretization fundamentally limits on-grid sparse recovery. Atomic norm minimization avoids the grid by working in the continuous domain, reformulated as an SDP that exploits the Vandermonde structure of ULA steering vectors. SPARROW provides a practical alternative: coarse-grid LASSO followed by continuous position refinement. Atomic norm achieves super-resolution (below the Rayleigh limit) but scales as $O(M^3)$ and is limited to 1D geometries; SPARROW extends to 2D/3D at minimal additional cost.

Super-Resolution via Atomic Norm Minimization