Traditional compressed sensing relies on the assumption that signals are sparse within a discrete dictionary. For instance, in line spectral estimation, we typically assume that frequencies lie exactly on a predefined grid. However, physical parameters—such as a target's velocity, a radio wave's angle of arrival, or a musical tone—exist on a continuum.
When a true parameter falls between two grid points, traditional methods suffer from basis mismatch or gridding errors. As Wenjing Liao notes in MUSIC for multidimensional spectral estimation: stability and super-resolution, forcing continuous signals onto a fixed lattice introduces severe spectral leakage and limits resolution. Instead of finding a sparse representation, standard $\ell_1$ optimization spreads the signal's energy across multiple adjacent grid points, destroying the very sparsity the algorithm relies on. Gongguo Tang et al. emphasize in Demixing Sines and Spikes: Robust Spectral Super-resolution in the Presence of Outliers that this fundamental limitation necessitates frameworks capable of resolving continuous values without being constrained by a predefined sampling lattice.
Defining the Continuous Convex Hull
To bypass the grid entirely, we must operate directly in the continuous domain. Instead of selecting columns from a finite matrix, we consider an infinite dictionary of atoms parameterized by a continuous variable, such as $\mathcal{A} = \{e^{j 2\pi f t} : f \in 0, 1)\}$. To enforce sparsity over this infinite set, researchers utilize the atomic norm.
Geometrically, the $\ell_1$ norm is the convex hull of a finite set of discrete coordinate vectors (forming a cross-polytope). The atomic norm generalizes this concept: it is the convex hull of the infinite set of continuous atoms. In their foundational framework, [Badri Narayan Bhaskar et al. (Compressed Sensing off the Grid) demonstrated that minimizing this atomic norm allows for the exact recovery of continuous frequencies from a few random samples. By optimizing over the continuous convex hull, the framework naturally selects the exact sparse combination of continuous parameters without any discretization error.
From Infinite Atoms to Semidefinite Programming
How do we computationally minimize a norm defined over an infinite set of atoms? We cannot check infinitely many candidate frequencies. The magic of atomic norm minimization lies in a mathematical duality: for specific continuous atom sets (like complex exponentials), the atomic norm can be exactly reformulated as a finite-dimensional Semidefinite Program (SDP).
This connection relies on the Vandermonde decomposition of positive semidefinite Toeplitz matrices. Minimizing the atomic norm of a 1D line spectrum is mathematically equivalent to minimizing the trace of a Toeplitz matrix subject to a linear matrix inequality. As Zai Yang et al. explain in Continuous Compressed Sensing With a Single or Multiple Measurement Vectors, this formulation bridges continuous compressed sensing with low-rank matrix completion. The rank of the underlying Toeplitz matrix corresponds directly to the number of continuous frequencies present in the signal.
To understand why this optimization successfully identifies the exact frequencies, we can look at the dual optimization problem. The dual problem constructs a dual polynomial whose magnitude is bounded by $1$ across the entire continuous parameter space. Crucially, the dual polynomial reaches a magnitude of exactly $1$ precisely at the true, off-grid frequencies of the signal. By locating where the dual polynomial "touches" this boundary, we can read off the exact continuous parameters.
Scaling to Multiple Measurement Vectors
In many practical scenarios, such as multi-antenna arrays or sequential time snapshots, we observe an ensemble of signals that share the same underlying continuous frequencies but vary in amplitude. Atomic norm minimization naturally scales to this Multiple Measurement Vector (MMV) setting.
Yuejie Chi demonstrated in Joint sparsity recovery for spectral compressed sensing that leveraging this shared spectral structure significantly reduces the number of measurements required for exact recovery. To formalize this across distributed systems, Zhenqi Lu et al. introduced a concatenated atomic norm (CA-norm) in Distributed Compressed Sensing off the Grid to enforce joint sparsity across separate sensors.
Furthermore, Yuanxin Li et al. in Off-the-Grid Line Spectrum Denoising and Estimation With Multiple Measurement Vectors and Zai Yang in Exact Joint Sparse Frequency Recovery via Optimization Methods showed that the MMV atomic norm framework relaxes the required separation conditions between frequencies. Exploiting temporal or spatial redundancy allows the algorithm to resolve continuous components that are spaced much closer together than traditional single-snapshot limits allow.
Robustness against Noise and Outliers
Real-world signals are rarely pristine; they are frequently corrupted by noise and gross outliers. To handle bounded noise, Badri Narayan Bhaskar et al. (Near Minimax Line Spectral Estimation, Near Minimax Line Spectral Estimation) proposed Atomic Norm Soft Thresholding (AST). Instead of enforcing an exact data constraint, AST regularizes the atomic norm alongside a quadratic error term, achieving near-minimax optimal denoising performance in the continuous frequency domain.
When data suffers from sparse, large-magnitude corruptions in the time domain, the problem becomes one of "demixing sines and spikes." The authors of Demixing Sines and Spikes: Robust Spectral Super-resolution in the Presence of Outliers proved that by minimizing a combination of the continuous atomic norm (for the sines) and the $\ell_1$ norm (for the spikes), one can perfectly isolate continuous spectral lines from time-domain outliers. This was further extended to the MMV setting by Sajad Daei et al. in Demixing Sines and Spikes Using Multiple Measurement Vectors, demonstrating that temporal redundancy enhances robustness against both noise and outliers simultaneously.
Real-World Super-Resolution Applications
Because physical waves propagate through continuous space and time, atomic norm minimization has become a cornerstone for high-resolution sensing applications across several domains:
- Radar and Sonar: Reinhard Heckel showed in Super-Resolution MIMO Radar that Multiple-Input Multiple-Output (MIMO) radar can achieve super-resolution recovery of continuous target angles, delays, and Doppler shifts. In passive sonar, Jinhong Kim et al. (Tonal signal detection in passive sonar systems using atomic norm minimization) and Junhan Kim et al. (Detection of tonal frequency of underwater radiated noise via atomic norm minimization) utilized the framework to eliminate spectral leakage and accurately detect the tonal frequencies of underwater radiated noise in low-SNR environments. Additionally, Yinchuan Li et al. applied continuous parameter estimation to track target positions and velocities using ambient OFDM communication signals in Multi-target Position and Velocity Estimation Using OFDM Communication Signals.
- Wireless Communications: In millimeter-wave (mmWave) systems, Junquan Deng et al. leveraged the framework in MmWave Channel Estimation via Atomic Norm Minimization for Multi-User Hybrid Precoding to estimate sparse spatial channels from a continuous dictionary of steering vectors, overcoming the hardware limitations of having few RF chains for hundreds of antennas.
- Advanced Waveform Recovery: Christos Thrampoulidis et al. extended the framework to phaseless super-resolution in Phaseless super-resolution in the continuous domain, recovering continuous-domain Dirac deltas from low-frequency Fourier magnitude measurements alone. For joint radar-communications spectrum sharing, Román Jácome et al. utilized multivariate atomic norms in Multi-Antenna Dual-Blind Deconvolution for Joint Radar-Communications via SoMAN Minimization to execute blind deconvolution across continuous dimensions of time, frequency, and spatial angle simultaneously.
Key Foundational Work
Compressed Sensing off the Grid (2012) — contributed 2 concept elements to this direction.
Accurate Spectral Analysis of Two-Dimensional Point Sets (2011) — contributed 1 concept elements to this direction.