 Open Access
 Total Downloads : 232
 Authors : Aswani Mathew, P. Darsana
 Paper ID : IJERTV3IS080849
 Volume & Issue : Volume 03, Issue 08 (August 2014)
 Published (First Online): 28082014
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
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 nonzero valued filter coefficients. Due to the presence of l0 norm of filter coefficients in objective function, the design problem is highly nonconvex. 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

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 nonlinear 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 nonzero 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 nonzero 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 nonconvex 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.

PROBLEM FORMULATION
A. Second Order Cone Programming
The sparse FIR filter design can be expressed as a convex optimization problem as
minh0 (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 Fkhdk2 (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 ONENORM 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.

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 nonlinearphase 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 frequencydomain error with certain coefficients constrained to zero and the minimization of the 1norm of the coefficients. This approach is likely to be successful for nonlinearphase 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 h0 (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)

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, subproblems 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 l0norm 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

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.

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

M. Zibulevsky and M. Elad, L1L2 optimization in signal and image processing, IEEE Signal Process. Mag.,vol. 27,May 2010

J. T. Kim, W. J. Oh and Y. H. Lee, Design of nonuniformly spaced LinearPhasemFIR filters using Mixed Integer Linear Programming,
IEEE Trans. Signal Process. Vol. 44,Jan 1996

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

M. S. Lobo, L. Vandenberghe, S. boyd, and H. lebret, Applications of Secondorder Cone Programming, Linear Algebra and its Appl., vol. 282, pp. 193228, nov 1998.

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

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

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

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