New adaptive algorithms for linear filtering and nonlinear prediction

Abstract

Bu tezde iki uyarlanır süzgeçleme işini ele alıyoruz: Doğrusal Uyarlanır Süzgeçlemeve Doğrusal Olmayan Uyarlanır Öngörü. Bu işleri sırasıyla sistem tanımlama ve ardışıkdoğrusal olmayan öngörü problemleri üzerinde düşünüyoruz. Bu tezde 3 adet yeni uyarlanıralgoritma (2 adet doğrusal süzgeçleme için ve 1 adet doğrusal olmayan Öngörü için) sunuluyor.Doğrusal süzgeçlemede, LMS (Least Mean Squares) algoritması temel bir algoritma olupbasit bir çalışma prensibi vardır ancak yeterince hızlı yakınsama yapmaz. [1]'de Duttweilertarafından önerilen orantılı güncelleme fikri LMS algoritmasının yakınsama hızında seyreltiksistemler için önemli bir gelşme sağlar. Biz bu tezde [2]'nin LMS algoritmasından LMF(Least Mean Fourth) algoritmasını ürettiği yolu takip edip hatanın dördüncü kuvvetinin or-talamasını küçülterek PNLMF (Proportionate Normalized LMF) algoritmasını üretiyoruz.Yukawa'nın [3]'de probleme bir Krylov altuzayı izdüşüm tekniğini dahil etmesi orantılıgüncelleme fikrini seyreltik olmayan ayırgan sistemler için de kullanılabilir hale geitrir. Butezde, aynı Krylov altuzay izdüşüm tekniğini kullanıp yine hatanın dördüncü kuvvetininortalamasını küçülterek KPNLMF (Krylov-Proportionate NLMF) algoritmasını sunuyoruz.Burda, [2]'deki LMS ile LMF arasındaki ilişkinin aynısını KPNLMS ile KPNLMF arasındada gözlemliyoruz. Benzetimler, KPNLMF algoritmasının tatbiki önem içeren farklı olasılıkyoğunluk fonksiyonlarına sahip gürültüler altında KPNLMS algoritmasından daha iyi çalıştığınıgösteriyor. Benzetimlerde ayrıca KPNLMF algoritmasının başarımının NLMF algoritmasınınbaşarımından üstün olduğu gösteriliyor. Bu tezin bir diğer katkısı KPNLMS ve KPNLMFalgoritmaları için yatışkın durum ortalama karesel hata analizi gerçekleştirmesi. İki algo-ritmanın da kuramsal olarak yatışkın durum ortalama karesel hata kıstasına göre istenilensonuca yakınsama yaptıkları kanıtlanıyor.Tezin ikinci kısmında herhangi bir sınırlı, gerçek değerli ve belirlenimci sinyalin gürültüylebozulmuş geçmiş örneklerinden karesel hata kayıp fonksiyonuyla ardışık doğrusal olmayanöngörülmesi ele alınıyor. CRNNP adında yeni bir rasgeleleştirilmiş ardışık öngörücü algo-ritma sunuyoruz. Bu tezin bu konudaki ana katkısı toplanır gürültü altında yüksek öngörübaşarımına ulaşmasıdır. CRNNP algoritması herhangi bir belirlenimci sinyalle çalışabildiğiiçin anlamlı bir başarım ölçüsü tanımlamak adına yarışmacı bir çerçeve sunuyoruz. CRNNP,içindeki algoritmalar varsayımsal olarak paralel çalışan bir yarışma sınıfında işlem görüyor.CRNNP ulaşılmak istenen temiz sinayli kullanarak hem geçmiş gözlem uzayındaki en iyibölümlemeyi hem de ilgin model parametrelerini seçebilen, yarışma sınıfındaki en iyi algorit-manın başarımına erişiyor. Yarışma sınıfı, bir bağlam ağacı yapısında temsil edilen parçalıilgin modellerdir. Bu yüzden problemin doğasında varolan doğrusal olmamayı modellemekiçin bağlam ağacı yapısı kullanıyoruz. CRNNP algoritması ardışık karar verme probleminehizmet ediyor ve kararlarını her zaman belli sayıdaki yöntemden birini rasgeleleştirilmiş birşekilde seçerek veriyor. Rasgeleleştirme ağırlıkları yöntemlerin öngörü başarımına dayalıolarak belirleniyor.

In this thesis, we consider two adaptive filtering tasks: Linear Adaptive Filtering andNonlinear Adaptive Prediction. We handle system identification and sequential (online)nonlinear prediction problems for these tasks respectively. 3 novel adaptive algorithms (2in linear filtering and 1 in nonlinear prediction) are presented in this thesis.For linear adaptive filtering, Least Mean Squares (LMS) is a fundamental, simple yetnot fast enough converging algorithm. Proportionate update idea that is proposed by Dut-tweiler in [1] achieves a significant development in the convergence speed of LMS for sparsesystems. We develop the Proportionate Normalized Least Mean Fourth (PNLMF) algo-rithm by minimizing mean fourth error (MFE) in the same way as [2] produces the LeastMean Fourth (LMF) algorithm from LMS. Yukawa's implementation of a Krylov subspaceprojection technique into the problem extends the use of proportionate update idea to non-sparse systems. We exploit the same Krylov subspace projection technique and introducethe Krylov-Proportionate Normalized Least Mean Fourth (KPNLMF) algorithm by againminimizing MFE. The Krylov-Proportionate Normalized Least Mean Squares (KPNLMS)algorithm minimizes mean square error (MSE) and our introduced KPNLMF algorithm isthe MFE counterpart of KPNLMS. We observe the same relation between KPNLMS andKPNLMF as the one between LMS and LMF that is presented in [2]. Simulations showthat KPNLMF attains a much lower mismatch (filter weight error power) than KPNLMSwhen the system noise has a probability density function among certain types that are ofpractical importance. It is also shown in the simulations that KPNLMF converges fasterthan the Normalized LMF (NLMF) algorithm. Another contribution of this thesis is thatthe steady-state MSE analysis is performed both for KPNLMS and KPNLMF. They areboth shown theoretically to converge to the desired solution according to the steady-stateMSE criterion.In the second main part of the thesis, we deal with the sequential nonlinear prediction ofan arbitrary, deterministic and bounded signal from its noise-corrupted past samples undersquare error loss. We present a novel randomized sequential prediction algorithm and nameit Competitive Randomized Noisy Nonlinear Predictor (CRNNP). The main contribution ofthis thesis in this topic is that the CRNNP algorithm achieves a high prediction performanceunder additive noise. Since our CRNNP algorithm works for an arbitrary deterministicsignal, we introduce a competitive framework in order to define a meaningful performancemeasure. CRNNP works in a competition class of algorithms that hypothetically workin parallel. We show that CRNNP achieves the performance of the best algorithm thatcan both select the best partition of the past observations space and the affine modelparameters based on the desired clean signal in hindsight. The competition class is theclass of certain nonlinear models, i.e. piecewise affine models represented on a context-tree.So, we employ a context-tree structure to model the nonlinearity that exists in the problem.The CRNNP algorithm serves for sequential decision problem and it makes its decision bychoosing a strategy from several number of strategies at each time in a randomized fashion.Randomization weights are determined according to the prediction performances of thestrategies.