Redundancy in Non-Orthogonal Transforms

Compression efficiency is mainly driven by redundancy of the overcomplete set of functions chosen for the signal decomposition. In Matching Pursuit algorithms for example, the redundancy of the dictionary influences the convergence of the residual energy. The set of functions or dictionary plays a crucial role into the non-orthogonal transform properties, and more particularly in the ability of this transform to compact the signal energy. Redundancy provides an important criteria in the design of dictionaries and quantifies the power of the transform to capture signal features. The size of the dictionary provides a first indicator of the dictionary propertie, but it does not take into account the distribution of the atoms. This paper provides a formulation for the structural redundancy of an overcomplete set of functions. We also compute the structural redundancy factor for random dictionaries and show its implication in the practical context of Matching Pursuit.