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

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ń? ..

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

Problem polega na rozwiązaniu:

$$\text{minimize} (\text{over} \; \mathbf{x}) \quad \| A\mathbf{x} - \mathbf{b} \|_2$$

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:$\mathbf{b}$zdgelsd$\mathbf{z}$

• $A\mathbf{z} = \mathbf{b}$
• $\| \mathbf{z} \|_2 \leq \|\mathbf{x} \|_2$ dla wszystkich które spełniają . (tzn. jest minimalnym rozwiązaniem normalnym dla nieokreślonego systemu.$\mathbf{x}$$A\mathbf{x} = \mathbf{b}$$\mathbf{z}$

Przykład: jeśli system to , numpy.linalg.lstsq zwróci .$x + y = 1$$x = .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 \Sigma V' = A$$U$$V$$\Sigma$

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:$A$$S$

$$A = U \begin{bmatrix} S & 0 \\ 0 & 0 \end{bmatrix} V'$$

Pseudo odwrotności z jest dana przez:$A$

$$A^\dagger = V \begin{bmatrix} S^{-1} & 0 \\ 0 & 0 \end{bmatrix} U'$$

Rozważ rozwiązanie . Następnie:$\mathbf{x} = A^\dagger \mathbf{b}$

$$\begin{align*} A\mathbf{x} - \mathbf{b} &= U \begin{bmatrix} S & 0 \\ 0 & 0 \end{bmatrix} V' V \begin{bmatrix} S^{-1} & 0 \\ 0 & 0 \end{bmatrix} U' \mathbf{b} - \mathbf{b} \\ &= U \begin{bmatrix} I & 0 \\ 0 & 0 \end{bmatrix} U' \mathbf{b} - \mathbf{b}\\ \end{align*}$$

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.$I$$\mathbf{b}$
2. $A\mathbf{x} - \mathbf{b} = \mathbf{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^\dagger = A'\left(AA' \right)^{-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^\dagger = \left(A'A \right)^{-1}A'$$