Dlaczego macierze symetryczne z dodatnim określeniem (SPD) są tak ważne?

Znam definicję macierzy symetrycznej dodatniej określonej (SPD), ale chcę zrozumieć więcej.

Dlaczego są tak ważne, intuicyjnie?

Oto co wiem. Co jeszcze?

• Dla danych danych macierzą współwariancji jest SPD. Macierz współwariancji jest ważnym miernikiem, zobacz ten doskonały post dla intuicyjnego wyjaśnienia.

• Forma kwadratowa $\frac 1 2 x^\top Ax-b^\top x +c$jest wypukły, jeśli$A$jest SPD. Wypukłość to miła właściwość dla funkcji, która może zapewnić, że lokalne rozwiązanie jest rozwiązaniem globalnym. W przypadku problemów wypukłych istnieje wiele dobrych algorytmów do rozwiązania, ale nie w przypadku problemów niewypukłych.

• Gdy $A$ jest SPD, rozwiązanie optymalizujące dla postaci kwadratowej

  $$\text{minimize}~~~ \frac 1 2 x^\top Ax-b^\top x +c$$ i rozwiązanie dla układu liniowego $$Ax=b$$ są takie same. Możemy więc przeprowadzić konwersje między dwoma klasycznymi problemami. Jest to ważne, ponieważ pozwala nam korzystać ze sztuczek odkrytych w jednej domenie w drugiej. Na przykład możemy użyć metody gradientu sprzężonego do rozwiązania układu liniowego.

• Istnieje wiele dobrych algorytmów (szybkich, stabilnych numerycznie), które działają lepiej dla macierzy SPD, takich jak rozkład Cholesky'ego.

EDYCJA: Nie próbuję pytać o tożsamość macierzy SPD, ale intuicję stojącą za właściwością, aby pokazać znaczenie. Na przykład, jak wspomniał @Matthew Drury, jeśli macierzą jest SPD, wszystkie wartości własne są dodatnimi liczbami rzeczywistymi, ale dlaczego wszystkie wartości są ważne. @Matthew Drury miał świetną odpowiedź na przepływ i właśnie tego szukałem.

(Rzeczywista) macierz symetryczna ma pełny zestaw wektorów własnych ortogonalnych, dla których wszystkie odpowiednie wartości własne są liczbami rzeczywistymi. W przypadku macierzy niesymetrycznych może się to nie powieść. Na przykład obrót w przestrzeni dwuwymiarowej nie ma wektora własnego lub wartości własnych w liczbach rzeczywistych. Aby je znaleźć, należy przejść do przestrzeni wektorowej nad liczbami zespolonymi.

Jeśli macierz jest dodatkowo dodatnia, wówczas wszystkie te wartości własne są dodatnimi liczbami rzeczywistymi. Ten fakt jest znacznie łatwiejszy niż pierwszy, ponieważ jeśli jest wektorem własnym o długości jednostkowej i $v$$\lambda$ odpowiadającą mu wartością własną, to

gdzie ostatnia równość używa definicji pozytywnej definitywności.

Znaczenie intuicji jest takie, że wektory własne i wartości własne transformacji liniowej opisują układ współrzędnych, w którym transformacja jest najłatwiejsza do zrozumienia. Transformacja liniowa może być bardzo trudna do zrozumienia w „naturalnych” podstawach, takich jak standardowy układ współrzędnych, ale każda zawiera „preferowaną” podstawę wektorów własnych, w których transformacja działa jak skalowanie we wszystkich kierunkach. Dzięki temu geometria transformacji jest znacznie łatwiejsza do zrozumienia.

Na przykład, drugi test pochodnej do miejscowego ekstremów funkcją $R^2 \rightarrow R$ jest często stosowany w postaci szeregu tajemniczej stanów związanych z wpisu drugiej matrycy pochodnych oraz niektórych uwarunkowań. W rzeczywistości warunki te po prostu kodują następującą obserwację geometryczną:

• Jeśli macierz drugich pochodnych jest dodatnia, oznacza to, że masz lokalne minimum.
• Jeśli macierz drugich pochodnych jest ujemna, masz lokalne maksimum.
• W przeciwnym razie nie jesteś w żadnym punkcie siodła.

Możesz to zrozumieć dzięki powyższemu wnioskowi geometrycznemu w bazie własnej. Pierwsza pochodna w punkcie krytycznym znika, więc tempo zmian funkcji tutaj kontrolowane jest przez drugą pochodną. Teraz możemy rozumować geometrycznie

• W pierwszym przypadku istnieją dwa kierunki własne, a jeśli się poruszasz, jedna z funkcji wzrasta.
• W drugim, dwa kierunki własne i jeśli poruszasz się w którejś z funkcji, zmniejsza się.
• W ostatnim są dwa kierunki własne, ale w jednym z nich funkcja rośnie, w drugim maleje.

Ponieważ wektory własne obejmują całą przestrzeń, każdy inny kierunek jest liniową kombinacją kierunków własnych, więc szybkości zmian w tych kierunkach są liniowymi kombinacjami szybkości zmian w kierunkach własnych. Tak więc dzieje się tak we wszystkich kierunkach (mniej więcej to oznacza, że ​​funkcja zdefiniowana w przestrzeni o wyższym wymiarze może być różniczkowa- na). Teraz, jeśli narysujesz mały obrazek w głowie, ma to sens z czegoś, co jest dość tajemnicze w tekstach dla początkujących.

Dotyczy to bezpośrednio jednego z twoich punktów

Forma kwadratowa jest wypukły, jeśliAjest SPD. Wypukła to fajna właściwość, dzięki której lokalne rozwiązanie może być globalne$\frac 1 2 x^\top Ax-b^\top x +c$$A$

Macierz drugich pochodnych jest wszędzie , co jest symetrycznym dodatnim określonym. Geometrycznie oznacza to, że jeśli odejdziemy w dowolnym kierunku własnym (a więc w dowolnym kierunku, ponieważ każdy inny jest liniową kombinacją kierunków własnych), sama funkcja wygnie się powyżej swojej płaszczyzny stycznej. Oznacza to, że cała powierzchnia jest wypukła.$A$

Znajdziesz intuicję w wielu elementarnych sposobach pokazania, że ​​wartości własne prawdziwej macierzy symetrycznej są prawdziwe: /mathpro/118626/real-symmetric-matrix-has-real-eigenvalues-elementary- dowód / 118640 # 118640

W szczególności forma kwadratowa występuje naturalnie w ilorazie Rayleigha, a macierze symetryczne zapewniają prawdopodobnie najbardziej naturalny sposób wyświetlania dużej rodziny matryc, których wartości własne są rzeczywiste. Zobacz na przykład twierdzenie o minimaksie Couranta: https://en.wikipedia.org/wiki/Courant_minimax_principle$x^TAx$

Ponadto, ściśle symetryczne dodatnie konkretne matryce są tylko zestaw matryc, które mogą definiować nietrywialne produkt wewnętrzną wraz z indukowanym normy: . Wynika to z definicji rzeczywistych wektorów x , y d ( x , y ) = d ( y , x ) dla wszystkich x , y i ‖ x ‖ 2$d(x,y)=\langle x,Ay\rangle=x^TAy$$x,y$ $d(x,y)=d(y,x)$$x,y$ dla x ≠ 0 . W ten sposób symetryczne dodatnie określone macierze można postrzegać jako idealnych kandydatów do przekształceń współrzędnych.$\|x\|^2=x^TAx>0$$x\neq 0$

Ta ostatnia właściwość jest absolutnie kluczowa w obszarze maszyn wektorów wspierających, w szczególności metod jądra i sztuczki jądra , gdzie jądro musi być symetryczne dodatnio, aby wywołać właściwy produkt wewnętrzny. Rzeczywiście twierdzenie Mercer'a uogólnia intuicyjne właściwości macierzy symetrycznych na przestrzenie funkcjonalne.

Jeśli chodzi o optymalizację (ponieważ otagowałeś swoje pytanie tagiem optymalizacyjnym), macierze SPD są niezwykle ważne z jednego prostego powodu - Heski SPD gwarantują, że kierunek wyszukiwania jest kierunkiem opadania. Rozważ wyprowadzenie metody Newtona dla nieograniczonej optymalizacji. Najpierw tworzymy rozszerzenie Taylora dla :$f(x + \Delta x)$

Następnie bierzemy pochodną w odniesieniu do :$\Delta x$

Na koniec ustaw pochodną równą 0 i rozwiąż dla :$\Delta x$

Zakładając, że to SPD, łatwo zauważyć, że Δ x jest kierunkiem opadania, ponieważ:$\nabla^2 f(x)$$\Delta x$

Podczas korzystania z metody Newtona macierze Hesji spoza SPD są zwykle „szturchnięte” w SPD. Istnieje zgrabny algorytm o nazwie zmodyfikowany Cholesky, który wykryje Hesja spoza SPD, „popchnie” go odpowiednio we właściwym kierunku i rozłoży na czynniki wynik, a wszystko to za (zasadniczo) taki sam koszt jak rozkład na czynniki choleskie. Metody quasi-Newtona unikają tego problemu, zmuszając przybliżony Hesjan do bycia SPD.

Nawiasem mówiąc, symetryczne systemy nieokreślone są obecnie przedmiotem dużej uwagi. Pojawiają się one w kontekście wewnętrznych metod punktowych do ograniczonej optymalizacji.

Geometrycznie dodatnia określona macierz definiuje metrykę , na przykład metrykę Riemanniana, dzięki czemu możemy od razu korzystać z pojęć geometrycznych.

Gdyby $x$ i $y$ to wektory i $A$ dodatnia określona macierz

In addition, positive definite matrices are related to inner product: In $\mathbb{R}^n$, we can define an inner product by

There are already several answers explaining why symmetric positive definite matrices are so important, so I will provide an answer explaining why they are not as important as some people, including the authors of some of those answers, think. For the sake of simplicity, I will limit focus to symmetric matrices, and concentrate on Hessians and optimization.

If God had made the world convex, there wouldn't be convex optimization, there would just be optimization. Similarly, there wouldn't be (symmetric) positive definite matrices, there would just be (symmetric) matrices. But that's not the case, so deal with it.

If a Quadratic Programming problem is convex, it can be solved "easily". If it is non-convex, a global optimum can still be found using branch and bound methods (but it may take longer and more memory).

If a Newton method is used for optimization and the Hessian at some iterate is indefinite, then it is not necessary to "finagle" it to positive definiteness. If using a line search, directions of negative curvature can be found and the line search executed along them, and if using a trust region, then there is some small enough trust region such that the solution of the trust region problem achieves descent.

As for Quasi-Newton methods, BFGS (damped if the problem is constrained) and DFP maintain positive definiteness of the Hessian or inverse Hessian approximation. Other Quasi-Newton methods, such as SR1 (Symmetric Rank One) do not necessarily maintain positive definiteness. Before you get all bent out of shape over that, that is a good reason for choosing SR1 for many problems - if the Hessian really isn't positive definite along the path to the optimum, then forcing the Quasi-Newton approximation to be positive definite may result in a lousy quadratic approximation to the objective function. By contrast, the SR1 updating method is "loose as a goose", and can writhely morph its definiteness as it proceeds along.

For nonlinearly constrained optimization problems, what really matters is not the Hessian of the objective function, but the Hessian of the Lagrangian. The Hessian of the Lagrangian may be indefinite even at an (the) optimum, and indeed, it is only the projection of the Hessian of the Lagrangian into the nullspace of the Jacobian of the active (linear and nonlinear) constraints which need be positive semi-definite at the optimum. If you model the Hessian of the Lagrangian via BFGS and thereby constrain it to be positive definite, it might be a terrible fit everywhere, and not work well. By contrast, SR1 can adapt its eigenvalues to what it actually "sees".

There's much more that I could say about all of this, but this is enough to give you a flavor.

Edit: What I wrote 2 paragraphs up is correct. However, I forgot to point out that it also applies to linearly constrained problems. In the case of linearly constrained problems, the Hessian of the Lagrangian is just (reduces down to) the Hessian of the objective function. So the 2nd order optimality condition for a local minimum is that the projection of the Hessian of the objective function into the nullspace of the Jacobian of the active constraints is positive semi-definite. Most notably, the Hessian of the objective function need not (necessarily) be psd at the optimum, and often isn't, even on linearly constrained problems.

You already cited a bunch of reasons why SPD are important yet you still posted the question. So, it seems to me that you need to answer this question first: Why do positive quantities matter?

My answer is that some quantities ought to be positive in order to reconcile with our experiences or models. For instance, the distances between items in the space have to be positive. The coordinates can be negative, but the distances are always non-negative. Hence, if you have a data set and some algorithm that processes it you may well end up with one that breaks down when you feed a negative distance into it. So, you say "my algorithm requires positive distance inputs at all times", and it wouldn't sound like an unreasonable demand.

In the context of statistics, a better analogy would be the variance. So, we calculate the variance as

So, variance-covariance matrices are positive semi-definite, i.e. "non-negative" in this analogy. The example of an algorithm that requires this condition is Cholesky decomposition, it's very handy. It's often called a "square root of the matrix". So, like the square root of a real number that requires non-negativity, Cholesky wants non-negative matrices. We don't find this constraining when dealing with covariance matrices because they always are.

So, that's my utilitarian answer. The constraints such as non-negativity or SPD allow us build more efficient calculation algorithm or convenient modeling tools that are available when your inputs satisfy these constraints.

Here are two more reasons which haven't been mentioned for why positive-semidefinite matrices are important:

1. The graph Laplacian matrix is diagonally dominant and thus PSD.

2. Positive semidefiniteness defines a partial order on the set of symmetric matrices (this is the foundation of semidefinite programming).