Exact and Robust Reconstructions of Integer Vectors Based on Multidimensional Chinese Remainder Theorem (MD-CRT)

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 paper 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.

References in corpus (7)

• Multi-Stage Robust Chinese Remainder Theorem
• Towards Robustness in Residue Number Systems
• Exact and Robust Reconstructions of Integer Vectors Based on Multidimensional Chinese Remainder Theorem (MD-CRT)
• Coprime Sensing via Chinese Remaindering over Quadratic Fields, Part I: Array Designs
• Coprime Sensing via Chinese Remaindering over Quadratic Fields, Part II: Generalizations and Applications
• On Solving a Generalized Chinese Remainder Theorem in the Presence of Remainder Errors
• Selecting wavelengths for least squares range estimation

Cited by in corpus (4)

• Exact and Robust Reconstructions of Integer Vectors Based on Multidimensional Chinese Remainder Theorem (MD-CRT)
• Multivariate Dynamical Sampling in $l^2({\mathbb{Z}}^2)$ and Shift-Invariant Spaces Associated with Linear Canonical Transform
• On the Foundation of Sparse Sensing (Part I): Necessary and Sufficient Sampling Theory and Robust Remaindering Problem
• On the Foundation of Sparse Sensing (Part II): Diophantine Sampling and Array Configuration