Sparse Adaptive Filtering and Applications

Abstract

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.