Discrete wavelet transforms over finite sets which are translation invariant

The discrete wavelet transform was originally a linear operator that works on signals that are modeled as functions from the integers into the real or complex numbers. However, many signals have discrete function values. This paper builds on two recent developments: the extension of the discrete wavelet transform to finite valued signals and the research of nonlinear wavelet transforms triggered by the introduction of the lifting scheme by Sweldens. It defines an essentially nonlinear translation invariant discrete wavelet transform that works on signals that are functions from the integers into any finite set. Such transforms can be calculated very time efficiently since only discrete arithmetic is needed. Properties of these generalized discrete wavelet transforms are given along with an elaborate example of such a transform. In addition, an upper bound is given for the number of certain kinds of discrete wavelet transforms over finite sets and it is shown that, in case the finite set is a ring, there are much more nonlinear transforms than linear transforms. Finally the paper presents some ideas to find explicit examples of discrete wavelet transforms over finite sets.