Aliaksei Sandryhaila (PhD. thesis, Electrical and Computer Engineering, Carnegie Mellon University, 2010)
Algebraic Signal Processing: Modeling and Subband Analysis
Preprint (1.8 MB)

Traditional linear signal processing is based on viewing signals as sequences or functions in time that flow in one direction, from past through present into future. Somewhat surprisingly, the assumption that the most basic operation that can be performed on a signal is a time shift, or ``delay,'' is sufficient to derive many relevant signal processing concepts, including spectrum, Fourier transform, frequency response and others. This observation has led us to search for other linear, shift-invariant signal models that are based on a different definition of a basic signal shift, and hence have different notions of filtering, spectrum, and Fourier transform. Such models can serve as alternatives to the time signal model traditionally assumed in modern linear signal processing, and provide valuable insights into signal modeling in different areas of signal processing. The platform for our work is the algebraic signal processing theory, a recently developed axiomatic approach to, as well as a generalization of linear signal processing. In this thesis we present a new class of infinite and finite discrete signal models built on a new basic shift called the generic nearest-neighbor shift. We construct filter and signals spaces for these new models, and identify the corresponding signal processing concepts, such as frequency, spectrum, Fourier transform, frequency response, and convolution. We also derive relevant properties of these models, such as the Parseval equality and the notions of low and high frequencies. We then consider the problem of subband analysis for the newly constructed signal models. As a corresponding subband analysis tool for infinite signals, we extend the definition of filter banks to the new models, and construct perfect-reconstruction filter banks for subband decomposition. We also construct filter banks for robust signal transmission. As a subband analysis tool for finite signals, we study the implementation of appropriate discrete Fourier transforms. We propose a mathematical approach to the factorization of general discrete Fourier transform matrices, and apply it to construct fast computational algorithms for the Fourier transforms of interest. Finally, we consider possible applications of the constructed signal models in different areas of signal processing. For example, we demonstrate that the use of new signal models can be beneficial in such applications as the compression of ECG signals and the efficient implementation of widely-used discrete signal transforms, such as the discrete cosine transform.

Signal transforms, Algebraic signal processing theory: Current status, Theory of transform algorithms, Frames, Filter banks, Orthogonal polynomials, Alternative signal models