Design of sparse filters by a discrete filled function technique

Abstract

In this paper, we consider the sparse filter design problem where some of the coefficients can be reduced to zeroes in order to lower implementation complexity. The objective is to choose the fewest number of nonzero filter coefficients to meet a given performance requirement. We formulate a discrete optimization problem to minimize the number of nonzero terms and develop a discrete search method to find the minimal nonzero terms. In each step, we need to consider a subproblem to design the filter coefficients with a given set of nonzero terms. We formulate this subproblem as a linear programming problem and apply an exchange algorithm to find the optimal coefficients. For illustration, we compare the proposed algorithm with existing methods and show that the proposed method gives better results in all our test cases.