Exact deconvolution using number-theoretic transforms

Chinese remainder theorem cyclic convolution deconvolution number theoretic transforms reconstruction recursive computation of divided differences residue arithmetic

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Numerical methods for trigonometric approximation and interpolation (65T40) Realizations from input-output data (93B15)

Review text

Let us consider a one- (or two-) dimensional deconvolution problem \(a*x=b\) where * stands for cyclic convolution, a and b are known integer vectors (or matrices) and x is a vector (matrix) of the formal solution in the field of rational numbers \({\mathbb{Q}}\). This solution exists and is unique if and only if the circulant (block) matrix A associated with a is invertible over \({\mathbb{Q}}\), i.e. the determinant \(d=\det A\neq 0\). Using symmetric residue arithmetic modulo an odd integer \(m>1\) and number theoretic transforms (NTTs) the authors present two algorithms which yield the exact solution x without round-off errors. The first algorithm assumes \(m=m_ 1m_ 2...m_ s\) where \(m_ i\), \(i=1,2,...,s\) are relatively prime. Applying the Chinese remainder theorem (CRT) the original problem is converted to s deconvolution problems over residue rings modulo \(m_ i\), \(i=1,...,s\), which are solved in parallel by means of a set of s NTTs. Within this algorithm a new computational scheme is introduced for the CRT reconstruction of the symmetric residue modulo m from the symmetric residues modulo \(m_ i\), \(i=1,...,s\). This scheme resembles a modular analogue of the recursive computation of divided differences. The value of d is obtained as an intermediate result, allowing thus the regularity check \(d\neq 0\) as well. An example of a \(3\times 3\) deconvolution illustrates the above method. The second algorithm is a generalization of the recent result of \textit{M. Morháč} [Comput. Math. Appl. Part A 12, 319-329 (1986; Zbl 0609.65030)] to arbitrary length (not necessarily the 2-radix one), using one NTT modulo m (not necessarily the Fermat number transform) several times. This algorithm assumes the a priori knowledge of \(d\neq 0\).

Recommendations

Cites work

Cited in

(6)

This page was built for publication: Exact deconvolution using number-theoretic transforms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1123581)