Abstract
Many signals are modeled as a superposition of exponential functions in spectroscopy of chemistry, biology, and medical imaging. This paper studies the problem of recovering exponential signals from a random subset of samples. We exploit the Vandermonde structure of the Hankel matrix formed by the exponential signal and formulate signal recovery as Hankel matrix completion with Vandermonde factorization (HVaF). A numerical algorithm is developed to solve the proposed model and its sequence convergence is analyzed theoretically. Experiments on synthetic data demonstrate that HVaF succeeds over a wider regime than the state-of-the-art nuclear-norm-minimization-based Hankel matrix completion method, while it has a less restriction on frequency separation than the state-of-the-art atomic norm minimization and fast iterative hard thresholding methods. The effectiveness of HVaF is further validated on biological magnetic resonance spectroscopy data.
Introduction
In fields such as chemistry, biology, and medical imaging, signals are frequently modeled as a superposition of complex exponential functions. A significant bottleneck in Nuclear Magnetic Resonance (NMR) spectroscopy is the long duration required for data acquisition. To accelerate this process, researchers utilize non-uniform sampling (NUS), collecting only a small fraction of the data. However, accurately reconstructing the full signal from these sparse measurements remains a significant challenge.
The Challenge of Signal Recovery
Existing approaches for signal reconstruction have notable drawbacks:
- Compressed Sensing: Often requires frequencies to lie on a predefined grid, leading to "basis mismatch" errors.
- Atomic Norm Minimization (ANM): Operates in the continuous frequency domain but requires frequencies to be well-separated and does not easily extend to damped (decaying) signals.
- Low-Rank Hankel Matrix Completion (LRHMC): While flexible, it does not fully exploit the specific mathematical structure of exponential signals, often requiring more data points for successful recovery.
Proposed Method: HVaF
The authors propose a new model called Hankel matrix completion with Vandermonde Factorization (HVaF). The core innovation lies in explicitly exploiting the mathematical property that the Hankel matrix of a sum-of-exponentials signal can be factorized into a product involving Vandermonde matrices.
Instead of merely enforcing that the overall Hankel matrix is low-rank, HVaF enforces structure on the individual factors of the matrix factorization ($Hx = UV^T$). Specifically, the model applies a nuclear norm penalty to the Hankel matrices formed by each column of $U$ and $V$, encouraging each column to represent a single exponential component. This non-convex optimization problem is solved using an Alternating Direction Method of Multipliers (ADMM) framework combined with a continuation scheme to ensure convergence.
Experimental Evaluation
The researchers evaluated HVaF using two main types of data:
- Synthetic Data: Superpositions of undamped and damped complex sinusoids with varying degrees of frequency separation and random sampling patterns.
- Real Biological Data: A realistic 2D $^{1}H-^{15}N$ NMR spectrum. The time-domain data was non-uniformly sampled using a Poisson-gap pattern at a low sampling rate (22%).
Key Results
In synthetic tests, HVaF demonstrated a significantly larger "success region" in phase transition plots (Number of Exponentials $R$ vs. Number of Measurements $M$) compared to state-of-the-art methods like EMaC and FIHT.
HVaF is also considerably less sensitive to frequency separation. It can distinguish between two peaks that are very close together, where other methods like ANM or FIHT would fail or merge them. Furthermore, the algorithm proved robust to rank overestimation, succeeding even when the expected number of exponentials was preset to be much larger than the true number. On real biological NMR data, HVaF recovered weak peaks that were underestimated by standard methods, achieving lower relative error and higher correlation with the ground truth spectrum.
Conclusion
HVaF provides a robust framework for recovering complex exponential signals by leveraging the inherent Vandermonde structure of their Hankel matrices. Its ability to handle damped signals and resolve closely spaced frequencies makes it particularly effective for fast NMR spectroscopy. While the computational cost of multiple Singular Value Decompositions (SVDs) is a consideration for very large datasets, the gains in reconstruction accuracy and parameter estimation represent a significant advancement in the field.
Summary updated