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

20

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 12xAxbx+cjest wypukły, jeśliAjest 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

    minimize   12xAxbx+do
    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.

Haitao Du
źródło
7
Wszystkie wartości własne są dodatnimi liczbami rzeczywistymi. Ten fakt leży u podstaw wielu innych.
Matthew Drury
4
Aby pójść nieco dalej niż @Matthew: Jeśli wybierzesz odpowiednią podstawę, wszystkie takie macierze są takie same i równe macierzy tożsamości. Innymi słowy, w każdym wymiarze (dla rzeczywistych przestrzeni wektorowych) istnieje dokładnie jedna dodatnia, zdefiniowana kwadratowo postać, i jest taka sama jak odległość euklidesowa.
whuber
2
Znajdziesz intuicję w wielu elementarnych sposobach pokazania, że ​​wartości własne prawdziwej macierzy symetrycznej są prawdziwe: mathoverflow.net/questions/118626/... W szczególności, kwadratowa postać występuje naturalnie w ilorazie Rayleigha, a matryce symetryczne zapewniają naturalny sposób wyświetlania dużej rodziny matryc, których wartości własne są rzeczywiste. Zobacz twierdzenie o minimaksie Couranta na przykład: en.wikipedia.org/wiki/Courant_minimax_principlexTAx
Alex R.
4
Wydaje się to zbyt szerokie; jeśli nie ma jeszcze trzech odpowiedzi, prawdopodobnie na tej podstawie go zamknę. Proszę podać więcej wskazówek na temat tego, co konkretnie chcesz wiedzieć (proszenie o intuicję jest zbyt osobiste / indywidualne, aby ludzie mogli zgadywać w przypadku takim jak ten)
Glen_b
1
Trudno mi znaleźć sytuację w statystykach , która dałaby początek macierzy, która nie jest psd (chyba że spieprzyłeś się w obliczaniu macierzy korelacji, np. Wypełniając ją korelacją par obliczoną na danych z brakującymi wartościami) . Każda kwadratowa macierz symetryczna, o której mogę myśleć, to albo kowariancja, informacja lub macierz projekcji. (W innym miejscu w matematyce stosowanej macierze inne niż psd mogą być normą kulturową, np. Macierze elementów skończonych w PDE, powiedzmy.)
StasK

Odpowiedzi:

15

(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λ odpowiadającą mu wartością własną, to

λ=λvtv=vtAv>0

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ą R2R 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ć globalne12xAxbx+cA

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

Matthew Drury
źródło
5
Graficzny sposób patrzenia na to: jeśli jest SPD, kontury powiązanej postaci kwadratowej są elipsoidalne. A
JM nie jest statystykiem
7
Ta charakterystyka @JM jest bardzo spostrzegawcza. W przypadku, gdy ktoś zastanawia się, co może być specjalnego w konturach elipsoidalnych, należy pamiętać, że są to po prostu idealne kule w przebraniu: jednostki miary mogą się różnić wzdłuż ich głównych osi, a elipsoidy można obracać względem współrzędnych, w których opisane są dane , ale dla bardzo wielu celów - zwłaszcza koncepcyjnych - różnice te są nieistotne.
whuber
Jest to związane z moim sposobem geometrycznego rozumienia metody Newtona. Najlepiej przybliż bieżący poziom ustawiony za pomocą elipsoidy, a następnie weź układ współrzędnych, w którym elipsoida jest okręgiem, przesuń prostopadle do okręgu w tym układzie współrzędnych.
Matthew Drury,
1
Jeśli istnieją (aktywne) ograniczenia, musisz wykonać rzutowanie na jakobian aktywnych wiązań, zanim wykonasz wartość własną i śledzenie kierunku. Jeśli Hesjan jest psd, (dowolną) projekcją będzie psd, ale odwrotność niekoniecznie jest prawdziwa i często nie jest. Zobacz moją odpowiedź.
Mark L. Stone
10

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_principlexTAx

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)=x,Ay=xTAyx,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.x2=xTAx>0x0

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.

Alex R.
źródło
9

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+Δx)

f(x+Δx)f(x)+ΔxTf(x)+12ΔxT2f(x)Δx

Następnie bierzemy pochodną w odniesieniu do :Δx

f(x+Δx)f(x)+2f(x)Δx

Na koniec ustaw pochodną równą 0 i rozwiąż dla :Δx

Δx=2f(x)1f(x)

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

f(x)TΔx=f(x)T2f(x)1f(x)<0

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.

Bill Woessner
źródło
Dziękuję bardzo za świetną odpowiedź. Rozumiem, że porządny kierunek jest ważny w metodzie przeszukiwania linii. W metodach opartych na regionie zaufania ważny jest także porządny kierunek?
Haitao Du
1
Jest to nadal ważne dla metod regionu zaufania. Metody obszaru zaufania zasadniczo działają, ograniczając rozmiar kroku PIERWSZY, a następnie rozwiązując go dla kierunku kroku. Jeśli krok nie osiągnie pożądanego zmniejszenia wartości funkcji celu, zmniejsz granice wielkości kroku i zacznij od nowa. Wyobraź sobie, że twój algorytm generowania kierunku kroku nie gwarantuje, że kierunek kroku jest kierunkiem opadania. Nawet gdy promień obszaru zaufania osiągnie wartość 0, nigdy nie możesz wygenerować akceptowalnego kroku (nawet jeśli taki istnieje), ponieważ żaden z twoich kierunków kroków nie jest kierunkami zniżania.
Bill Woessner,
Metody przeszukiwania linii w zasadzie wykazują to samo zachowanie. Jeśli kierunek wyszukiwania nie jest kierunkiem opadania, algorytm wyszukiwania linii może nigdy nie znaleźć akceptowalnej długości kroku - ponieważ nie ma takiej wartości. :-)
Bill Woessner,
Świetna odpowiedź, dziękuję za pomoc w połączeniu elementów.
Haitao Du
9

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 ZA dodatnia określona macierz

d(x,y)=(xy)TA(xy)
is a metric (also called distance function).

In addition, positive definite matrices are related to inner product: In Rn, we can define an inner product by

x,y=xTAy
where A as above is positive definite. More, all inner products on Rn arises in this way.

kjetil b halvorsen
źródło
1
...and of course the usual distance has A=I...
J. M. is not a statistician
6

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.

Mark L. Stone
źródło
"Who's Afraid of Non-Convex Loss Functions?" ... not @MarkL.Stone
GeoMatt22
@GeoMatt22 You bet your @$$ I'm not. On the other hand, if you are going to create (choose) a loss function, there's no need to make it non-convex when it serves no good purpose other than show-boating. Discretion is the better part of valor.
Mark L. Stone
@Mark L. Stone: This is interesting! Can you give reference to some literature where I can read about such things?
kjetil b halvorsen
@kjetil b halvorsen . Line search with directions of negative curvature folk.uib.no/ssu029/Pdf_file/Curvilinear/More79.pdf . Trust regions are covered in many books and papers. Well-known book with good intro to trust regions is amazon.com/… .. Monster book, somewhat out of date now, is epubs.siam.org/doi/book/10.1137/1.9780898719857 . As for my last paragraph about optimality conditions, read up on 2nd order KKT conditions
Mark L. Stone
@kjetil b halvorsen I didn't address finding global optimum of non-convex Quadratic Program. Widely available software, such as CPLEX, can do this, see ibm.com/support/knowledgecenter/SS9UKU_12.6.1/… . Of course it is not always fast, and may need some memory. I've solved to global optimality some QP minimization problems with tens of thousands of variables which had several hundred signficant magnitude negative eigenvalues.
Mark L. Stone
5

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

i(xiμ)2/n
It's obvious from the definition that if you feed in the real numbers xi into the equation the output is always non-negative. Hence, you may build algorithms that work with non-negative numbers, and they may be more efficient than algorithm without this restriction. That's the reason we use them.

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.

Aksakal
źródło
3

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).

Thoth
źródło