applied here guarantees the convergence to the optimum under the
aforesaid condition on μ, on account of the convexity of the loss
function.
Considering a very common case that the weight vector w is sparse
with the majority of its elements exactly or nearly zeros, many sparsityaware variants of the classical LMS algorithm have been proposed to
improve the performance by employing the prior sparse information.
For instance, the L0-LMS, L1-LMS and Lp-LMS introduce the L0, L1 and
Lp norms of weight vector w, respectively, into the loss function of
classical LMS algorithm. For the Lp-LMS, the corresponding loss
function is
J k , p  ek2 / 2   p w k p
(4)

Variable p norm constrained LMS
algorithm based on gradient of root
relative deviation
Yong Feng✉, Fei Chen and Jiasong Wu
A new Lp-norm constraint least mean square (Lp-LMS) algorithm with
new strategy of varying p is presented, which is applied to system
identification in this letter. The parameter p is iteratively adjusted by the
gradient method applied to the root relative deviation of the estimated
weight vector. Numerical simulations show that this new algorithm
achieves lower steady-state error as well as equally fast convergence
compared with the traditional Lp-LMS and LMS algorithms in the
application setting of sparse system identification in the presence of
noise.

where w k

p





N
i 1

| wk ,i | p



1/ p

defines the Lp norm (0 < p < 1) , with a

constant factor γp weighing the penalty term and determined by the
trade-off between the misadjustment and convergence rate. Accordingly,
the update is then revised as

Introduction: Recent years have brought up an avalanche of interest in
sparse adaptive filtering in a variety of applications, such as sparse
channel estimation and system identification, and such a tilde is mainly
stimulated by the study of the least absolutely shrinkage and selection
operator (LASSO) and compressed sensing (CS). Among these methods,
the least mean square (LMS) algorithm is probably the most notable and
extensively used on the account of its computational simplicity and ease
of implementation. Moreover, the family of norm constrained LMS
algorithms have attracted much attention and are able to gain better
performances than the traditional LMS approach and greater robustness
against additive noise in identifying a sparse system [1-4].
So many norm constrained LMS algorithms have been released to
better the performance of the classical LMS algorithm, such as the L0norm penalty LMS (L0-LMS) [1], L1-norm constrained LMS (L1-LMS)
[2], Lp norm LMS (Lp-LMS) [3] and Lp norm-like LMS (Lpl-LMS) [4].
Different corresponding norm constraints are integrated to the loss
function of the classical LMS in the aforementioned new methods in
order to accelerate the convergence and / or lower the steady state mean
square error (MSE). However, most of these existing algorithms as well
as their variants have the difficulty of adaptability to the sparsity of the
unknown systems to be estimated, due to the lack of any adjustable
factors [4].
In this letter, we derive a new Lp-LMS algorithm with a varying p to
address the aforementioned concern, which is achieved by iteratively
adjusting p with a gradient method applied to the root relative deviation
of the estimated weight vector. Hence it results in a better Lp-norm
penalty for the proposed Lp-LMS algorithm. Moreover, the numerical
simulation results show that the proposed algorithm has lower MSE
than the classical LMS and Lp-LMS algorithms.

w k 1  w k   ek x k   p

wk

1 p
p

sgn(w k )

 p  | w k |1 p

(5)

where ρp = μγp, εp is a constant imposed to bound the corresponding
term in the situation when any component of wk approaches zero. The
sign function sgn(x) is defined conventionally, i.e., 1 for x  0 , 0 for
x  0 and -1 for x  0 , and sgn(wk) applies to each element of wk,
respectively. Note that the convergence and consistency analysis of the
Lp-LMS still remains problematic owing to the non-convexity of its loss
function [5].
Variable Lp-LMS Algorithms: As demonstrated by its proposer Taheri
[3], The Lp-LMS algorithm can achieve higher performance than the
classical LMS, better than or at least comparable to the L1-LMS, L0LMS and Lpl-LMS algorithms. However, it suffers the difficulty of
adapting to the sparsity of the systems, due to the lack of related
adjustable factors. To address this problem, we have developed a new
Lp-LMS algorithm with a variable p, termed as the Lvp(GSE)-LMS [6],
which is achieved by iteratively adjusting p along the opposite direction
of the gradient of the instantaneous square error with respect to p,
leading to an optimal value of p for the Lp-LMS and thus a better
performance. Since the computational complexity of this approach
might be a little high and inspired by the recent research of Lp recovery
with affine scaling transformations in compressed sensing [7], we will
derive some alternative methods to automatically adjust the value of p
of the Lp-LMS in the following.
Intuitively, the idea of linearly varying the value of p comes to our
sight firstly and simply, i.e.,
pk 1  max{ pk  s,0}
(6)
where p0 is set to be 1 and the step size s is a very small positive
constant, i.e., this method initializes p with the value 1 and then
decreases it with a fixed step size s. If p reaches 0 before the steady
state of convergence, the rest iterations take a fixed p = 0 (but we often
use a small value like 0.01 instead of zero in simulations).
However, the aforementioned linear variation of p is independent of
the iterative algorithm, leading to an improved version that associates
the variable p with the convergence preliminarily. Let the deviation
Dk  w k  w k 1 2 representing the L2 norm of the difference between

Conventional Lp-LMS Algorithm: Let yk stand for the output of a finite
impulse response system which has an additive noise nk at time k,
represented as
yk  wT x k  nk
(1)
where w is the weight vector of length N and the impulse response of an
unknown system, and (·)T denotes the transpose operator. xk represents
the stationary input vector with zero mean and autocorrelation matrix R,
which consists of the last N input signal samples, i.e.,
x k  [ xk , xk 1 ,, xk  N 1 ]T . nk is a white noise process with variance  k2 .
Providing an xk and yk following the above linear system settings, the
problem is how to find the weight vector w.
The loss function Jk in the traditional LMS algorithm is regulated as
J k  ek2 / 2
(2)
where ek represents the instantaneous error between the desired
ek  yk  wTk x k
response
and
output,
i.e.,
,
where

the estimated weight at current iteration wk and its previous one wk-1,
then we define the relative deviation RDk  Dk / w k 2 and root RD
rRDk  RDk . The improved p-variation might be
pk 1  min rRDk ,1
(7)
where the value of rRDk diminishes and approaches zero at the end of
the convergence. If the deviation is lower than a user-defined threshold
ε, we will stop the iteration of p.
However, the second method doesn't work well since the final value
of p is close to 0 which is empirically not the optimal one. It is well
known that the LMS algorithm searches the weight vector along the
opposite of the gradient of loss function and moves on iteratively with a
small step size. Following the similar idea of gradient method, we might
vary p as follows
pk 1  pk  rRDk / rRDk
(8)

w k  [ wk ,1 , wk ,2 ,..., wk ,N ]T denotes the weight vector of the filter to be
estimated at time k. With the gradient descent method, the update of
classical LMS is then derived as follows
J
w k 1  w k   k  w k   ek x k
(3)
w k
1
where the step size μ satisfies 0    max and max denotes the
maximum eigenvalue of the above R. The gradient descent method

where the difference rRDk  rRDk  rRDk 1 denotes the gradient of
rRDk weighted by a positive constant δ. This method, termed as LvpGrRD-

1

LMS, adjusts p based on the change in rRDk and is expected to work
effectively with a feedback mechanism.
Additionally, we notice that the above algorithm converges fast as
well as keeps stable if the parameter δ varies from a larger initial value
to a smaller stable value during the iterations. Hence, a simple scheme
of a variable δ might be given by
 k 1   k  u
(9)
where the step size u is a small positive constant. Moreover, this method
might be employ in the Lpl-LMS as well to improve its performance.

Jiasong Wu (School of Computer Science and Engineering, Southeast
University, Nanjing 210096, China)

a

Simulation results: In order to verify the performance of the proposed
LvpGrRD-LMS, numerical simulations are implemented in this section in
the light of the convergence rate and steady-state mean square deviation

a

a

c

2
(MSD, MSD k  E || w  w k ||2  ). Set in the application of sparse
system identification, its performances are compared with those of the
classical LMS and Lp-LMS algorithms in different sparsity levels.
The sparse system to be estimated has 16 taps, whose 1, 4, 8 or 16
tap(s) are established to be non zeros, setting the sparsity ratio (SR) as
1/16, 4/16, 8/16 and 16/16, respectively. The positions of the nonzero
taps are chosen randomly with their values setting to be 1 or -1
randomly as well. The noise signal and input signal employed are both
assumed to be white Gaussian processes of a fixed length 500 with
variances 1 and 0.01 (or 0.001), respectively, leaving the signal-to-noise
ratio (SNR) 20 dB or 30 dB. For the sake of concisely presentation, SR
= 1/16 is set for the 1~500th iteration, SR = 4/16 for the following 500
ones, and lastly SR = 8/16 for the left 500 iterations. Listed in Table 1
are all the left parameters that are discreetly and fairly selected. All the
simulation results are averaged for 200 times. Note that the value of p
varies from the 10th to the 200th iterations with different parameter δ's
under different SRs in the experiment.

Fig. 1 MSD curves of the three tested approaches with SNR = 20 dB
and SR = 1/16, 4/16 or 8/16, respectively.

b
a,c

Fig. 2 The iterations of p in the setting of a totally non-sparse system
(SR = 16 /16, SNR = 30dB).

Table 1. Residual parameters of different approaches in this simulations.
Approaches
μ
ε
ρ
p
δ
LMS
/
/
/
/
Lp-LMS
0.5
/
0.05
0.05
5×10-5
LvpGrRD-LMS
p0=1
0.02*
* Different δ = 0.02, 0.02, 0.01 and 0.005 are intended for SR
= 1/16, 4/16, 8/16 and 16/16, separately.

Fig. 3 The iterations of p under different SRs (corresponding to Fig.1).

Fig. 1 presents three MSD curves of the tested algorithms with
horizontal axis the number of iterations at different sparsity levels, viz.
SR = 1/16, 4/16 and 8/16. As can be seen from Fig.1, the LvpGrRD-LMS
generally yields significantly lower steady-state error than both the
classical LMS and Lp-LMS do with different sparsity ratios, due to the
adjustment of the value of p. Specifically, the stable MSD of LvpGrRDLMS is much higher than the Lp-LMS in the very sparse case, i.e., SR =
1/16, and they both outperform the classical LMS with the help of
sparse penalty, i.e., the Lp norm constraint; When SR increases, the
proposed LvpGrRD-LMS algorithm still achieves lower stable error than
the Lp-LMS and classical LMS, except in case that the system is totally
non-sparse (SR = 16/16, see Fig. 2) when the LvpGrRD-LMS performs
very close to the classical LMS, way better than the Lp-LMS that
deteriorates in non-sparse cases as expected. Correspondingly, the
iteration of the varying p is presented in Fig. 3, showing that p
iteratively converges from the initial value p = 1 for all different SRs
except the last non-sparse one.

References
1. Gu, Y.T., Jin J. and Mei, S.L.: ‘L0 Norm Constraint LMS Algorithm
for Sparse System Identification’, IEEE Signal Process. Lett., 2009, 16,
(9), pp. 774-777, doi: 10.1109/LSP.2009.2024736
2. Chen, Y., Gu Y. and Hero, A.O.: ‘Sparse LMS for system
identification’, 34th IEEE Conf. on Acoust., Speech and Signal Process.
(ICASSP), Taipei, Taiwan, April 2009, pp. 3125-3128, doi:
10.1109/ICASSP.2009.4960286
3. Taheri, O. and Vorobyov, S.A.: ‘Sparse channel estimation with Lpnorm and reweighted L1-norm penalized least mean squares’, 36th
IEEE Conf. on Acoust., Speech and Signal Process. (ICASSP), Prague,
Czech Republic, May 2011, pp. 2864 - 2867, doi:
10.1109/ICASSP.2011.5947082
4. Wu, F.Y. and Tong, F.: ‘Gradient optimization p-norm-like
constraint LMS algorithm for sparse system estimation’, Signal
Process., 2013. 93, (4): pp. 967-971, doi: 10.1016/j.sigpro.2012.10.008
5. Aliyu, M.L., Alkassim, M.A. and Salman, M.S.: ‘A p-norm variable
step-size LMS algorithm for sparse system identification’, Signal,
Image and Video Process., 2013: pp. 1-7, doi: 10.1007/s11760-0130610-7
6. Feng, Y., et al.: ‘Error Gradient-based Variable-Lp norm Constraint
LMS Algorithm for Sparse System Identification’, arXiv: 1509.07951,
2015
7. Dominguez, R.J., et al.: ‘Reconstruction in Compressive Sensing
Using Affine Scaling Transformations with Variable-p Diversity
Measure’, 13th IEEE Digital Signal Process. Workshop and 5th IEEE
Signal Process. Educ. Workshop (DSP/SPE), Marco Island, FL, Jan.
2009, pp. 708-713, doi: 10.1109/DSP.2009.4786014

Conclusion: In order to further improve the performance of the system
identification with the popular Lp-LMS algorithm, the LvpGrRD-LMS
approach was proposed as a supplement of the former where the
variable parameter p was iteratively adapted to the gradient of root
relative deviation of the estimate weight vector. Numerical simulations
showed that this proposed algorithm achieves lower steady-state error
and equally high rate of convergence than the traditional Lp-LMS and
classical LMS algorithm.
Acknowledgments: This work was supported by the NSFC (grants
61571213 and 61201344).
Yong Feng and Fei Chen (Department of Electrical and Electronic
Engineering, South University of Science and Technology of China,
Shenzhen 518055, China)
✉ E-mail: fengy@sustc.edu.cn

2

