A fast O(N) algorithm for adaptive filter bank design

Designing optimal filter banks for subband coding applications has recently attracted considerable attention. In particular, the authors have developed an adaptive algorithm based on stochastic gradient descent (SGD) that enables one to optimize two channel paraunitary filter banks in an on-line fashion. The idea has also been extended to the case of tree-structured filter banks. The computational complexity of the algorithm proposed is proportional to N² where N is the number of stages in the paraunitary lattice. In this paper we derive a fast algorithm which reduces the amount of computation to O(N). We also show that the new algorithm can be implemented using an IIR lattice. Some issues regarding numerical stability of the IIR implementation are also discussed