Performance Analysis of SOCP and Linear Programming Algorithms for Sparse Filter Design

Performance Analysis of SOCP and Linear Programming Algorithms for Sparse Filter Design

Aswani Mathew

PG Scholar, Dept.of Electronics and Communication Amal Jyothi College of Engineering Kanjirappally,India

P. Darsana

Asst.Prof, Dept.of Electronics and Communication Amal Jyothi College of Engineering Kanjirappally,India

Abstract This paper deals with a novel algorithm – SOCP, which is used to design sparse FIR filters. The focus of the design problem is to reduce the number of non-zero valued filter coefficients. Due to the presence of l0 norm of filter coefficients in objective function, the design problem is highly non-convex. In order to tackle this problem, an iterative procedure is used to obtain sparsity pattern, which is then used to compute final solution in a convex optimization problem. In each iterative step, sparse design problem is changed to sub problems. The optimal solutions of these sub problems can be obtained by solving their dual problems. The design procedure is repeated to improve the sparsity. The performance of proposed algorithm is compared with previous algorithms to find efficient one.

KeywordsSecond order cone programming (SOCP); sparse filters

1. INTRODUCTION

   In the design and analysis of communication systems and signal processing, convex optimization methods are widely used. Convex optimization refers to minimizing a convex objective function subject to convex constraints. Convex optimization has been used in signal processing for long time in the design of linear and non-linear filter designs. It was considered that optimization problems were highly expensive, but these misconceptions are overruled now. The results that justified gave increased computational power.

   The objective of this paper is to reduce the number of non-zero valued filter coefficients. The proposed design is inspired from iterative shrinkage/thresholding [IST] [3] algorithms. In order to obtain a sparse FIR filter design, the number of non-zero filter coefficients is minimized subject to set of error constraints. This main problem is then converted to dual problems to obtain the optimal solutions. In such a sparse filter obtained, the multipliers corresponding to zero valued coefficients can be omitted. This in turn results in reduction of complexity. In general l0 norm of a filter coefficient is considered as a measure of sparsity. This leads to non-convex optimization problems.

   Mixed integer linear programming [MILP] [4] algorithm is proposed that uses cost of arithmetic operations and delays and is formulated as a weighted l0 norm of filter coefficient

   vector. In orthogonal matching pursuit [OMP] [5] algorithm makes use of active indices. This set get expands by one in each iterative step and is used to reduce optimization error.

   This paper also deals with a comparative study of SOCP and Linear programming [LP] [2] algorithm for sparse filter designs. In LP, two methods are being employed. The first method is successive thinning algorithms which turns the impulse response to zero until the given specifications are violated. The second method makes use of l1 norm which is the convex relaxation of l0 norm. In this, two types of approximation algorithms for sparse filter design are used. Both approaches make extensive use of linear programming, and the existence of efficient techniques for solving linear programs contributes significantly to their efficiency. In particular, the presented techniques use linear programming as a significant algorithmic component in determining both the subset of coefficients permitted to be nonzero as well as their values. Ongoing advancements in the execution times of linear program solvers may therefore be used extensively by the presented techniques.

2. PROBLEM FORMULATION

   A. Second Order Cone Programming

   The sparse FIR filter design can be expressed as a convex optimization problem as

   min||h||0 (1)

   s.t |W(wk)[H(ejwk) D(wk)]| (wk), k=1,2.K

   The impulse response h is the objective function which is minimized under the constraints. The constraints is obtained by multiplying a weighting function W(wk) with difference of frequency response of FIR filter and ideal frequency response D(w). (wk) is the upper bound of constraints. The ||.||0 represents l0 norm that gives the idea about number of non- zero valued coefficients

   SOCP problem of the corresponding (1) is given as

   min t (2)

   s.t ||Fkhdk||2 (wk)+t, k=1,2.K

   The sparse filter design equation (1) is first converted to a Euclidean norm, where Fk and dk represents real and

   imaginary parts of impulse response respectively, which is further converted to SOCP problem in (2).

   To obtain a sparsity pattern is the main objective of our design problem. Our algorithm consists of two steps. In first step iteration is used to obtain the sparsity. Then (2) is solved to redefine the result. Our proposed algorithm starts from an initial point h(0).Suppose that in lth iteration, we obtain a feasible point for (1),then a design problem is constructed with same objective function whereas constraints are modified as in (3).

   TABLE I. SPARSITY AND ERROR IN ONE-NORM DESIGN

   Sparsity	Error
   0	0
   20	0.0253
   22	0.0502
   24	0.0752
   26	0.1002
   26	0.1250
   28	0.1501
   28	0.1751
   28	0.2001

   TABLE II. SPARSITY AND ERROR IN MINIMUM INCREASE RULE

   Sparsity	Error
   0	0
   23	0.5010
   23	0.5010
   23	0.5010
   23	0.5010
   23	0.5010
   23	0.5010
   23	0.5010
   23	0.5010
   23	0.5010

   The iterative procedure continues until l0 norm stops decreasing. Our algorithm is inspired from IST and in each iterative step, l0 norm can be decomposed into sub problems.

   In l+1iteration,

   experiments is conducted to confirm that this multistage design strategy can largely improve the sparsity of design results.

3. DESIGN EXAMPLE

   An LPF is designed with an order 32.It is then converted to convex optimization problem where l1 norm is taken to obtain the sparsity. SOCP problem is implemented and compared with linear programming algorithms on the grounds of sparsity and error. The number of zero valued coefficients is displayed in the Tables. We conduct three sets of designs with weighting function varying from0 to 2.The proposed algorithm achieve better results in terms of sparsity. The techniques presented in this work can be extended to design nonlinear-phase FIR filters and IIR filters. Fig.1 shows the output of a LPF performed under the three algorithms mentioned in this paper.The performance analysis of three algorithms shows that SOCP overrules the other two algorithms.Sparsity of SOCP is good enough as per the simulation results.Fig.2 shows the magnitude spectrum of SOCP.The approach retains the overall structure of the algorithms whie modifying optimization problems concerned, namely the minimization of the frequency-domain error with certain coefficients constrained to zero and the minimization of the 1-norm of the coefficients. This approach is likely to be successful for nonlinear-phase FIR filters since the optimization problems remain convex with respect to the coefficients.

   TABLE III. SPARSITY AND ERROR IN SOCP

   Sparsity	Error
   16	2.8280
   18	12.5322
   19	17.1858
   20	18.1961
   20	19.7063
   22	19.7063
   23	19.8920
   26	20.1791
   31	20.4240

   min ||h||0 (3)

   s.t ||hb (l)||

   u (l)

   k 2 k

   b (l) =F T V (l) + h(l)

   k k k

   u (l) 2

   T (l)

4. CONCLUSION

k k k k k

k =[ (wk) v (l) T(c IF F ) v

vk = [dkFkh(l)]/ Ck

] /Ck

Ck is the maximum eigen value of Fk.The optimal solution of (3) can be obtained from

n

h (l+1) =T(*)

n

where T() =bn if (q T )2 1T

=0 if (qnT )2 1T

where is the lagrangean multiplier and qn is the set of all bn. Various parameters of design are compared with linear programming algorithms to check the efficiency.

To achieve a better result, we can run the design algorithm for several times. All stages start from the design output of the previous stage except the first aarep. This procedure continues until the sparsity of the design result cannot be further increased.At the end of each stage the design problem (2) is solved to refine the solution. This operation essentially pushes the final solution obtained in the previous iterative procedure away from the boundary of the feasibility domain.In this way, it is possible to achieve sparser designs in the successive stages. A large number of

In this paper, a new algorithm is proposed for sparse FIR filter designs. The sparsity pattern is obtained by the iterative procedure. In each iterative step, sub-problems are created. By solving its dual problem, optimal solution can be found out. In order to improve the sparsity the iteration can be repeated for several times. Analyses indicate that the proposed algorithm can efficiently and reliably deal with the l0-norm design problem with multiple quadratic constraints.Simulation results also reveal that in many designs,the proposed algorithm outperforms existing design algorithms.Besides sparse FIR filter designs discussed in this paper, the proposed algorithm can be applied to any optimization task which is formulated in the form of (1).

Fig. 1. Comparison of the three design methods

Fig. 2. Magnitude response of the proposed algorithm

REFERENCES

1. Aimin Jiang, Hon Keung Kwan, Yanping Zhu, Peak Error- Constrained Sparse FIR Filter Design Using Iterative SOCP, IEEE Trans.Signal Processing, vol. 60, Aug 2012.

2. T Baran, D Wen,and A V Oppenheim, Linear Programming algorithms for Sparse Filter Design, IEEE Trans.Signal Processing, vol. 58, March 2010.

3. M. Zibulevsky and M. Elad, L1-L2 optimization in signal and image processing, IEEE Signal Process. Mag.,vol. 27,May 2010

4. J. T. Kim, W. J. Oh and Y. H. Lee, Design of nonuniformly spaced Linear-PhasemFIR filters using Mixed Integer Linear Programming,

   IEEE Trans. Signal Process. Vol. 44,Jan 1996

5. D. Mattera, F. Palmieri, and S. Haykin, Efficient Sparse FIR filter design, in Proc. IEEE Int Conf. Acoustic. Speech. Signal Process,. vol. 2.

6. M. S. Lobo, L. Vandenberghe, S. boyd, and H. lebret, Applications of Second-order Cone Programming, Linear Algebra and its Appl., vol. 282, pp. 193-228, nov 1998.

7. T. W. Parks and C. S Burrus, Digital filter Design. New York, Wiley, 1987.

8. S. Boyd and I. Vandenberghe, Convex Optimization, Cambridge, U. K. Cambridge Univ . Press. 2004.

9. W. S. Lu and T. Hinamoto, Digital filters with Sparse Coefficients,in Proc, IEEE. Int. Symp. Circuits Syst. Paris, May 2010, pp.169-172.

10. S. Mallat, A Wavelet tour of Signal Processing:The Sparse way,.,San Diego,CA,2008