Performance Analysis of $l_0$ Norm Constraint Least Mean Square Algorithm

Abstract

As one of the recently proposed algorithms for sparse system identification, <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$l_0$</tex></formula> norm constraint Least Mean Square ( <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$l_0$</tex> </formula> -LMS) algorithm modifies the cost function of the traditional method with a penalty of tap-weight sparsity. The performance of <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex Notation="TeX">$l_0$</tex></formula> -LMS is quite attractive compared with its various precursors. However, there has been no detailed study of its performance. This paper presents comprehensive theoretical performance analysis of <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$l_0$</tex> </formula> -LMS for white Gaussian input data based on some reasonable assumptions, which are reasonable in a large range of parameter setting. Expressions for steady-state mean square deviation (MSD) are derived and discussed with respect to algorithm parameters and system sparsity. The parameter selection rule is established for achieving the best performance. Approximated with Taylor series, the instantaneous behavior is also derived. In addition, the relationship between <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$l_0$</tex></formula> -LMS and some previous arts and the sufficient conditions for <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex Notation="TeX">$l_0$</tex></formula> -LMS to accelerate convergence are set up. Finally, all of the theoretical results are compared with simulations and are shown to agree well in a wide range of parameters.