Traditional compressed sensing relies on the assumption that a signal is sparse in a known, discrete dictionary. However, real-world signals—like the frequencies in Nuclear Magnetic Resonance (NMR) or the edges in an MRI scan—often exist in a continuous domain. When these "off-the-grid" signals are forced onto a discrete grid, the resulting "basis mismatch" leads to significant reconstruction errors.
A powerful alternative has emerged: instead of treating the signal as a sparse vector, we "lift" it into a structured matrix (such as a Hankel or Toeplitz matrix). In this higher-dimensional space, the signal's sparsity manifests as a low-rank property, allowing us to recover missing data using the tools of matrix completion.
The Hankel Lift: From Vectors to Matrices
The core mechanism of this research direction is the transformation of a 1D or 2D signal into a structured matrix. For a 1D signal composed of a few complex exponentials, we can arrange its samples into a Hankel matrix, where each ascending skew-diagonal is constant.
As Chen et al. demonstrate in their work on Enhanced Matrix Completion (EMaC), this shift-invariant structure is not arbitrary. If a signal consists of only $r$ distinct frequencies, its corresponding Hankel matrix will have a rank of exactly $r$. This transformation converts the non-linear problem of frequency estimation into a linear low-rank matrix completion problem.
This principle extends to multidimensional data. Biswas et al. show that 2D piecewise constant images can be recovered by mapping Fourier domain convolutions into multifold Toeplitz matrices. By representing image edges as the zero-set of a bandlimited function, the authors prove that the resulting matrix is low-rank, enabling perfect reconstruction from undersampled data.
The Duality of Sparsity and Rank
Why does this work? The intuition lies in the annihilating filter relationship. A signal that is sparse in the spectral domain is "predictable" in the time domain; there exists a filter that, when convolved with the signal, yields zero.
Ye et al. formalize this duality, showing that sparsity in the spatial domain translates directly to low-rank properties in structured spectral matrices. This mathematical bridge allows researchers to apply the rigorous theoretical guarantees of matrix completion—originally established by Candès for random entries—to the highly structured patterns found in signal processing. While Candès proved that nuclear norm minimization acts as a convex proxy for rank, Hassibi et al. provided the necessary and sufficient conditions for this heuristic to succeed, grounding the field in geometric theory.
Efficient Recovery Algorithms
While nuclear norm minimization is a powerful convex tool, it can be computationally expensive for high-dimensional data like MRI. Recent work has focused on more efficient, non-convex optimization strategies:
- Projected Gradient Descent (PGD): Cai et al. introduced PGD for spectral compressed sensing, demonstrating that one can iteratively project onto the space of low-rank Hankel matrices to achieve fast recovery.
- Accelerated Structured Alternating Projections (ASAP): To handle outliers and noise, Cai et al. developed ASAP, which achieves a 10x speedup over previous methods by combining Hankel structures with tangent space projections.
- Preconditioning: To further speed up convergence, Cai et al. proposed using Jacobi-preconditioned gradient descent, which maintains stability and linear convergence even under noisy conditions.
Incorporating Physical Priors
The most recent advances move beyond generic low-rank assumptions to incorporate the specific physical models of the signals being measured.
In the context of NMR and MRI, Ying et al. and Qu et al. propose Hankel matrix completion with Vandermonde Factorization (HVaF). Because a sum of exponentials naturally forms a Vandermonde structure, explicitly enforcing this factorization during the matrix completion process leads to much higher fidelity. This is particularly effective at preserving faint spectral peaks that generic low-rank methods might smooth away.
Broadening the Horizon
The utility of structured low-rank completion is not limited to imaging. Zhang demonstrates that time-series forecasting can be reframed as a "future data recovery" problem. By constructing a convolution matrix from circular shifts of existing data, the author shows that periodic or smooth signals can be recovered without needing to explicitly model complex temporal dynamics.
Whether in the form of Continuous Compressed Sensing (Yang et al.) or multi-channel MRI reconstruction (Zhang et al.), the core insight remains the same: by lifting signals into structured matrices, we can exploit the deep mathematical relationship between sparsity and rank to see what is missing.
Key Foundational Work
Exact Matrix Completion via Convex Optimization (2008) — contributed 1 concept elements to this direction.
Matrix Completion With Noise (2010) — contributed 1 concept elements to this direction.
Necessary and sufficient conditions for success of the nuclear norm heuristic for rank minimization (2008) — contributed 1 concept elements to this direction.