Source-linked AI summary
l_0 Norm Constraint LMS Algorithm for Sparse System Identification
Yuantao Gu, Jian Jin, Shunliang Mei
TL;DR
Sparse system identification is difficult for standard LMS methods because they do not exploit impulse responses dominated by near-zero coefficients. The paper adds an approximated l0 penalty to LMS, creating zero attraction and using partial updating to reduce extra computation. Simulations report accelerated identification of sparse systems, while parameter selection requires balancing convergence speed against steady-state misalignment.
Problem
Standard adaptive algorithms do not exploit sparse systems, whose impulse responses contain many near-zero coefficients and few large ones.
Method
The paper adds an approximated l0 norm penalty to the LMS cost function, creating zero attraction, and applies partial coefficient updating to reduce computational complexity.
Results
The proposed l0-LMS accelerates identification of sparse systems, and l0-NLMS reaches steady state first among the compared algorithms in the reported experiment.
Takeaways & Limitations
Accelerating convergence of near-zero coefficients improves sparse system identification because those coefficients constitute the majority of sparse-system responses.
Takeaways & Limitations
The attraction parameter κ requires a trade-off: larger values increase convergence speed but also increase steady-state misalignment.
Abstract
from arXiv · showhide
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.
1 Introduction
Sparse systems have impulse responses dominated by near-zero coefficients, while standard adaptive algorithms do not exploit this structure. The paper therefore proposes an l0-constrained LMS algorithm to accelerate sparse system identification.
- Sparse systems: Sparse systems contain many near-zero impulse-response coefficients and only a few large ones.They include general sparse and clustering sparse systems, such as acoustic and satellite-link echo paths.
- Existing methods: Traditional LMS and RLS have no particular advantage for sparse identification because they do not use sparse characteristics.Earlier approaches include Adaptive Delay Filters and proportionate updating methods.
- Proposed approach: The proposed l0-constrained LMS integrates a sparsity constraint into the LMS cost function to accelerate near-zero coefficient convergence.The approach is motivated by LASSO and compressive sensing.
- Proposed approach: Partial coefficient updating reduces the additional computational complexity introduced by the l0 norm constraint.The paper reports that simulations show good performance for sparse system identification.
2 New LMS Algorithm
The new algorithm augments LMS with an l0-based sparsity penalty, yielding a zero-attracting update that accelerates small coefficients while partial updating limits added computation. The constraint can also be incorporated into LMS variants such as NLMS.
- Traditional LMS: Traditional LMS minimizes squared estimation error and updates each filter coefficient using the error, input, and adaptation step-size.The filter and input vectors have length L, and μ is the adaptation step-size.
- l0-constrained cost: An l0 penalty counts non-zero coefficients and is added to the LMS cost function to promote sparse solutions.The factor γ balances the sparsity penalty against estimation error, while continuous approximation addresses the NP-hard minimization.
- l0-LMS recursion: The l0-LMS recursion adds a zero-attraction term to the conventional LMS update for every coefficient.The attraction term depends on κ, β, the coefficient sign, and an exponential function of coefficient magnitude.
- Approximation: A first-order Taylor approximation simplifies the exponential attraction term while preserving a positive approximation.The resulting recursion uses f_β(w_i(n)) instead of the exponential expression.
- Complexity reduction: Sequential partial updating lowers l0-LMS implementation cost by refreshing one of Q attraction terms per iteration and reusing previous values.The attraction term changes little during adaptation, motivating this update schedule.
- LMS variants: The l0 norm constraint can also be incorporated into LMS variants such as NLMS.The paper identifies NLMS as potentially attractive because of its robustness.
3 Brief Discussion
The discussion explains how the zero-attraction term accelerates near-zero coefficient convergence and how β and κ govern the algorithm’s behavior. β balances attraction intensity and range, while κ trades adaptation speed against steady-state misalignment.
- Zero attraction: The modified recursion adds zero attraction to the traditional LMS gradient update.This attraction is represented by the additional term in Equation (9).
- Zero attraction: Near-zero coefficients converge faster because attraction is strongest within (−1/β, 1/β) and vanishes outside that range.The paper links this acceleration to improved sparse system identification because near-zero coefficients are the majority.
- Choice of β: A larger β increases attraction intensity but narrows its range, making its effect on convergence difficult to evaluate.The paper uses β = 5 as a practical finite choice, while also mentioning gradual increases during iteration.
- Choice of κ: A larger κ strengthens attraction and speeds convergence but also increases steady-state misalignment.κ is therefore selected according to the trade-off between adaptation speed and adaptation quality.
4 Simulations
Simulations evaluate l0-LMS and l0-NLMS across colored and white signals, parameter settings, and system sparsities. The proposed methods converge faster under sparse-system conditions, with κ trading convergence rate against steady-state misalignment.
- Experimental setup: The simulations use partial updating with Q = 4 for both l0-LMS and l0-NLMS.The experiments also fix β = 5 for the proposed algorithms.
- Colored-signal comparison: The proposed l0-NLMS reaches steady state first among five algorithms and recovers fastest after an abrupt system change.The comparison uses matched steady-state errors and a colored input signal.
- Parameter effects: l0-LMS converges faster than LMS, while larger κ increases convergence rate but also increases steady-state misalignment.The κ experiment uses an eight-nonzero-coefficient system and white Gaussian signal and noise.
- Varying sparsity: As the number of large coefficients increases, l0-LMS convergence slows and gradually approaches standard LMS performance.The sparsity experiment varies the number of large coefficients from 8 to 128 while matching steady-state error across algorithms.
- Varying sparsity: LMS performance is unaffected by the number of large coefficients, whereas l0-LMS performs better for sparser systems.Across the tested sparsities, l0-LMS is reported as never worse than LMS.
5 Conclusion
The conclusion proposes an LMS algorithm with an l0-norm constraint for sparse system identification and reports accelerated identification of sparse systems. It also highlights partial updating for reduced computing complexity and verifies parameter and sparsity effects experimentally.
- 5 Conclusion: The proposed algorithm adds an l0-norm constraint to the LMS cost function to improve sparse system identification.The constraint exploits the sparsity property of the unknown system.
- 5 Conclusion: The added constraint accelerates convergence of near-zero impulse-response coefficients in sparse systems.Partial updating is adopted to reduce computing complexity.
- 5 Conclusion: Simulations verify the effects of algorithm parameters and unknown-system sparsity.The conclusion reports accelerated identification of sparse systems.