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, in this article we propose 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, which provides an algorithm to uniquely reconstruct an integer vector from its remainders, if it is in the fundamental parallelepiped of the lattice generated by a least common right multiple of all the moduli. For some special forms of moduli, we present explicit reconstruction formulae. Moreover, 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, and accordingly, two different conditions on the remainder error bound for the reconstruction robustness are obtained, which are related to a quarter of the minimum distance of the lattice generated by the gcld of all the moduli or the Smith normal form of the gcld.
Introduction
The Chinese Remainder Theorem (CRT) is a cornerstone of number theory, providing a method to reconstruct a large integer from its remainders relative to several smaller, coprime moduli. In modern signal processing, the CRT is indispensable for resolving ambiguities in phase unwrapping and frequency estimation, particularly when operating under sub-Nyquist sampling constraints. However, as signal processing tasks increasingly involve multidimensional (MD) data—such as in radar arrays, medical imaging, and wireless sensor networks—the traditional 1D CRT faces significant limitations.
This paper, published in IEEE Transactions on Signal Processing, extends the CRT framework to the multidimensional domain, introducing the MD-CRT for integer vectors. By utilizing integer matrix moduli instead of scalars, the authors provide a robust mathematical foundation for reconstructing vectors even in the presence of noise, a critical requirement for practical MD signal processing.
The Multidimensional Challenge
Transitioning from 1D integers to MD vectors introduces two primary complexities:
- Geometric Complexity: While 1D reconstruction involves segments on a number line, MD reconstruction occurs within complex geometric structures. The "range" of unique reconstruction is defined by the fundamental parallelepiped of a lattice generated by the least common right multiple (lcrm) of the matrix moduli.
- Non-Commutativity: Unlike scalar multiplication, matrix multiplication is generally non-commutative ($AB \neq BA$). This property breaks many of the standard proofs used in 1D CRT, requiring a more sophisticated approach rooted in lattice theory and ring theory.
MD-CRT and Robust Reconstruction
The authors define the remainder of an integer vector with respect to a nonsingular integer matrix $M$. To address the "brittleness" of the classic CRT—where a small error in a single remainder can lead to a total reconstruction failure—the paper introduces the Robust MD-CRT (MD-RCRT).
The robustness of the reconstruction depends on the relationship between the moduli. The authors assume the moduli share a Greatest Common Left Divisor (gcld) matrix, denoted as $M$. Based on this, they propose two distinct reconstruction algorithms:
Algorithm 1: Lattice-Based Correction
This approach leverages the minimum distance of the lattice generated by the gcld matrix $M$. It focuses on correcting erroneous remainders by finding the closest vector within the lattice structure, effectively "denoising" the input before reconstruction.
Algorithm 2: Smith Normal Form (SNF) Decomposition
This algorithm employs the Smith Normal Form to diagonalize the matrices over integers. By transforming the MD problem into a set of decoupled 1D sub-problems, the reconstruction becomes more computationally manageable for certain classes of moduli.
The Quarter-Distance Robustness Bound
A significant contribution of this work is the derivation of a theoretical bound for robustness. The authors prove that the reconstruction of "folding vectors" (the integer quotients in the division process) is perfectly accurate as long as the error $\tau$ in the remainders satisfies:
$$\tau < \frac{\lambda_{LAT}(M)}{4}$$
where $\lambda_{LAT}(M)$ represents the minimum distance of the lattice generated by the common factor matrix $M$. This "quarter-distance" rule is a direct and elegant generalization of the $M/4$ bound established in 1D robust CRT literature.
Experimental Validation
The theoretical findings were validated through two primary methods:
- Numerical Simulations: Thousands of trials using random integer vectors confirmed that the proposed algorithms consistently achieve exact reconstruction when the noise remains within the theoretical bounds.
- MD Frequency Estimation: The MD-RCRT was applied to a 2D sinusoidal frequency estimation task using sub-Nyquist matrix sampling. The results demonstrated that the MD-RCRT could successfully identify high-frequency signals from undersampled, noisy data, significantly outperforming traditional separable 1D methods.
Conclusion and Future Directions
The MD-CRT and its robust counterpart provide a rigorous framework for multidimensional integer vector reconstruction. While the current robust version requires the quotient matrices to be pairwise commutative and coprime, it marks a substantial leap forward in MD signal processing. Future research may focus on relaxing these commutativity constraints to allow for completely arbitrary matrix moduli and optimizing the computational efficiency of solving the Closest Vector Problem (CVP) in higher dimensions.
Summary updated