A Branch-and-Bound Algorithm with Reduced Search Space for Sparse Filter Design

This paper presents a branch-and-bound algorithm with reduced search space for sparse FIR filter design. To estimate the possibilities of zero positions, the second-order zero coefficients combinations are evaluated. The search space is reduced by keeping the potential zero positions (with high probabilities) and removing the non-potential positions (with low probabilities). The reduced search space is applied in branch-and bound algorithm to heuristically search for the sparse solutions. A weighted least squares (WLS) technique for quasi equiripple design is further proposed to efficiently solve the subproblems in branch-and-bound search. Simulation results demonstrate the effectiveness of the proposed algorithm.