In order to improve the performance of least mean square (LMS)-based adaptive filtering for identifying block-sparse systems, a new adaptive algorithm called block-sparse LMS (BS-LMS) is proposed in this paper. The basis of the proposed algorithm is to insert a penalty of block-sparsity, which is a mixed @math norm of adaptive tap-weights with equal group partition sizes, into the cost function of traditional LMS algorithm. To describe a block-sparse system response, we first propose a Markov-Gaussian model, which can generate a kind of system responses of arbitrary average sparsity and arbitrary average block length using given parameters. Then we present theoretical expressions of the steady-state misadjustment and transient convergence behavior of BS-LMS with an appropriate group partition size for white Gaussian input data. Based on the above results, we theoretically demonstrate that BS-LMS has much better convergence behavior than @math -LMS with the same small level of misadjustment. Finally, numerical experiments verify that all of the theoretical analysis agrees well with simulation results in a large range of parameters.
The identification of an unknown system with sparse impulse response could be accelerated and enhanced by introducing a sparsity constraint into the cost function of LMS, where the sparsity constraint could be approximated @math norm @cite_19 , @math norm @cite_36 , reweighted @math norm @cite_36 @cite_16 , smoothed @math norm @cite_4 @cite_30 , @math norm @cite_21 @cite_37 , or a convex sparsity penalty @cite_26 . However, literature on adaptive filtering algorithms benefiting from block-sparsity is scarce. Thus, it is important to further improve the performance by utilizing block structure. Among the above algorithms, @math -LMS @cite_19 demonstrates rather good performance in experiments and has comprehensive theoretical guarantee @cite_7 . Therefore, in this work we generalize @math -LMS to BS-LMS by utilizing block-sparsity. Part of our derivations (mainly in Section ) are based on the approach in @cite_7 . However, the main contribution of this paper, including BS-LMS algorithm Section ), the Markov-Gaussian block-sparse model (Section ), and superior performance analysis (Section ), are brand-new compared to the above references.
@cite_30 @cite_37 @cite_26 @cite_4 @cite_7 @cite_36 @cite_21 @cite_19 @cite_16
2128007683 2293909378 2098674248 2146725538
It has been known for a while that l1-norm relaxation can in certain cases solve an under-determined system of linear equations. Recently, E. Candes ("Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information," IEEE Trans. Information Theory, vol. 52, no. 12, pp. 489-509, Dec. 2006) and D. Donoho ("High-dimensional centrally symmetric polytopes with neighborlines proportional to dimension," Disc. Comput. Geometry, vol. 35, no. 4, pp. 617-652, 2006) proved (in a large dimensional and statistical context) that if the number of equations (measurements in the compressed sensing terminology) in the system is proportional to the length of the unknown vector then there is a sparsity (number of nonzero elements of the unknown vector) also proportional to the length of the unknown vector such that l1-norm relaxation succeeds in solving the system. In this paper, in a large dimensional and statistical context, we determine sharp lower bounds on the values of allowable sparsity for any given number (proportional to the length of the unknown vector) of equations for the case of the so-called block-sparse unknown vectors considered in "On the reconstruction of block-sparse signals with an optimal number of measurements," (M. , IEEE Trans, Signal Processing, submitted for publication. In order to improve the performance of least mean square (LMS) based system identification of sparse systems, a new adaptive algorithm is proposed which utilizes the sparsity property of such systems. A general approximating approach on l 0 norm-a typical metric of system sparsity, is proposed and integrated into the cost function of the LMS algorithm. This integration is equivalent to add a zero attractor in the iterations, by which the convergence rate of small coefficients, that dominate the sparse system, can be effectively improved. Moreover, using partial updating method, the computational complexity is reduced. The simulations demonstrate that the proposed algorithm can effectively improve the performance of LMS-based identification algorithms on sparse system. We propose a new approach to adaptive system identification when the system model is sparse. The approach applies l 1 relaxation, common in compressive sensing, to improve the performance of LMS-type adaptive methods. This results in two new algorithms, the zero-attracting LMS (ZA-LMS) and the reweighted zero-attracting LMS (RZA-LMS). The ZA-LMS is derived via combining a l 1 norm penalty on the coefficients into the quadratic LMS cost function, which generates a zero attractor in the LMS iteration. The zero attractor promotes sparsity in taps during the filtering process, and therefore accelerates convergence when identifying sparse systems. We prove that the ZA-LMS can achieve lower mean square error than the standard LMS. To further improve the filtering performance, the RZA-LMS is developed using a reweighted zero attractor. The performance of the RZA-LMS is superior to that of the ZA-LMS numerically. Experiments demonstrate the advantages of the proposed filters in both convergence rate and steady-state behavior under sparsity assumptions on the true coefficient vector. The RZA-LMS is also shown to be robust when the number of non-zero taps increases. As one of the recently proposed algorithms for sparse system identification, I0 norm constraint Least Mean Square (io-LMS) algorithm modifies the cost function of the traditional method with a penalty of tap-weight sparsity. The performance of I0-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 I0-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 I0-LMS and some previous arts and the sufficient conditions for I0-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.