W jaki sposób NumPy rozwiązuje najmniejsze kwadraty w przypadku niedokreślonych systemów?

14

Powiedzmy, że mamy X kształtu (2, 5)
iy kształtu (2,)

To działa: np.linalg.lstsq(X, y)

Spodziewalibyśmy się, że zadziała to tylko wtedy, gdy X będzie miał kształt (N, 5), gdzie N> = 5 Ale dlaczego i jak?

Odzyskujemy 5 wag zgodnie z oczekiwaniami, ale jak rozwiązać ten problem?

Czy to nie tak, że mamy 2 równania i 5 niewiadomych?
Jak numpy może to rozwiązać?
Musi zrobić coś takiego jak interpolacja, aby stworzyć więcej sztucznych równań? ..

George Pligoropoulos
źródło
3
Dlaczego to nie powinno działać? Nieokreślony system ma wiele rozwiązań.
Matthew Gunn
Czy możesz mieć link do odpowiedniej teorii? ..
George Pligoropoulos

Odpowiedzi:

19

Rozumiem, że numpy.linalg.lstsq opiera się na procedurze LAPACK dgelsd .

Problem polega na rozwiązaniu:

minimize(overx)Axb2

Oczywiście nie ma to unikalnego rozwiązania dla macierzy A, której ranga jest mniejsza niż długość wektora . W przypadku nieokreślonego systemu udostępnia rozwiązanie , które:bzdgelsdz

  • Az=b
  • z2x2 dla wszystkich które spełniają . (tzn. jest minimalnym rozwiązaniem normalnym dla nieokreślonego systemu.xAx=bz

Przykład: jeśli system to , numpy.linalg.lstsq zwróci .x+y=1x=.5,y=.5

Jak działa dgelsd?

Procedura dgelsdoblicza rozkład wartości pojedynczej (SVD) A.

Po prostu naszkicuję pomysł użycia SVD do rozwiązania układu liniowego. Rozkład wartości w liczbie pojedynczej jest faktoryzacją gdzie i są macierzami ortogonalnymi, a jest macierzą diagonalną, w której wpisy diagonalne są znane jako wartości osobliwe.UΣV=AUVΣ

Efektywna ranga macierzy będzie liczbą pojedynczych wartości, które są faktycznie niezerowe (tj. Wystarczająco różne od zera w stosunku do precyzji maszyny itp.). Niech będzie macierzą diagonalną niezerowych wartości pojedynczych. SVD jest zatem:AS

A=U[S000]V

Pseudo odwrotności z jest dana przez:A

A=V[S1000]U

Rozważ rozwiązanie . Następnie:x=Ab

Axb=U[S000]VV[S1000]Ubb=U[I000]Ubb

Są tu w zasadzie dwa przypadki:

  1. Liczba niezerowych wartości pojedynczych (tj. Rozmiar macierzy ) jest mniejsza niż długość . Rozwiązanie tutaj nie będzie dokładne; rozwiążemy układ liniowy w sensie najmniejszych kwadratów.Ib
  2. Axb=0

Ta ostatnia część jest nieco trudna ... trzeba śledzić wymiary macierzy i używać tego, że jest macierzą ortogonalną.U

Równoważność pseudo-odwrotności

Kiedy ma liniowo niezależne rzędy (np. Mamy macierz tłuszczu), to: A

A=A(AA)1

W przypadku nieokreślonego systemu można pokazać, że pseudo-odwrotność daje minimalne rozwiązanie normy.

Kiedy ma liniowo niezależne kolumny (np. Mamy cienką matrycę), to: A

A=(AA)1A

Matthew Gunn
źródło
dgelsd używa SVD, ale czy Rm używa QR?
Haitao Du
@ hxd1011R domyślnie lmkorzysta z faktoryzacji QR, ale możesz podać alternatywy.
Sycorax mówi Przywróć Monikę