Design of Discrete-Time Filters for Efficient Implementation

The cost of implementation of discrete-time filters is often strongly dependent on the number of non-zero filter coefficients or the precision with which the coefficients are represented. This work addresses the design of sparse and bit-efficient filters under different constraints on filter performance in the context of frequency response approximation, signal estimation, and signal detection.

This talk focuses mainly on sparse filter design subject to a quadratic constraint, a formulation that encompasses several filtering tasks. The problem admits efficient and exact solutions in special cases. The general case is much more difficult computationally and many heuristic algorithms have been proposed, usually without guarantees. The emphasis in this talk is on optimal algorithms based on the branch-and-bound procedure. The complexity of branch-and-bound is reduced through the use of bounds that are good approximations to the true optimal cost and can also be computed efficiently. Several bounding methods are developed, many involving relaxations of the original problem, and their approximation properties are discussed. Numerical experiments show that the bounds can result in substantial reductions in computational complexity. Applications to channel equalization and minimum-variance distortionless-response beamforming are presented. Extensions to bit-efficient design and sparse design under a Chebyshev constraint are described briefly.