Matrix factorizations for reversible integer mapping

Reversible integer mapping is essential for lossless source coding by trans formation. A general matrix factorization theory for reversible integer map ping of invertible linear transforms is developed in this paper. Concepts o f the integer factor and the elementary reversible matrix (ERM) for integer mapping are introduced, and two forms of ERM-triangular ERM (TERM) and sin gle-row ERM (SERM)-are studied. We prove that there exist some approaches t o factorize a matrix into TERMs or SERMs if the transform is invertible and in a finite-dimensional space. The advantages of the integer implementatio ns of an invertible linear transform are i) mapping integers to integers, i i) perfect reconstruction, and iii) in-place calculation. We find that besi des a possible permutation matrix, the TERM factorization of an N-by-N nons ingular matrix has at most three TERMs, and its SERM factorization has at m ost N + 1 SERMs. The elementary structure of ERM transforms is the ladder s tructure. An executable factorization algorithm is also presented. Then, th e computational complexity is compared, and some optimization approaches ar e proposed. The error bounds of the integer implementations are estimated a s well. Finally, three ERM factorization examples of DFT, DCT, and DWT are given.