A fast converging partial update LMS algorithm with random combining strategy

Partial update (PU) techniques efficiently reduce computational complexity, especially for long-tap applications such as echo cancelation problems. However, periodic signals are known to induce instability for many PU algorithms, but not the stochastic PU (SPU) algorithm. For a small enough step-size, the SPU algorithm guarantees stability. However, it suffers a slow convergence speed. This paper proposes a non-uniformly distributed SPU (NSPU) least-mean-square (LMS) algorithm, which updates the taps in a non-uniform fashion such that a bigger tap gains a higher updating probability. This can be accomplished by randomly combining a "data independent" (SPU) with a "data dependent" (maximum partial output) PU criteria. Our approach not only preserves the stability of the SPU LMS algorithm but also enhances the convergence speed with a lower hardware cost. Simulation results show that our NSPU LMS algorithm demonstrates significant improvements when only one-sixteenths of total taps are updated at each iteration.