A Caltech Library Service

Optimization Algorithms for Realizable Signal-Adapted Filter Banks


Tkacenko, Andre (2004) Optimization Algorithms for Realizable Signal-Adapted Filter Banks. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/QZYN-ND12.


Multirate filter banks are fundamental systems commonly used in digital signal processing (DSP). Typically, they are used to decompose a discrete-time signal into a set of frequency selective components called subband signals. Filter banks have been found to be useful for lossy data compression schemes such as MP3 and JPEG 2000, denoising, and signal estimation. In the last decade, transmultiplexers, the dual structures of multirate filter banks, have been shown to be useful in digital communications systems such as discrete multitone (DMT) systems for channel equalization and inter/intra-symbol interference cancellation in the presence of noise.

Recently, a special type of filter bank adapted to its input known as the principal component filter bank (PCFB) has been shown to be simultaneously optimal for a wide variety of objectives. Such filter banks are not only optimal for relevant data compression type objectives such as coding gain and multiresolution, but also for digital communications type objectives such as power minimization, when the filter bank is implemented in its transmultiplexer form. The only problem is that PCFBs, which are defined over classes of paraunitary (PU) filter banks, are only known to exist for certain classes. In particular, PCFBs are in general known to exist only in the extremal cases where the analysis/synthesis polyphase matrix has zero memory and doubly infinite memory, respectively. Furthermore, for many practical cases of inputs, the filters corresponding to the infinite-order PCFB have ideal bandpass response and are as such unrealizable. When the polyphase matrix has finite memory or a finite impulse response (FIR), it is believed that PCFBs do not exist, although this has not yet been formally proven in the literature.

The main contribution of this thesis is to bridge the gap between the zero memory PCFB and the infinite-order one. To that end, a variety of methods for the design of realizable signal-adapted FIR filter banks is presented. It is shown that a popular conventional method for designing signal-adapted FIR PU filter banks, which only requires the design of an optimal FIR compaction filter, is in fact not well suited for designing good filter banks due to the exponential complexity caused by the nonuniqueness of the FIR compaction filter. To avoid this dilemma, we propose a method by which all of the filters are obtained together. In particular, the method consists of finding an FIR PU least-squares approximant to the infinite-order PCFB polyphase matrix. Using an elegant complete parameterization of FIR PU systems in terms of canonical building blocks, an iterative greedy algorithm for solving the least-squares problem is presented. Simulation results provided here show that as the order or memory of the signal-adapted FIR PU filter bank increases, the filter bank behaves more and more like the infinite-order PCFB in terms of a variety of objectives including coding gain, multiresolution, and power minimization. This serves to bridge the gap between the zero memory and infinite memory PCFBs, which previously has not been done in the literature.

In addition to being useful for the design of PCFB-like FIR filter banks, the proposed iterative algorithm can also be used for a variety of other design problems including the FIR PU interpolation problem. Unlike the traditional FIR interpolation problem, whose solution is known in closed form, the FIR PU interpolation problem is far more difficult and is in fact still open. Despite this, the proposed algorithm can be used to find an approximant to an interpolant and sometimes even find an interpolant, as we show here through simulations.

In the second part of the thesis, we focus on the design of realizable signal-adapted quantized filter banks in which the filters are FIR but otherwise unconstrained. The filters are chosen to minimize the mean-squared error of the output, which is shown to be equivalent to maximizing the coding gain of the system. By alternately optimizing the analysis and synthesis filters, an iterative greedy algorithm, different from that mentioned above, is proposed for the design of such filter banks. Simulation results provided show that the filter banks designed exhibit performance close to the information theoretic rate-distortion bound.

Finally, we show how some of the techniques used in the above iterative algorithms can be used for the design of a channel shortening equalizer. Channel shortening equalizers, which arise in the context of digital communications, have been found to be necessary for DMT systems such as the digital subscriber loop (DSL) in which the channel impulse response must be shortened to the length of the cyclic prefix. In particular, we show how the eigenfilter technique which is used in the above-mentioned FIR PU iterative greedy algorithm, can be used for the design of a noise optimized channel shortening equalizer. As opposed to other techniques, which require a Cholesky decomposition of a certain matrix for every delay parameter considered, the proposed method is lower in complexity in that it only requires a single such decomposition for all delay values. Despite this significant decrease in complexity, it is shown through simulations that the equalizers designed using this technique perform nearly optimally in terms of observed bit rate.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:channel shortening equalizers; data compression; greedy algorithm; interpolation; multirate signal processing; paraunitary; principal component filter bank
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Electrical Engineering
Awards:Charles Wilts Prize, 2004.
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Vaidyanathan, P. P.
Thesis Committee:
  • Vaidyanathan, P. P. (chair)
  • Hassibi, Babak
  • Vrcelj, Bojan
  • Bruck, Jehoshua
  • McEliece, Robert J.
Defense Date:7 May 2004
Record Number:CaltechETD:etd-05142004-214312
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:1800
Deposited By: Imported from ETD-db
Deposited On:19 May 2004
Last Modified:04 Feb 2021 02:16

Thesis Files

PDF (tkacenko_phd_thesis.pdf) - Final Version
See Usage Policy.


Repository Staff Only: item control page