Abstract
Signal sampling and reconstruction is a fundamental engineering task at the heart of signal processing. The celebrated Shannon-Nyquist theorem guarantees perfect signal reconstruction from uniform samples, obtained at a rate twice the maximum frequency present in the signal. Unfortunately a large number of signals of interest are far from being band-limited. This motivated research on reconstruction from sub-Nyquist samples, which mainly hinges on the use of random/incoherent sampling procedures. However, uniform or regular sampling is more appealing in practice and from the system design point of view, as it is far simpler to implement, and often necessary due to system constraints. In this work, we study regular sampling and reconstruction of three- or higher-dimensional signals (tensors). We show that reconstructing a tensor signal from regular samples is feasible. Under the proposed framework, the sample complexity is determined by the tensor rank-rather than the signal bandwidth. This result offers new perspectives for designing practical regular sampling patterns and systems for signals that are naturally tensors, e.g., images and video. For a concrete application, we show that functional magnetic resonance imaging (fMRI) acceleration is a tensor sampling problem, and design practical sampling schemes and an algorithmic framework to handle it. Numerical results show that our tensor sampling strategy accelerates the fMRI sampling process significantly without sacrificing reconstruction accuracy.
Introduction
In signal processing, the Shannon-Nyquist theorem is the gold standard, but it requires sampling at twice the maximum frequency. For wideband signals, this rate is often prohibitively high. To circumvent this, fields like Compressive Sensing (CS) and Low-Rank Matrix Completion (LRMC) allow for "sub-Nyquist" sampling. However, these techniques usually rely on random or incoherent sampling. While mathematically elegant, random sampling is difficult to implement in hardware. In systems like MRI, hardware constraints make regular, uniform sampling much more efficient.
This research breaks the "randomness requirement" in sub-Nyquist signal reconstruction. By treating multidimensional signals as tensors, the authors prove that perfect reconstruction is possible from regular, structured samples at rates far below the Nyquist limit, provided the signal has a low tensor rank.
Methods
The authors leverage Tensor Algebra, specifically the Canonical Polyadic Decomposition (CPD), to model multidimensional signals as third-order (or higher) tensors. In this framework, the complexity of a signal is determined by its tensor rank, not its frequency bandwidth.
Key Sampling Paradigms
The paper introduces three structured sampling schemes designed to be hardware-friendly:
- Fiber Sampling: Sampling 1D "threads" through the tensor.
- Slab Sampling: Observing entire "slices" or slabs of the tensor in different modes.
- Entry Sampling: A regular grid of individual points.
The RETSINA Algorithm
To reconstruct the signal, the authors propose the REgular Tensor Sampling and INterpolation Algorithm (RETSINA). The algorithm follows a three-step process:
- Sub-tensor Decomposition: Compute the CPD of the sampled sub-tensors independently.
- Ambiguity Resolution: Use overlapping "common information" between sampled patterns to align the factors, resolving inherent permutation and scaling ambiguities.
- Coupled CPD: Solve a joint optimization problem to refine the estimates and fill in the missing entries.
Experimental Results
The framework was evaluated using synthetic data (tensors up to $500 \times 500 \times 500$) and real fMRI k-space scans.
- Extreme Compression: In synthetic tests, a tensor with rank 1000 could be recovered with a sampling ratio as low as 0.019 (less than 2% of the data).
- fMRI Performance: In 3-fold acceleration tests, RETSINA achieved a Normalized Reconstruction Error (NRE) of 0.124, significantly better than the baseline k-t Focuss (0.339).
- Computational Efficiency: RETSINA was much faster, taking 12 minutes compared to 25.6 minutes for k-t Focuss and 480 minutes for k-t SLR.
- Phase Preservation: Unlike matrix-based methods, RETSINA reconstructs both magnitude and phase, which is critical for medical imaging.
Conclusion
This work demonstrates that deterministic guarantees for signal recovery can be achieved using regular sampling patterns, provided the signal is modeled as a low-rank tensor. This approach is highly compatible with existing MRI hardware and offers significant speedups for clinical applications. Future work will address the challenges of automated rank estimation and further optimization for real-time GPU implementation.
Summary updated