Traditional compressed sensing relies on a fundamental assumption: the signal of interest is sparse within a predefined, discrete dictionary. In applications like radar, wireless communications, and medical imaging, we assume the signal consists of a few frequencies or angles of arrival. However, physical parameters like frequency and time delay are continuous. When a true signal parameter falls between the points of a fixed grid, the resulting "basis mismatch" leads to power leakage and severe estimation errors.
To solve this, researchers have developed gridless or off-the-grid recovery methods. These techniques move away from discrete bins and treat signal parameters as continuous variables, allowing for "super-resolution" that is limited by noise rather than the granularity of a search grid.
The Problem of Basis Mismatch
In standard sparse recovery, we approximate a signal as a sum of atoms from a finite grid. If the true frequency of a signal is $10.52$ Hz but our grid only includes $10.5$ and $10.6$ Hz, the optimization algorithm will attempt to represent the signal using a combination of nearby grid points. This creates a "blurred" estimate and prevents the recovery of the true, sparse underlying structure.
Badri Narayan Bhaskar and Gongguo Tang identified this as a fundamental bottleneck in Compressed Sensing off the Grid. They argued that increasing grid density is not a viable solution, as it leads to highly correlated dictionary columns, making the optimization problem numerically unstable and computationally expensive.
Atomic Norm Minimization
The breakthrough in gridless recovery was the introduction of the atomic norm. Instead of defining sparsity over a discrete set of vectors, Tang and Bhaskar defined a norm based on the convex hull of an infinite set of atoms—such as complex exponentials with any continuous frequency.
In Atomic norm denoising with applications to line spectral estimation, the authors showed that this infinite-dimensional problem can often be solved using finite-dimensional Semidefinite Programming (SDP). By enforcing a Toeplitz structure on the signal's covariance matrix, the atomic norm promotes sparsity in the continuous domain. This allows for the exact recovery of frequencies from a few samples, provided the frequencies are sufficiently separated.
Newtonized Refinement and Greedy Approaches
While atomic norm minimization provides strong theoretical guarantees, the resulting SDPs can be computationally heavy for large-scale systems like massive MIMO. An alternative approach is to use greedy algorithms that "refine" their estimates in the continuous space.
Jiang Zhu and Zhiwei Xu developed Newtonized Orthogonal Matching Pursuit. This method starts with a standard greedy search on a coarse grid but follows each step with a Newton-type local optimization. This "slides" the estimated parameters toward their true continuous values, achieving sub-grid accuracy without the cost of a dense dictionary. Similarly, Mats Viberg introduced C-LASSO, which uses a homotopy path to adjust parameter estimates toward optimality in a continuous framework, significantly improving robustness to sources with varying power levels.
Tensor Decompositions for Multi-Dimensional Signals
For signals with multiple dimensions—such as those in massive MIMO systems involving delay, Doppler, and angle—the problem becomes even more complex. Jun Fang and Hongbin Li proposed using tensor decompositions to achieve gridless estimation.
In Spectral Compressed Sensing via CANDECOMP/PARAFAC Decomposition, they demonstrated that by modeling received signals as tensors and imposing a Vandermonde structure on the factor matrices, one can directly map latent components to continuous physical parameters. This approach bypasses the need for any grid and avoids the "leakage" effects that plague traditional Fourier-based methods in high-mobility environments.
Achieving Super-Resolution
The ultimate goal of these methods is super-resolution: the ability to distinguish targets closer than the classical Rayleigh limit (the inverse of the signal bandwidth). Reinhard Heckel and Veniamin I. Morgenshtern proved in Super-Resolution Radar that targets can be perfectly recovered in the continuous delay-Doppler space using convex optimization, even when they are separated by only a small fraction of the traditional resolution limit.
By treating parameters as continuous random variables—often within a variational Bayesian framework as seen in the work of Jiang Zhu on Grid-less Variational Direction of Arrival Estimation—these systems can reach the theoretical Cramer-Rao Bound for estimation accuracy. This shift from discrete to continuous thinking has become essential for modern high-precision sensing, from 6G channel estimation to quantitative MRI.