Iterative reweighted l1 design of sparse FIR filters

doi:10.1016/j.sigpro.2011.09.031

Signal Processing

Volume 92, Issue 4, April 2012, Pages 905-911

https://doi.org/10.1016/j.sigpro.2011.09.031 Get rights and content

Abstract

Sparse FIR filters have lower implementation complexity than full filters, while keeping a good performance level. This paper describes a new method for designing 1D and 2D sparse filters in the minimax sense using a mixture of reweighted l₁ minimization and greedy iterations. The combination proves to be quite efficient; after the reweighted l₁ minimization stage introduces zero coefficients in bulk, a small number of greedy iterations serve to eliminate a few extra coefficients. Experimental results and a comparison with the latest methods show that the proposed method performs very well both in the running speed and in the quality of the solutions obtained.

Highlights

► Sparse FIR filters have lower implementation complexity than full filters. ► We optimize sparse 1D and 2D linear phase filters. ► We start with reweighted $l_{1}$ minimization, which eliminates coefficients in bulk. ► Further greedy iterations eliminate coefficients one by one. ► The overall process gives better results or is faster than previous methods.

Introduction

When designing 1D and 2D discrete-time filters, two important considered factors are: the filter quality and the cost of the implementation. Traditional design methods like the Parks–McClellan algorithm [1] or those based on convex optimization [2] can be used to design the filter with minimum order satisfying the design constraints. Other techniques are based on various implementation schemes and achieve the trade-off by restricting the coefficients of the filters to binary values [3] or powers of two [4] in order to completely remove the multiplications or replace them with shifts, recursive running-sum prefilters [5], cyclotomic polynomial prefilters [6], interpolated FIR filters [7] and frequency-response masking [8]. Many of these techniques can be extended to the 2D case, like for example frequency-response masking [9].

The approach in this paper is to use tools from the field of sparse representations [10] and the basic idea is to reduce the number of additions and multiplications by setting coefficients of the filters to zero. We call a filter sparse if it contains a relatively large number of zero coefficients. Since the problem of minimizing the number of nonzero coefficients is in general NP-hard [11], fast methods that give good approximations of the optimal solution were developed. The two most popular approaches that are used to induce sparsity are: convex relaxation to l₁ minimization [12] and greedy methods [13]. In this sense, previous work for sparse filter design includes the use of the orthogonal matching pursuit algorithm [14], greedy coefficient elimination [15] and linear programming [15], [16], [17]; see also [18] for a mixed integer programming approach. In this paper we consider a combination of the two approaches to design filters in the minimax sense. In the first stage, reweighted l₁ minimization (IRL1) [19] is used to induce a relatively large number of zero coefficients and then, in the second stage, greedy iterations are used to cut down extra coefficients one by one. This combination proves to be very efficient both in the running time and the quality of the obtained solutions.

The paper is structured as follows: Section 2 details the design problems for 1D and 2D FIR filters, Section 3 presents the proposed method called IRL1G and finally Section 4 outlines the results and a comparison with two other recent techniques used to design sparse filters.

Section snippets

1D FIR filter design

Consider H(z) the linear phase FIR filter with odd length N whose amplitude response is $A (ω) = \sum_{k = - n}^{n} h_{k} e^{- kj ω} = h_{0} + \sum_{k = 1}^{n} 2 h_{k} \cos (k ω),$ where $h_{k} \in R$ , $n = (N - 1) / 2$ and the rightmost form of (1) results from the symmetry of the coefficients: $h_{k} = h_{- k}$ . Given a desired response $D (ω)$ , the goal is to compute coefficients h_k such that the maximum absolute value of the error $E (ω) = A (ω) - D (ω)$ is minimized over $0 \leq ω \leq π$ . Using a uniformly distributed dense grid of points $ω_{i} \in [0, π], i = 1, \dots, L$ (transition bands not included), this

Design of sparse filters

Since the problems of designing sparse filters were formulated in the same manner for the 1D and 2D cases, this section describes an optimization method that works in both situations. Since the maximization of the number of zero coefficients is NP-hard in general, at the center of our method stands the l₁ minimization technique. We hope to obtain good results because the l₁ minimization problem is the convex relaxation of the original problem which is discrete in nature and non-convex. In order

1D case

We present here the results obtained by the IRL1G method for designing lowpass 1D filters with $ω_{p} = 0.26 π$ and $ω_{s} = 0.34 π$ . The parameters of the IRL1G algorithm are: $maxSteps = 15$ , $μ = 1$ , $ε = 10^{- 6}$ , $ε^{stop} = 10^{- 4}$ , $ε^{cut} = 10^{- 7}$ , $L = 15 N$ and $μ = 1$ . For comparison, the smallest coefficient rule (SCR) and the l₁ minimization (called here M1N) algorithms from [15] are also implemented.

In the case of SCR, if the solution of the optimization problem ends up having M zero coefficients, then using this strategy, M+1 LPs are

Conclusions

By combining two of the most popular approaches in the field of sparse representations we have developed a new efficient method called IRL1G that can be used to design sparse 1D and 2D FIR filters. The power of IRL1G relies on its two stages: the reweighted l₁ minimization that induces a relatively large number of zero coefficients in just a few iterations and the polishing greedy iterations that run only for a few steps and further eliminate a few extra coefficients. This combination means

Acknowledgements

This work was done in preparation of project PN-II-ID-PCE-2011-3-0400. Cristian Rusu's work has been funded by the Sectoral Operational Programme Human Resources Development 2007–2013 of the Romanian Ministry of Labour, Family and Social Protection through the Financial Agreement POSDRU/88 /1.5/S/61178.

References (19)

J.H. McClellan et al.
A unified approach to the design of optimum FIR linear phase digital filters
IEEE Transactions on Circuit Theory
(1973)
S.-P. Wu, S. Boyd, L. Vandenberghe, FIR filter design via semidefinite programming and spectral factorization, in: IEEE...
M. Bateman et al.
An approach to programmable CTD filters using coefficients 0, +1, and −1
IEEE Transactions on Circuits and Systems
(1980)
D. Li et al.
A polynomial-time algorithm for designing FIR filters with power-of-two coefficients
IEEE Transactions on Signal Processing
(2002)
J. Adams et al.
Some efficient digital prefilter structures
IEEE Transactions on Circuits and Systems
(1984)
R.J. Hartnett et al.
On the use of cyclotomic polynomial prefilters for efficient FIR filter design
IEEE Transactions on Signal Processing
(1993)
T. Saramaki et al.
Design of computationally efficient interpolated FIR filters
IEEE Transactions on Circuits and Systems
(1988)
Y.C. Lim et al.
Frequency-response masking approach for digital filter design: complexity reduction via masking filter factorization
IEEE Transactions on Circuits and Systems II
(1994)
Y.C. Lim et al.
The optimum design of one- and two-dimensional FIR filters using the frequency response masking technique
IEEE Transactions on Circuits and Systems
(1993)

There are more references available in the full text version of this article.

Cited by (62)

Design and optimisation of regression-type small phase shift FIR filters and FIR-based differentiators with optimal local response in LS-sense
2021, Mechanical Systems and Signal Processing
The design of finite impulse response (FIR) filters and FIR-based differentiators is a popular topic in the field of digital signal processing. FIR filters/differentiators are characterised by a filtering architecture that does not include a feedback loop. Therefore, they are stable and have a relatively simple design, and most importantly, they can yield a filter with a linear phase diagram. Nevertheless, the FIR filter design methods reported in the scientific literature lead to a filter architecture that causes a transport delay or a nonlinear phase shift in the implementation environment. This limits the applicability of FIR filters/differentiators, e.g. in closed-loop control or real-time state estimation. In this paper, a method for FIR filter and FIR-based differentiator coefficient design is presented. The coefficients of the FIR filter and FIR-based differentiator are designed such that the FIR architecture results in a convolution leading to a locally optimal response in the least-squares sense. Thus, the FIR architecture response is characterised by an extremely small phase shift for the passband of the designed architecture. This feature results in a higher-order FIR architecture compared with the conventional design methods. In the proposed method, the delay caused by the FIR architecture is minimised by coefficient determination. Therefore, when the method is applied to a known FIR architecture, it causes a shorter delay than all other methods of coefficient determination.
Non-convex and non-smooth variational decomposition for image restoration
2019, Applied Mathematical Modelling
Citation Excerpt :
It can well remove noises while preserving image edges and contours. We use the iteratively reweighted l1 algorithm (IRL1) [40,41] combined with the alternating direction method of multipliers (ADMM) [42,43] to numerically solve the proposed non-convex model. Compared to the TV regularization and non-convex TV regularization models, the proposed model exhibits superior performance in edge and detail preservation.
The variational image decomposition model decomposes an image into a structural and an oscillatory component by regularization technique and functional minimization. It is an important task in various image processing methods, such as image restoration, image segmentation, and object recognition. In this paper, we propose a non-convex and non-smooth variational decomposition model for image restoration that uses non-convex and non-smooth total variation (TV) to measure the structure component and the negative Sobolev space $H^{- 1}$ to model the oscillatory component. The new model combines the advantages of non-convex regularization and weaker-norm texture modeling, and it can well remove the noises while preserving the valuable edges and contours of the image. The iteratively reweighted l¹ (IRL1) algorithm is employed to solve the proposed non-convex minimization problem. For each subproblem, we use the alternating direction method of multipliers (ADMM) algorithm to solve it. Numerical results validate the effectiveness of the proposed model for both synthetic and real images in terms of peak signal-to-noise ratio (PSNR) and mean structural similarity index (MSSIM).
Nonconvex and nonsmooth total generalized variation model for image restoration
2018, Signal Processing
Citation Excerpt :
New model can preserve image edges well and simultaneously alleviate the staircase effects. In addition, based on the majorization-minimization (MM) scheme [48], two iteratively reweighted algorithms are introduced to numerically solve the proposed model: iteratively reweighted least squares (IRLS) algorithm [49–51] and iteratively reweighted l1 (IRL1) algorithm [52,53], respectively. The main contributions of this paper are summarized as follows: (1) A nonconvex and nonsmooth TGV model is proposed for image restoration. (
In this paper, we propose a nonconvex and nonsmooth total generalized variation (TGV) model for image restoration, which can provide an even sparser representation of the variation of the image function than the traditional TGV model that uses convex l₁ norm to measure the variation. New model combines the advantages of nonconvex regularization and TGV regularization, and can preserve image edges well and simultaneously alleviate the staircase effects often arising in the total variation based models. Two different iteratively reweighed algorithms are introduced to numerically solve the proposed nonconvex and nonsmooth TGV model. Numerical results show that the proposed model is effective in edge-preserving and staircase-reduction in image restoration. In addition, compared with several state-of-the-art variational models, the proposed model has the best performance in terms of PSNR and MSSIM values.
Design of Sparse IIR Filters Based on LASSO
2024, IEEJ Transactions on Electronics, Information and Systems
SPARSE BROADBAND BEAMFORMER DESIGN VIA PROXIMAL OPTIMIZATION TECHNIQUES
2023, Journal of Nonlinear and Variational Analysis
The Binary Beetle Antennae Search Algorithm for Sparse Filter Design
2023, Proceedings - 2023 China Automation Congress, CAC 2023

View all citing articles on Scopus

View full text

Iterative reweighted l1 design of sparse FIR filters

Abstract

Highlights

Introduction

Section snippets

1D FIR filter design

Design of sparse filters

1D case

Conclusions

Acknowledgements

A unified approach to the design of optimum FIR linear phase digital filters

IEEE Transactions on Circuit Theory

An approach to programmable CTD filters using coefficients 0, +1, and −1

IEEE Transactions on Circuits and Systems

A polynomial-time algorithm for designing FIR filters with power-of-two coefficients

IEEE Transactions on Signal Processing

Some efficient digital prefilter structures

IEEE Transactions on Circuits and Systems

On the use of cyclotomic polynomial prefilters for efficient FIR filter design

IEEE Transactions on Signal Processing

Design of computationally efficient interpolated FIR filters

IEEE Transactions on Circuits and Systems

Frequency-response masking approach for digital filter design: complexity reduction via masking filter factorization

IEEE Transactions on Circuits and Systems II

The optimum design of one- and two-dimensional FIR filters using the frequency response masking technique

IEEE Transactions on Circuits and Systems

Iterative reweighted l₁ design of sparse FIR filters