In recent years, sparse signal estimation has become an important paradigm in the field of
signal processing due to its vast amount of applications. Among the wide range of
applications, system identification and echo cancelation are likely two of the most
challenging signal estimation problems for many practical channels with sparse nature.
For such channels, due to low convergence speed and sensitivity to highly correlated
inputs, conventional adaptive filtering algorithms such as least-mean-square (LMS)
algorithm and its variants, recursive least-squares (RLS)algorithm and Kalman filters are
incapable of exploiting the channel sparsity efficiently. To overcome the difficulties
associated with sparse system identification and echo cancelation, l0-norm constraint
LMS (l0-LMS) modifies the conventional LMS algorithm to capture and utilize the
sparsity of the channel . This modification results in a zero-point attraction to all
filter-taps. The l0-norm addition, however, causes the optimization problem to be
non-convex and hence not tractable.
In this thesis, we propose three different types of novel sparse adaptive filtering
algorithms to achieve faster convergence rate while decreasing the mean-square deviation
(MSD). Furthermore, all the novel approaches are transformed into convex optimization
problem by imposing either l1-norm or logarithmic penalty on the filter-tap during the
adaptation process. The first algorithm is referred as weighted zero-attracting leaky LMS
(WZA-LLMS) algorithm where the original cost function of the leaky-LMS algorithm is
modified by an addition of a log-sum penalty that produces an adjustment term in the
update equation. The adjustment causes the proposed algorithm to attract the zeros of
sparse channel and improves the performance. For system identification and echo
cancelation setting, the proposed algorithm not only yields lower MSD for highly sparse
channels but converges at the same rate as the standard zero-attracting-LMS (ZA-LMS)
algorithm. In the case of fully non-sparse channels, the WZA-LLMS algorithm performs
better than both the LLMS and ZA-LMS algorithms in the same settings. These filters can
also be efficiently implemented for potential application such as in finite-precision
hardware.
Due to an extra logarithmic cost function, however, the WZA-LLMS algorithm is
computationally complex. To reduce the complexity while achieving lower MSD, a zero
attractor-variable step-size LMS (ZA-VSSLMS) algorithm is introduced. This algorithm
imposes an l1-norm penalty to the original quadratic cost function of the VSSLMS
algorithm which captures the system sparsity during adaptation process. For highly sparse
channel, this process accelerates the final convergence and improves the error
performance. The convergence analysis for ZA-VSSLMS algorithm is studied when the
white process presents at the input of the system. The stability condition of the algorithm
is presented. Next, the steady-state mean square deviation (MSD) analysis of the
algorithm is carried out. A steady-state MSD expression for the ZA-VSSLMS algorithm
is derived mathematically in terms of the system parameters for general white noise
process.A crucial upper bound of the zero-attractor controller (ρ) which yields minimum
MSD is theoretically shown. The effect of both zero-attractor controller (ρ) and the
forgetting factor (α) in ZA-VSSLMS are investigated. Furthermore, the behavior of the
ZA-VSSLMS algorithm is studied in the presence of noise with different probability
density functions.
Finally, to further improve the ZA-VSSLMS filter when the sparsity of the channel
decreases, with a slight cost in the number of computations, the WZA-VSSLMS
algorithm is introduced by adding the same log-sum penalty as in WZA-LLMS algorithm
into original cost function of VSSLMS algorithm.
The performance of the ZA-VSSLMS, WZA-VSSLMS and WZA-LLMS algorithms are
examined with respect to the standard ZA-LMS, VSSLMS, leaky-LMS, set-member- ship
normalized LMS (SM-NLMS) and LMS algorithms in system identification, echo
cancelation and image deconvolution problems. Simulation results show that the
theoretical and simulation results of the ZA-VSSLMS algorithm not only outperforms the
aforementioned algorithms but further are in good agreement with a wide range of
parameters, different channels, input signal and noise types.
Keywords: Adaptive Filters, Sparse Signal, Compressive Sensing, LMS Algorithm, Zero
Attractor.
OZ: Son yıllarda, ayrık sinyal kestirimi, genis¸ uygulama olanakları sundu˘gu ic¸in, sinyal
is¸lemede ¨onemli bir aras¸tırma alanı olarak ortaya c¸ıkmıs¸tır. Uygulama alanları arasında,
ayrık yapıya sahip gerc¸ek kanallar ic¸in sistem tanılama ve yankı giderme en ¨onemlileridir.
Bu t¨ur kanallar ic¸in, LMS, RLS ve Kalman benzeri geleneksel uyarlanır filtre
algoritmaları, ayrık yapıya sahip ¨ozellikleri kullanamamakta ve yavas¸ yakınsama ve
ilintili g¨ur¨ult¨ude d¨us¸ ¨uk bas¸arım sa˘glama gibi sorunlara yol ac¸maktadırlar. Ayrık yapıyı
kullanabilmek ic¸in l0-norm kısıtı eklenerek LMS algoritması g¨uncellenmektedir. Bu
de˘gis¸iklik, filtre katsayılarının sıfıra do˘gru yaklas¸malarını sa˘glamaktadır. Bununla beraber,
l0-norm kısıtının eklenmesi, eniyiles¸tirme problemini dıs¸b¨ukey olmaktan c¸ıkarmakta ve
c¸ ¨oz¨um¨un¨u zorlas¸tırmaktadır.
Bu tezde, daha hızlı yakınsama ve ortalama karesel sapmayı (MSD) azaltan ¨uc¸ ¨ozg¨un
ayrık uyarlanır filtre ¨onerilmis¸tir. Bunlara ek olarak, dıs¸b¨ukey olmayan eniyiles¸tirme
problemleri, filtrede l1-norm kısıtı kullanılarak uyarlama adımları sırasında dıs¸b¨ukey hale
d¨on¨us¸t¨ur¨ulm¨us¸t¨ur. ¨Onerilen birinci algoritma, a˘gırlıklı sıfıra yaklas¸an kac¸aklı LMS
algoritması, WZA-LLMS, olarak adlandırılmıs¸ ve logaritmik toplama dayalı bir ek kısım
eklenerek maliyet is¸levi g¨uncellenmis¸tir. Kanalın yapısında bulunan sıfır katsayılarına
daha hızlı yaklas¸ılarak bas¸arım artırılmaktadır. Sistem tanılama ve yankı giderme
uygulamalarında, ayrık kanallar ic¸in daha d¨us¸ ¨uk MSD elde edilmekte, yakınsama hızı ise
standard sıfıra yaklas¸an LMS algoritmasına (ZA-LMS) ile benzer olmaktadır. Ayrık
olmayan kanallar ic¸in de, WZA-LLMS LLMS ve ZA-LMS algoritmalarından daha
y¨uksek bas¸arım g¨ostermektedir. ¨Onerilen filtreler gerc¸ek donanımlarda etkin
algoritmaların uygulamasında da kullanılabilmektedir.
Eklenen logaritmik maliyet is¸levi nedeniyle WZA-LLMS algoritması, y¨uksek is¸lem
karmas¸ıklı˘gına sahiptir. ˙Is¸lem karmas¸ıklı˘gını azaltmak ic¸in de˘gis¸ken adım b¨uy¨ukl¨u˘g¨une
sahip ZA-VSSLMS algoritması tasarlanmıs¸tır. Bilinen VSSLMS algoritmasına l1-norm
kısıtı eklenerek ayrık kanal yapısının ¨ozellikleri kullanılmıs¸tır. Y¨uksek ayrık ¨ozellikleri
olan kanallarda, ZA-VSSLMS algoritması y¨uksek bas¸arım g¨ostermektedir. Beyaz Gauss
g¨ur¨ult¨us¨u altında, algoritma kuramsal olarak analiz edilerek MSD sonucui t¨uretilmis¸tir.
Kalıcıdurum bas¸arımına, sıfırayaklas¸tırıcı ρ ve α adım uzunlu˘gu parametrelerinin etkileri
incelenmis¸ ve ρ ic¸in ¨ust sınır belirlenmis¸tir. Ayrıca, farklı olasılık da˘gılımına sahip g¨ur¨ult¨u
da˘gılımlarının bas¸arıma etkisi aras¸tırılmıs¸tır.
Son olarak, ZA-VSSLMS algoritmasını daha da iyiles¸tirmek ic¸in, maliyet is¸levine bir
logaritmik toplama terimi eklenerek WZA-VSSLMS elde edilmis¸tir.
nerilen ZA-VSSLMS, WZA-VSSLMS, WZA-LLMS algoritmalarının, bilinen standard
algoritmalar ile bas¸arımları, sistem tanılama, yankı giderme ve imge ters-evris¸im
problemlerinde kıyaslanmıs¸tır. Benzetim ve kuramsal sonuc¸lar, ¨onerilen ZA-VSSLMS
algoritmasının, farklı g¨ur¨ult¨u da˘gılımlarında daha y¨uksek bas¸arım sa˘gladı˘gını
g¨ostermektedir. Ayrıca, kuramsal ve benzetim de˘gerleri farklı parametre de˘gerleri ic¸in
¨ort¨us¸mektedir.
Anahtar Kelimeler: Uyarlanır filtre, Ayrık sinyal, Sıkıs¸tırmalı algılama, LMS algoritması,
Sıfıra-yaklas¸an.
