Rozwiązywanie układu równań z rzadkimi danymi

Próbuję rozwiązać zbiór równań, który ma 40 zmiennych niezależnych (x1, ..., x40) i jedną zmienną zależną (y). Całkowita liczba równań (liczba wierszy) wynosi ~ 300, i chcę rozwiązać dla zestawu 40 współczynników, które minimalizują całkowity błąd kwadratowy między y a przewidywaną wartością.

Mój problem polega na tym, że macierz jest bardzo rzadka i nie znam najlepszego sposobu rozwiązania układu równań z rzadkimi danymi. Przykład zestawu danych pokazano poniżej:

   y    x1  x2 x3 x4 x5 x6 ... x40
87169   14  0  1  0  0  2  ... 0 
46449   0   0  4  0  1  4  ... 12
846449  0   0  0  0  0  3  ... 0
....

Obecnie używam algorytmu genetycznego, aby rozwiązać ten problem, a wyniki wychodzą z grubsza o czynnik dwóch różnic między obserwowanym a oczekiwanym.

Czy ktoś może zasugerować różne metody lub techniki, które są w stanie rozwiązać zestaw równań z rzadkimi danymi.

Jeśli dobrze cię rozumiem, jest to przypadek wielokrotnej regresji liniowej z rzadkimi danymi ( rzadka regresja ). Zakładając, że mam nadzieję, że poniższe zasoby okażą się przydatne.

1) Slajdy wykładowe NCSU na temat rzadkiej regresji z omówieniem algorytmów, notatek, wzorów, grafiki i odniesień do literatury: http://www.stat.ncsu.edu/people/zhou/courses/st810/notes/lect23sparse.pdf

2) Rekosystem oferuje wiele pakietów przydatnych do analizy rzadkiej regresji, w tym:

• Matryca ( http://cran.r-project.org/web/packages/Matrix )
• SparseM ( http://cran.r-project.org/web/packages/SparseM )
• MatrixModels ( http://cran.r-project.org/web/packages/MatrixModels )
• glmnet ( http://cran.r-project.org/web/packages/glmnet )
• pochodni ( http://cran.r-project.org/web/packages/flare )

3) Wpis na blogu z przykładem rozwiązania regresji rzadkiej na podstawie SparseM: http://aleph-nought.blogspot.com/2012/03/multiple-linear-regression-with-sparse.html

4) strony post stosując rzadkie w macierzy B , które znajduje się podkład na użyciu glmnet: http://www.johnmyleswhite.com/notebook/2011/10/31/using-sparse-matrices-in-r

5) Więcej przykładów i kilka dyskusji na ten temat można znaleźć na StackOverflow : /programming/3169371/large-scale-regression-in-r-with-a-sparse-feature-matrix

AKTUALIZACJA (na podstawie Twojego komentarza):

Jeśli próbujesz rozwiązać problem LP z ograniczeniami, ten teoretyczny artykuł może ci się przydać: http://web.stanford.edu/group/SOL/papers/gmsw84.pdf .

Sprawdź także pakiet R limSolve : http://cran.r-project.org/web/packages/limSolve . I ogólnie sprawdź pakiety w widoku zadań CRAN „Optymalizacja i programowanie matematyczne” : http://cran.r-project.org/web/views/Optimization.html .

Na koniec sprawdź książkę „Korzystanie z R do analizy numerycznej w nauce i inżynierii” (autor: Victor A. Bloomfield). Zawiera sekcję dotyczącą rozwiązywania układów równań, reprezentowaną przez rzadkie macierze (sekcja 5.7, strony 99-104), która zawiera przykłady oparte na niektórych z wyżej wymienionych pakietów: http://books.google.pl/books? ID = 9ph_AwAAQBAJ & pg = PA99 i gazowe = PA99 i dq = r + limsolve + rzadki + matrycowego źródło = Bl OTS = PHDE8nXljQ i porządek = sPi4n5Wk0M02ywkubq7R7KD_b04 & hl = pl & sa = X & ei = FZjiU-ioIcjmsATGkYDAAg & at = 0CDUQ6AEwAw # v = onepage i q = r% 20limsolve% 20sparse% 20matrix & f = fałszywe .

Odpowiedź Aleksandra jest całkowicie poprawna.

Jednak sposób, w jaki pytanie jest postawione, implikuje, że jest to proste zwykłe pytanie regresji metodą najmniejszych kwadratów: minimalizowanie sumy kwadratów reszt między zmienną zależną a liniową kombinacją predyktorów.

Chociaż w macierzy projektowej może znajdować się wiele zer, system jako taki nie jest zbyt duży: 300 obserwacji na 40 predyktorach jest nie więcej niż średniej wielkości. Możesz uruchomić taką regresję za pomocą R bez specjalnych wysiłków dla rzadkich danych. Wystarczy użyć lm()polecenia (dla „modelu liniowego”). Użyj, ?lmaby wyświetlić stronę pomocy. I pamiętaj, że lmdomyślnie po cichu doda stałą kolumnę z nich do macierzy projektu (punkt przecięcia) - dołącz -1po prawej stronie formuły, aby to ukryć. Ogólnie rzecz biorąc, zakładając, że wszystkie twoje dane (i nic więcej) są data.framewywoływane foo, możesz to zrobić:

model <- lm(y~.-1,data=foo)

Następnie możesz spojrzeć na oszacowania parametrów itp. W następujący sposób:

summary(model)
residuals(model)

Jeśli twój system jest znacznie większy, powiedzmy na przykład 10 000 obserwacji i setek predyktorów, spojrzenie na wyspecjalizowane rzadkie solwery według odpowiedzi Aleksandra może zacząć mieć sens.

Wreszcie w swoim komentarzu do odpowiedzi Aleksandra wspominasz o ograniczeniach w swoim równaniu. Jeśli to jest twój kluczowy problem, istnieją sposoby na obliczenie ograniczonych najmniejszych kwadratów w R. Osobiście lubię pcls()w mgcvpakiecie. Być może chcesz edytować swoje pytanie, aby uwzględnić rodzaj ograniczeń (ograniczenia pola, ograniczenia nieujemności, ograniczenia integralności, ograniczenia liniowe ...), z którymi się zmagasz?