Rekurzivni algoritam najmanjih kvadrata (RLS) je adaptivni filter koji rekurzivno utvrđuje koeficijente koji smanjuju ponderisani linearni najmanji kvadrat funkcija troškova u vezi ulaznih signala. Ovo je za razlika u odnosu na druge algoritme kao što je algoritam najmanjih srednjih kvadrata (LMS) čiji je cilj da smanji srednje kvadratne greške. U izvođenje rekurzivnog algoritma najmanjih kvadrata, ulazni signal se smatra determinističkim, dok se algoritam najmanjih srednjih kvadrata i slični algoritmi smatraju stohastičkom. U poređenju sa većinom svojih konkurenata, eksponati rekurzivnog algoritma najmanjih kvadrat izuzetno brzo konvergiraju. Međutim, ova korist dolazi po cenu visokog računarske kompleksnosti.
RLS je otkrio Karl Fridrih Gaus ali ostaje neiskorišćen ili ignorisan do 1950. godine, kada Placket otkriva originalni rad Gausa od 1821. U principu, RLS algoritmi mogu da se koriste za rešavanje svakog problema koji mogu da reše adaptivni filteri, Na primer, pretpostavimo da je signal d(n) koji se prenosi preko eha, bučni kanal koji uzrokuje da bude primljen kao
gde predstavlja dodatnu buku. Mi ćemo pokušati da oporavimo željeni signal upotrebom -tap impulsa konačnih odziva, :
gde je vektor koji sadrži Najnoviji uzorci . Naš cilj je da se proceni parametre filtera , i u svakom trenutku n mislimo na nove najmanjih kvadrata procena . Kako vreme prolazi, želimo da se u potpunosti izbegnu prepravke algoritma najmanjih kvadrata i da pronađu novu procenu za , u smislu .
Korist od RLS algoritma je da nema potrebe obrnuti matricu, čime se štedi računarska snaga. Još jedna prednost je u tome što daje intuiciju iza takvih rezultata kao Kalman filter.
Ideja RLS filtera je da minimizira funkciju troškova i adekvatno odabira filter koeficijenti , ažuriranje filtera kad stignu novi podaci. Signal greške i željeni signal su definisani u dijagramu negativne povratne sprege :
Greška implicitno zavisi od koeficijenta filtera putem procene. :
Najmanja funkcija kvadrata greška — želimo da se cena funkcija minimizira-kao funkcija e(n) stoga takođe zavisi od koeficijenta filtera:
gde je " faktor zaboravljanja " koji daje eksponencijalno manju težinu starijim uzorcima grešaka.
Funkcija troškova je svedena na minimum uzimanjem parcijalnog izvoda za sve stavke koeficijenta vektora i postavljanje rezultata na nulu:
Dalje, zameni sa definicijom signala greške
Preuređivanje jednačine prinosa
Ovaj oblik može da se izrazi u smislu matrice
where je izmeren uzorak kovarijansi matrica za , i je ekvivalentna procena za poprečnu-kovarijansu od i Na osnovu ovog izraza nalazimo koeficijente koji minimiziraju troškove funkcije kao::
Ovo je glavni rezultat diskusije.
Manji je, mali doprinos prethodnim uzorcima. To čini filter više osetljivim na nedavne uzorke, što znači više fluktuacije u filteru koeficijenta. Za slučaj se uzima kao primer rastućeg RLS algoritma. U praksi, se obično bira između 0,98 i 1.[1]
Rasprava je rezultirala u jednoj jednačini da se odredi koeficijent vektor koji minimizira funkciju troškova. U ovom odeljku želimo da izvedemo rekurzivno rešenje u obliku
gde je korektivni faktor u vremenu . Istražujemo poreklo rekurzivnog algoritma izražavajući unakrsno kovarijansu povodom
|
|
|
|
|
|
gde jedimenzionalni vektor podataka:
Slično izražavamo U pogledu
od
|
|
|
|
Da bi generisali koeficijent vektora mi smo zainteresovani za suprotnost od determinističke matrice. Iz tog zadatka identitet matrica dolazi u kombinaciji.
Sa
|
is -by-
|
|
is -by-1
|
|
is 1-by-
|
|
is the 1-by-1
|
Sledi identitet matrica
|
|
|
|
|
|
|
|
|
|
|
|
U skladu sa standardnom literaturom, definišemo
|
|
|
|
gde je "dobijen vektor"
|
|
|
|
Pre nego što krenemo dalje, neophodno je da se donese u drugom obliku
|
|
|
|
Oduzimanjem drugog mandata na levoj strani prinosa
|
|
|
|
Sa rekurzivnom definicijom željena forma prati
Sada smo spremni da završimo rekurziju. Kao što je navedeno
|
|
|
|
Drugi korak proizlazi iz rekurzivne definicije. Zatim smo ugradili rekurzivno definicije zajedno sa alternativnim oblikom i dobijamo
|
|
|
|
|
|
Sa dolazimo do jednačine za ažuriranje
|
|
|
|
Gde je Greška izračunavanja "posle"
filtera se ažurira::
To znači da smo našli faktor korekcije:
Ovaj intuitivno zadovoljavajući rezultat ukazuje da je korektivni faktor direktno proporcionalan greškama i pojačanjima vektora, i da kontroliše kolika osetljivost se želi.
RLS algoritam za pse pomoću RLS filtera može sumirati na:
Parametri: |
poredak filtera
|
|
faktor zaboravljanja
|
|
vrednost da se pokrene
|
Inicijalizacija: |
,
|
|
,
|
|
|
|
gde je matrica identiteta ranga
|
Obračun: |
Za
|
|
|
|
|
|
|
|
|
|
.
|
Imajte na umu da rekurzija za sledi algebarska Rikatijeva jednačina i tako povlači paralele do Kalman filtera.[2]
Rekurzivne rešetke najmanjih kvadrata filtera se odnosi na standardni RLS, osim da je potrebno manje aritmetičkih operacija . Ona nudi dodatne prednosti u odnosu na konvencionalne LMS algoritme kao što su brže stope konvergencije, modularne strukture, i neosetljivost na varijacijama u širenja ulazne korelacione matrice.LRLS algoritam zasnovan je na greškama i uključuje normalizovani oblik. Izvođenje je slična standardnom RLS algoritmu i zasniva se na definiciji . U predikcionom slučaju, imamo sa ulaznim signalom kao najviši uzorak. Predviđanje zaostalih slučajeva , gde indeks uzorka u prošlosti želimo da predvidimo, a ulazni signal je najnoviji uzorak.[3]
- je napredni koeficijent refleksije
- je nazadan koeficijent refleksije
- predstavlja trenutno aposteriori napredno predviđanje o grešci
- predstavlja trenutno aposteriori nazadno predviđanje o grešci
- je minimum najmanjih kvadrata nazadno predviđanje grešaka
- je minimum najmanjih kvadrata napredno predviđanje grešaka
- je faktor konverzije između apriori i aposteriori, greške
- su višestruki koeficijenti.
- je mala pozitivna konstanta koja može biti 0.01
Algoritam za LRLS filter se može sažeti u
Inicijalizacija:
|
|
For i = 0,1,...,N
|
|
(if x(k) = 0 for k < 0)
|
|
|
|
|
|
|
|
End
|
Izračunavanje:
|
|
For k ≥ 0
|
|
|
|
|
|
|
|
|
|
For i = 0,1,...,N
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
End
|
|
End
|
|
|
Normalizovana forma LRLS ima manje rekurzije i promenljivih. Može se izračunati primenom normalizacije internih varijabli algoritma koji će zadržati svoju veličinu. Ovo se uglavnom ne koristi u realnom vremenu aplikacije zbog broja odeljenja i kvadratnog korena operacija koja dolazi sa visokim računarskim opterećenjem.
Algoritam za NLRLS filter se može sažeti u
Inicijalizacija:
|
|
For i = 0,1,...,N
|
|
(if x(k) = d(k) = 0 for k < 0)
|
|
|
|
|
|
End
|
|
|
Izračunavanje:
|
|
For k ≥ 0
|
|
(ulazni signal snage)
|
|
(referentni signal snage)
|
|
|
|
|
|
For i = 0,1,...,N
|
|
|
|
|
|
|
|
|
|
|
|
|
|
End
|
|
End
|
|
|
- ^ Emannual C. Ifeacor, Barrie W. Jervis. Digital signal processing: a practical approach, second edition. Indianapolis: Pearson Education Limited. (2002). str. 718.
- ^ Welch, Greg and Bishop, Gary "An Introduction to the Kalman Filter", Department of Computer Science, University of North Carolina at Chapel Hill, September 17, 1997, accessed July 19, 2011.
- ^ Albu, Kadlec, Softley, Matousek, Hermanek, Coleman, Fagan "Implementation of (Normalised) RLS Lattice on Virtex" Arhivirano na sajtu Wayback Machine (4. март 2016), Digital Signal Processing, 2001, accessed December 24, 2011.
- Hayes, Monson H. (1996). „9.4: Recursive Least Squares”. Statistical Digital Signal Processing and Modeling. Wiley. стр. 541. ISBN 978-0-471-59431-4.
- Haykin, Simon (2002). Adaptive Filter Theory. Prentice Hall. ISBN 978-0-13-048434-5.
- M.H.A Davis, R.B. Vinter (1985). Stochastic Modelling and Control. Springer. ISBN 978-0-412-16200-8.
- Weifeng Liu, Jose Principe and Simon Haykin (2010). Kernel Adaptive Filtering: A Comprehensive Introduction. John Wiley. ISBN 978-0-470-44753-6.
- R.L.Plackett, Some Theorems in Least Squares, Biometrika, 1950, 37, 149-157, ISSN 0006-3444
- C.F.Gauss, Theoria combinationis observationum erroribus minimis obnoxiae, 1821, Werke, 4. Gottinge