Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRobustness in Chinese Remainder Theorem
125
0
0.0
(
0
)
Added by
Hanshen Xiao
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Chinese Remainder Theorem (CRT) has been widely studied with its applications in frequency estimation, phase unwrapping, coding theory and distributed data storage. Since traditional CRT is greatly sensitive to the errors in residues due to noises, the problem of robustly reconstructing integers via the erroneous residues has been intensively studied in the literature. In order to robustly reconstruct integers, there are two kinds of traditional methods: the one is to introduce common divisors in the moduli and the other is to directly decrease the dynamic range. In this paper, we take further insight into the geometry property of the linear space associated with CRT. Echoing both ways to introduce redundancy, we propose a pseudo metric to analyze the trade-off between the error bound and the dynamic range for robust CRT in general. Furthermore, we present the first robust CRT for multiple numbers to solve the problem of the CRT-based undersampling frequency estimation in general cases. Based on symmetric polynomials, we proved that in most cases, the problem can be solved in polynomial time efficiently. The work in this paper is towards a complete theoretical solution to the open problem over 20 years.
rate research
Read More
Chinese Remainder Theorem (CRT) is a powerful approach to solve ambiguity resolution related problems such as undersampling frequency estimation and phase unwrapping which are widely applied in localization. Recently, the deterministic robust CRT for multiple numbers (RCRTMN) was proposed, which can reconstruct multiple integers with unknown relationship of residue correspondence via generalized CRT and achieves robustness to bounded errors simultaneously. Naturally, RCRTMN sheds light on CRT-based estimation for multiple objectives. In this paper, two open problems arising that how to introduce statistical methods into RCRTMN and deal with arbitrary errors introduced in residues are solved. We propose the extended version of RCRTMN assisted with Maximum Likelihood Estimation (MLE), which can tolerate unrestricted errors and bring considerable improvement in robustness.
We prove the equidistribution of subsets of $(Rr/Zz)^n$ defined by fractional parts of subsets of~$(Zz/qZz)^n$ that are constructed using the Chinese Remainder Theorem.
Generalized Chinese Remainder Theorem (CRT) is a well-known approach to solve ambiguity resolution related problems. In this paper, we study the robust CRT reconstruction for multiple numbers from a view of statistics. To the best of our knowledge, it is the first rigorous analysis on the underlying statistical model of CRT-based multiple parameter estimation. To address the problem, two novel approaches are established. One is to directly calculate a conditional maximum a posteriori probability (MAP) estimation of the residue clustering, and the other is based on a generalized wrapped Gaussian mixture model to iteratively search for MAP of both estimands and clustering. Residue error correcting codes are introduced to improve the robustness further. Experimental results show that the statistical schemes achieve much stronger robustness compared to state-of-the-art deterministic schemes, especially in heavy-noise scenarios.
Generalized Chinese Remainder Theorem (CRT) has been shown to be a powerful approach to solve the ambiguity resolution problem. However, with its close relationship to number theory, study in this area is mainly from a coding theory perspective under deterministic conditions. Nevertheless, it can be proved that even with the best deterministic condition known, the probability of success in robust reconstruction degrades exponentially as the number of estimand increases. In this paper, we present the first rigorous analysis on the underlying statistical model of CRT-based multiple parameter estimation, where a generalized Gaussian mixture with background knowledge on samplings is proposed. To address the problem, two novel approaches are introduced. One is to directly calculate the conditional maximal a posteriori probability (MAP) estimation of residue clustering, and the other is to iteratively search for MAP of both common residues and clustering. Moreover, remainder error-correcting codes are introduced to improve the robustness further. It is shown that this statistically based scheme achieves much stronger robustness compared to state-of-the-art deterministic schemes, especially in low and median Signal Noise Ratio (SNR) scenarios.
Reversible data hiding in encrypted domain (RDH-ED) schemes based on symmetric or public key encryption are mainly applied to the security of end-to-end communication. Aimed at providing reliable technical supports for multi-party security scenarios, a separable RDH-ED scheme for secret image sharing based on Chinese remainder theorem (CRT) is presented. In the application of (t, n) secret image sharing, the image is first shared into n different shares of ciphertext. Only when not less than t shares obtained, can the original image be reconstructed. In our scheme, additional data could be embedded into the image shares. To realize data extraction from the image shares and the reconstructed image separably, two data hiding methods are proposed: one is homomorphic difference expansion in encrypted domain (HDE-ED) that supports data extraction from the reconstructed image by utilizing the addition homomorphism of CRT secret sharing; the other is difference expansion in image shares (DE-IS) that supports the data extraction from the marked shares before image reconstruction. Experimental results demonstrate that the proposed scheme could not only maintain the security and the threshold function of secret sharing system, but also obtain a better reversibility and efficiency compared with most existing RDH-ED algorithms. The maximum embedding rate of HDE-ED could reach 0.5000 bits per pixel and the average embedding rate of DE-IS is 0.0545 bits per bit of ciphertext.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
