유진우
(JinWoo Yoo)
†iD
Copyright © The Korean Institute of Electrical Engineers(KIEE)
Key words
Adaptive Filter, sparse system, affine projection algorithm, L0-norm, filter performance, convergence rate
1. Introduction
Adaptive filters have been used as a general tool for various applications such as
echo cancellation, noise cancellation, and channel estimation (1)-(2). The least-mean-square (LMS) algorithm and normalized least-mean-square (NLMS) algorithm
are the most preferred adaptive filtering algorithms because of their low computational
complexity and ease of implementation. Although LMS and NLMS have practical advantages,
they suffer from the performance degradation when the input signals are correlated.
Therefore, affine projection algorithm (APA) (3) has been proposed to overcome the correlated input signals, and it can actually achieve
a faster convergence rate than LMS and NLMS.
Unfortunately, because the above-mentioned algorithms do not reflect the sparsity
of a system, there is still room to improve the filter performance in terms of convergence
rate in a sparse system scenario. A sparse system means that its impulse response
is composed of mostly near-zero coefficients and very few large coefficients. Therefore,
since all most coefficients are nearly zero, the zero-attracting strategy can be effective
for increasing the performance of adaptive filter in aspects of convergence rate.
To improve the filter performance for identifying a sparse system, several algorithms
have been proposed in recent years (4)-(12). Among them, the concept of L0-norm constraint has been introduced to improve the
convergence rate of a sparse system (4), (10)-(11). Through the fast convergence rate due to the L0-norm constraint of cost function,
the real-time adaptive filter can be accomplished in sparse system identification
such as digital TV transmission channel estimation, acoustic echo cancellation, network
echo cancellation, underwater channel estimation.
This paper proposes an APA based on the L0-norm constraint for sparse system identification.
We suggest a new cost function including the L0-norm constraint to obtain an enhanced
version of APA for a sparse system. The proposed algorithm was experimented in a sparse
system, and its performance was compared with that of the original APA, proportionate
APA (PAPA) (6), and improved proportionate APA (IPAPA) (7).
2. Proposed Algorithm
2.1 Conventional Affine Projection Algorithm
Consider reference data $d_{i}$ obtained from an unknown system
$$d_{i}=\boldsymbol{u}_{i}^{T} \boldsymbol{w}+v_{i}$$
where $\boldsymbol{w}$ is the n-dimensional column vector of the unknown system that
is to be estimated, $v_{i}$ accounts for measurement noise, which has variance $\sigma_{v}^{2}$,
and $\boldsymbol{u}_{i}$ denotes an n-dimensional column input vector, $\boldsymbol{u}_{i}=[u_{i}u_{i-1}\bullet\bullet\bullet
u_{i-n+1}]^{T}$. The update equation of the conventional APA can be summarized as
(3):
$$\hat{\boldsymbol{w}}_{i+1}=\hat{\boldsymbol{w}}_{i}+\mu \boldsymbol{U}_{i}\left(U_{i}^{T}
\boldsymbol{U}_{i}\right)^{-1} \boldsymbol{e}_{i}$$
where $\boldsymbol{e}_{i}=\boldsymbol{d}_{i}-\boldsymbol{U}_{i}^{T} \boldsymbol{\hat{w}}_{i},
\boldsymbol{\hat{w}}_{i}$ is an estimate of $\boldsymbol{w}$ at iteration $i$, $\mu$
is the step-size parameter, $M$ is the projection order defined as the number of the
current input vector used for the update, and
\begin{align*}
\boldsymbol{U}_{i}=[\boldsymbol{u}_{i}\boldsymbol{u}_{i-1}\bullet\bullet\bullet \boldsymbol{u}_{i-M+1}],\:
\\
\boldsymbol{d}_{i}=[d_{i}d_{i-1}\bullet\bullet\bullet d_{i-M+1}]^{T}.
\end{align*}
2.2 Improved Affine Projection Algorithm via L0-norm constraint
The proposed APA is obtained by minimizing the conventional cost that consists of
the a priori error vector and the input data matrix considering the L0-norm constraint
(4), which makes the L0-norm of $\boldsymbol{\hat w}_{i}$ zero, as follow:
where $||\bullet ||_{0}$ denotes the L0-norm that defines the number of nonzero entries.
Even though the L0-norm does not satisfy the norm property mathematically, the L0-norm
definition has widely used in such as compressive sensing, adaptive filter to deal
with sparse system scenarios.
Our proposed cost function is obtained from (1) as
where $\gamma$ is a Lagrange multiplier for controlling the influence of the L0-norm
constraint. The derivative of the proposed cost function (2) with respect to the filter coefficient vector $\boldsymbol{\hat w}_{i}$ is
where $\boldsymbol{f}(\boldsymbol{\hat w}_{i})=[f(\hat w_{i}),\:...,\:f(\hat w_{i}(n-1))]^{T}$.
The representative approximation of the L0-norm is generally expressed as (4), (13):
where the parameter $\beta$ is a positive integer to determine the region of zero
attraction for all entries in $\boldsymbol{\hat w}_{i}$. Using the approximation in
(4), the derivative of $||\boldsymbol{\hat w}_{i}||_{0}$with respect to the filter coefficient
is component-wisely defined as
Generally, the sign function $sgn(\bullet)$ can be written as
Moreover, the first-order Taylor series expansion of the exponential function is adopted
to reduce the computational complexity of (5) as (4), (10):
Substituting (6) and (7) into (5), we can clearly express the function $f(\bullet)$ as
$$f(x)=\begin{cases}
-\beta^{2}x-\beta &,\: -\dfrac{1}{\beta}\le x<0\\
-\beta^{2}x+\beta &,\: 0<x\le\dfrac{1}{\beta}\\
0&,\: otherwise.
\end{cases}$$
Finally, using the gradient descent method, we can obtain a novel update equation
of the filter coefficient vectors derived from our modified cost function (2), as follows:
$$\begin{align*}
\boldsymbol{\hat w}_{i+1}= \boldsymbol{\hat w}_{i}-\mu\nabla_{\boldsymbol{\hat w}_{i}}J(\boldsymbol{\hat
w}_{i})\\
= \boldsymbol{\hat w}_{i}+\mu(\boldsymbol{U}_{i}(\boldsymbol{U}_{i}^{T}\boldsymbol{U}_{i})^{-1}\boldsymbol{e}_{i}-\gamma
\boldsymbol{f}(\boldsymbol{\hat w}_{i}))
\end{align*}$$
where the parameter $\mu$ is a step size.
3. Experimental Result
We experimented to demonstrate the performance of the proposed APA for system identification
scenario via computer simulation. An target-system coefficients with 128 taps (n =
128) was generated randomly, the adaptive filter and the unknown channel had the same
number of taps. In addition, we set 120 near-zero filter coefficients among the 128
taps to create a general sparse system. All the adaptive filters in our simulation
were tested with projection order M = 2, where projection order means the number of
input vectors. The correlated input signals were generated by filtering white Gaussian
noise through a first-order system as
$$G_{1}(z)=\dfrac{1}{1-0.9z^{-1}},\: G_{2}(z)=\dfrac{1+0.05z^{-1}}{1+z^{-1}+0.05z^{-2}}$$.
Fig. 1. NMSD learning curves for colored input generated by $G_{1}(z)$
Fig. 2. NMSD learning curves for colored input generated by $G_{2}(z)$
The measurement noise $v_{i}$ is added to $y_{i}$ with a signal-to-noise ratio (SNR)
of 30dB, where the SNR is defined by $10\log_{10}(E[y_{i}^{2}]/E[v_{i}^{2}])$ and
$y_{i}= \boldsymbol{u}_{i}^{T}\boldsymbol{w}$. The normalized mean squared deviation
(NMSD) is defined as $10\log_{10}(E[\boldsymbol{\widetilde w}^{T}\boldsymbol{\widetilde
w}]/(\boldsymbol{w}^{T}\boldsymbol{w}))$ with the filter-error vector $\boldsymbol{\widetilde
w}_{i}= \boldsymbol{w} - \boldsymbol{\hat w}_{i}$. Through ensemble averaging over
50 trials, the experiment results were obtained.
Figs. 1 and 2 show the NMSD learning curves for the original APA, PAPA (6), IPAPA (7), and the proposed algorithm with correlated input signals $G_{1}(z)$ and $G_{2}(z)$.
As we aim to compare only the convergence rate of the proposed algorithm with that
of the other algorithms, the parameters of each algorithm are chosen such that their
steady-state errors are the same. The parameters used for our experiments are as follows:
APA($\mu =0.09$), PAPA($\mu =0.08,\:\delta_{\rho}=0.01,\:\rho =0.01$), IPAPA($\mu
=0.09,\:\alpha =0,\:\epsilon =0.01$), the proposed algorithm($\mu =0.45,\:\beta =20,\:\gamma
=1.8\times 10^{-5}$). In particular, $\delta_{\rho},\:\rho$ of PAPA and $\alpha ,\:\epsilon$
of IPAPA are set as recommended by the reference journals. As shown in Figure. 1 and Figure. 2, the proposed APA accomplishes a faster convergence rate than the original APA, PAPA,
and IPAPA.
4. Conclusion
This paper proposed an affine projection algorithm based on the L0-norm constraint
for sparse system identification. The introduction of the L0-norm constraint in APA
is helpful to hasten the convergence of the near-zero filter coefficients. By devising
a modified cost function that includes the L0-norm constraint, the proposed APA attains
a faster convergence rate, as compared to the original APA, PAPA, and IPAPA. Moreover,
experimental results have been verified via computer simulation fairly.
Acknowledgements
This work was supported by the National Research Foundation of Korea(NRF) grant funded
by the Korea government(MSIT) (No. 2019R1G1A1100532).
References
S. Haykin, 2002, Adaptive Filter Theory, NJ:Prentice-Hall
B. Chen, Y. Zhu, J. C. Principe, 2011, A Variable Step-Size SIG Algorithm for Realizing
the Optimal Adaptive FIR Filter, International Journal of Control, Automation, and
Systems, Vol. 9, No. 6, pp. 1049-1055
K. Ozeki, T. Umeda, 1984, An adaptive filtering algorithm using an orthogonal projection
to an affine subspace and its properties, Electronics and Communication in Japan,
Vol. 67, No. 5, pp. 19-27
J. Jin, S. Mei, 2009, l0 Norm Constraint LMS Algorithm for Sparse System Identification,
IEEE Signal Processing Letters, Vol. 16, No. 9, pp. 747-777
Y. Wang, P. Zhang, M. Wu, J. Yang, 2012, Variable regulari- sation efficient -law
improved proportionate affine projection algorithm for sparse system identification,
Electronics Letters, Vol. 48, No. 3, pp. 182-184
L. Liu, M. Fukumoto, S. Zhang, 2009, A variable step-size proportionate affine projection
algorithm for network echo cancellation, Digital Signal Processing, 2009 16th Inter-
national Conference on, pp. 1-6
K. Sakhnov, 2008, An improved proportionate affine projection algorithm for network
echo cancellation, Systems, Signals and Image Processing, IWSSIP 2008. 15th International
Conference on, pp. 125-128
D. Donoho, 2006, Compressive sensing, IEEE Transactions on Information Theory, Vol.
52, No. 4, pp. 1289-1306
P. Naylor, J. Cui, M. Brookes, 2006, Adaptive algorithms for sparse echo cancellation,
Signal Processing, Vol. 86, No. 6, pp. 1182-1192
J. Yoo, J. Shin, H. Choi, P. Park, 2012, Improved affine projection sign algorithm
for sparse system identification, IET Electronics Letters, Vol. 48, No. 15, pp. 927-929
Y. Yu, H. Zhao, B. Chen, 2016, Sparse normalized subband adaptive filter algorithm
with l0-norm constraint, Journal of Franklin Institue, Vol. 353, No. 18, pp. 5121-5136
S. Jiang, Y. Gu, 2015, Block-Sparsity-Induced Adaptive Filter for Multi-Clustering
System Identification, IEEE Tran- sactions on Signal Processing, Vol. 63, No. 20,
pp. 5318-5330
P. Bradley, O. Mangasarian, 1998, Feature selection via concave minimization and support
vector machines, Proceedings of the 15th ICML, pp. 82-90
저자소개
JinWoo Yoo received his BS, MS, Ph.D. in electrical engineering from Pohang University
of Science and Technology (POSTECH) in 2009, 2011, 2015, respectively.
He was a senior engineer at Samsung Electronics from 2015 to 2019.
He is currently an assistant professor in the department of automotive engineering
at Kookmin University.
His current research interests are signal/image processing and autonomous driving.