Low-complexity approximations for discrete transforms : design, fast algorithms, image coding, and use as a tool in statistical inference

Abstract

Discrete transforms play an important role in the context of signal processing. They are pivotal tools because they allow us to analyze and interpret data in the domain of transforms, which often reveal useful patterns. In particular, we can mention the discrete Fourier transform (DFT), the Karhunen-Loève transform (KLT) and the discrete cosine transform (DCT) as the most relevant transforms in the context of signal and image processing. Although the relevance of using these transforms has been widely corroborated in several studies, the computational costs required for their implementations can become prohibitive in contexts where we have large amounts of data and/or demand for low-complexity devices. In this context, fast algorithms can be a solution for the reduction of arithmetic operations necessary for computing the transforms. However, it is still necessary to deal with the floating-point arithmetic. Thus, several low-complexity transform approximations have been developed, as a low-cost alternative for computing these transforms. This thesis is divided into two parts. In the first part, we propose several classes of low complexity approximations for the KLT and the DCT, fast algorithms, and demonstrate their usability in the context of image processing. In the second part of the thesis, we present approximation classes for the DFT and their applicability in problems of statistical inference, as in the context of signal detection. From the results obtained, we can conclude that the low complexity approximations for the transforms can be considered excellent alternatives in contexts where there is a massive amount of data to be processed or in the case of implementation in low-consumption hardware.