Maindonald opisuje sekwencyjną metodę opartą na obrotach Givensa . (Obrót Givensa jest ortogonalną transformacją dwóch wektorów, która zeruje dany wpis w jednym z wektorów.) W poprzednim etapie dokonałeś dekompozycji macierzy projektowej na macierz trójkątną T za pomocą transformacji ortogonalnej Q, tak że Q X = ( T , 0 ) ′ . (Uzyskanie wyników regresji z macierzy trójkątnej jest szybkie i łatwe). Po dołączeniu nowego wiersza v poniżej X skutecznie przedłużasz ( T , 0 )XT.QQX=(T,0)′vX Również przez niezerowy rząd, powiedz t . Zadanie polega na wyzerowaniu tego rzędu przy jednoczesnym zachowaniu wpisów w pozycjiprzekątnej T. Wykonuje to sekwencja rotacji Givens: rotacja z pierwszym rzędem T zeruje pierwszy element t ; następnie obrót z drugim rzędem T zeruje drugi element i tak dalej. Efektem jest przedwczesne Q przez serię obrotów, co nie zmienia jego ortogonalności.(T,0)′tTTtTQ
Gdy macierz projektowa ma kolumny (co ma miejsce w przypadku regresji na zmiennych p plus stała), liczba potrzebnych obrotów nie przekracza p + 1, a każdy obrót zmienia dwa wektory p + 1 . Pamięć potrzebna dla T to O ( ( p + 1 ) 2 ) . Zatem ten algorytm ma koszt obliczeniowy O ( ( p + 1 ) 2 ) zarówno w czasie, jak i przestrzeni.p+1pp+1p+1TO((p+1)2)O((p+1)2)
Podobne podejście pozwala określić wpływ regresji na usunięcie wiersza. Maindonald podaje formuły; podobnie jak Belsley, Kuh i Welsh . Dlatego jeśli szukasz ruchomego okna do regresji, możesz zachować dane dla okna w okrągłym buforze, przylegając do nowego układu odniesienia i upuszczając stary z każdą aktualizacją. Podwaja to czas aktualizacji i wymaga dodatkowej pamięci dla okna o szerokości k . Wydaje się, że 1 / k będzie analogiem parametru wpływu.O(k(p+1))k1/k
W przypadku rozkładu wykładniczego uważam (spekulacyjnie), że można dostosować to podejście do ważonych najmniejszych kwadratów, nadając każdej nowej wartości wagę większą niż 1. Nie powinno być potrzeby utrzymywania bufora poprzednich wartości ani usuwania starych danych.
Bibliografia
JH Maindonald, Obliczenia statystyczne. J. Wiley & Sons, 1984. Rozdział 4.
DA Belsley, E. Kuh, RE Welsch, Diagnostyka regresji: identyfikacja wpływowych danych i źródeł kolinearności. J. Wiley & Sons, 1980.