Abstract
The robust Chinese remainder theorem (CRT) has been recently proposed for robustly reconstructing a large nonnegative integer from erroneous remainders. It has found many applications in signal processing, including phase unwrapping and frequency estimation under sub-Nyquist sampling. Motivated by the applications in multidimensional (MD) signal processing, this paper proposes the MD-CRT and robust MD-CRT for integer vectors. Specifically, by rephrasing the abstract CRT for rings in number-theoretic terms, we first derive the MD-CRT for integer vectors with respect to a general set of integer matrix moduli. This provides an algorithm to uniquely reconstruct an integer vector from its remainders if it lies within the fundamental parallelepiped of the lattice generated by a least common right multiple of all the moduli. Furthermore, we derive the robust MD-CRT for integer vectors when the remaining integer matrices of all the moduli, left-divided by their greatest common left divisor (GCLD), are pairwise commutative and coprime. Two different reconstruction algorithms are proposed, yielding two distinct conditions for reconstruction robustness related to the minimum distance of the lattice generated by the GCLD.
Introduction
The Chinese Remainder Theorem (CRT) is a cornerstone of number theory, traditionally used to reconstruct a large integer from its remainders modulo several smaller, coprime integers. In modern engineering, however, the classical 1D CRT faces two significant hurdles: dimensionality and brittleness. Real-world signals in radar, sonar, and medical imaging are inherently multidimensional, and the standard CRT is notoriously sensitive to noise—a single small error in a remainder can lead to a catastrophic error in the final reconstruction.
This research extends the CRT into the multidimensional (MD) realm, providing a framework for reconstructing large integer vectors from potentially noisy matrix-based remainders. This extension is vital for high-stakes applications like sub-Nyquist frequency estimation and phase unwrapping.
The MD-CRT Framework
Bridging abstract algebra and lattice theory, the authors rephrase abstract ring theory into practical number-theoretic terms. Instead of simple integer moduli, the MD-CRT utilizes nonsingular integer matrices.
A vector can be uniquely reconstructed if it resides within the "fundamental parallelepiped"—the multidimensional building block—of the lattice generated by the moduli. This geometric approach allows the theorem to handle the complexities of multidimensional space where matrix multiplication is non-commutative and the concept of a "remainder" is defined by the geometry of the lattice.
Robust Reconstruction and Algorithms
To address the "brittleness" of the classical CRT, the paper introduces a robust version of the MD-CRT. The goal is to ensure that small errors in the remainders do not lead to large errors in the reconstructed vector. The authors propose two primary algorithms for this purpose:
- Algorithm 1 (Direct Approach): This algorithm works directly with the integer matrices to find the "folding vectors" (the quotients discarded during the modulo operation).
- Algorithm 2 (SNF-Based): This approach leverages the Smith Normal Form (SNF) to diagonalize integer matrices, simplifying the reconstruction process and offering different robustness constraints.
The "secret sauce" for achieving robustness lies in the Greatest Common Left Divisor (GCLD) of the moduli. By analyzing the lattice generated by this GCLD, the authors can determine the exact noise tolerance of the system.
Key Insights: The Geometry of Error
The study reveals that the robustness of the MD-CRT is fundamentally linked to the geometric properties of lattices:
- The Lattice Connection: Robustness is determined by the minimum distance (λ) of the lattice formed by the GCLD of the moduli. The authors prove that if the remainder error (τ) is less than a quarter of this minimum distance ($τ < λ/4$), the folding vectors can be accurately determined, ensuring a stable reconstruction.
- Graceful Degradation: Unlike the classical CRT, the robust MD-CRT ensures that the reconstruction error is upper-bounded by the remainder error. This means the system degrades gracefully; small input noise results in small output noise rather than total failure.
- Algorithm-Dependent Constraints: The choice between Algorithm 1 and Algorithm 2 allows engineers to select the method that best fits their specific matrix moduli and robustness requirements.
Performance and Applications
The theoretical bounds were validated through numerical simulations using $2 \times 2$ integer circulant matrices and a case study in MD sinusoidal frequency estimation.
In the frequency estimation simulation, the authors demonstrated how high-frequency signals sampled below the Nyquist rate could be recovered by combining multiple low-rate samples using the robust MD-CRT. The results showed a high probability of detection even at low Signal-to-Noise Ratios (SNR), with mean reconstruction errors staying well below the theoretical maximum until noise levels crossed the "catastrophic" threshold defined by the lattice geometry.
Conclusion and Future Work
This work provides a robust mathematical foundation for multidimensional signal processing under sub-Nyquist sampling. While the current robust MD-CRT requires the "quotient" matrices to be pairwise commutative and coprime, it covers many practical engineering scenarios. Future research may focus on developing a "universal" robust MD-CRT for arbitrary matrices and extending these principles from integer vectors to real-valued multidimensional signals.
Summary updated