Znalezienie pierwiastka kwadratowego macierzy Laplaciana

11

Załóżmy, że podano następującą macierz z transponowaniem . Produkt daje , $A$

[\begin{array}{ccc} 0.500 & - 0.333 & - 0.167 \\ - 0.500 & 0.667 & - 0.167 \\ - 0.500 & - 0.333 & 0.833 \end{array}]

$\left[\begin{array}{ccc} 0.500 & -0.333 & -0.167\\ -0.500 & 0.667 & -0.167\\ -0.500 & -0.333 & 0.833\end{array}\right]$

A^{T}

$A^T$

A^{T} A = G

$A^TA=G$

[\begin{array}{ccc} 0.750 & - 0.334 & - 0.417 \\ - 0.334 & 0.667 & - 0.333 \\ - 0.417 & - 0.333 & 0.750 \end{array}]

$\left[\begin{array}{ccc}0.750 & -0.334 & -0.417\\ -0.334 & 0.667 & -0.333\\ -0.417 & -0.333 & 0.750\end{array}\right]$

gdzie jest macierzą Laplaciana . Zauważmy, że macierze i mają stopień 2, z zerowym wartości własnych odpowiadający wektor własny . $G$ $A$ $G$ $1_n=\left[\begin{array}{ccc}1 & 1 & 1\end{array}\right]^T$

Zastanawiam się, jaki byłby sposób na uzyskanie gdyby podano tylkoPróbowałem eigendecomposition , a następnie ustawiłem , ale inny wynik. Myślę, że ma to związek z niedoborem rang. Czy ktoś mógłby to wyjaśnić? Oczywiście powyższy przykład służy ilustracji; można rozważyć ogólny rozkład macierzy Laplaciana powyższej postaci. $A$ $G$ $G=UEU^T$ $A'=UE^{1/2}$

Ponieważ na przykład rozkład Cholesky'ego można wykorzystać do znalezienia , rozkład na może dać wiele rozwiązań. Ja zainteresowany w roztworze, który może być wyrażony jako gdzie to macierzy tożsamości, , a jedne wektor spełniające . Jeśli upraszcza to sprawy, możesz założyć, że wpisy są nieujemne. $G=LL^T$ $G$

A = (I - 1_{n} w^{T}),

$A=(I-1_nw^{T}),$

I

$I$

3 \times 3

$3\times 3$

1_{n} = [1 1 1]

$1_n=[1~ 1~ 1]$

w

$w$

w^{T} 1_{n} = 1

$w^T1_n=1$

w

$w$

linear-algebra matrix eigensystem

— usero
źródło

Myślę, że dodany komentarz na temat reprezentacji jest tylko częściowo pomocny. Zakłada się, że jest dokładnie jedna wartość własna równa zero, ale brak determinacji zawsze istnieje, prawda?

A

$A$

— Wolfgang Bangerth,

@WolfgangBangerth Staram się zrozumieć znaczenie „niedeterminacji”. Jeśli to , to odnosi się do powyższego przykładu, a nie jestem pewien, czy to może być uogólnione dla . Jednak z wyjątkiem wątpię, aby rozwiązanie zawsze istniało.

d e t (A) = 0

$det(A)=0$

A = I - 1_{n} w^{T}

$A=I-1_nw^T$

n = 3

$n=3$

— usero

Nie, miałem na myśli to, że rozwiązanie twojego problemu nie jest jednoznacznie określone. Zwracałem uwagę na fakt, że to, czy macierz ma zerową wartość własną, czy nie, tak naprawdę nie zmienia faktu, że problem pierwiastka kwadratowego nie ma unikalnego rozwiązania.

— Wolfgang Bangerth,

11

Mamy macierz Laplaciana która ma zestaw wartości własnych dla gdzie zawsze know . Zatem macierz Laplaciana jest zawsze symetryczna dodatnia półokreślona. Ponieważ macierz nie jest jednoznacznie symetryczna, musimy zachować ostrożność, omawiając rozkład Choleskiego. Rozkład Cholesky'ego istnieje dla dodatniej półokreślonej macierzy, ale nie jest już unikalny. Na przykład dodatnia półokreślona macierz ma nieskończenie wiele Rozkłady Choleskiego $G=A^TA$ $\lambda_0\leq\lambda_1\leq\ldots\leq \lambda_n$ $G\in\mathbb{R}^{n\times n}$ $\lambda_0 = 0$ $G$

A = [\begin{array}{cc} 0 & 0 \\ 0 & 1 \end{array}],

$A=\left[\!\!\begin{array}{cc} 0 & 0 \\ 0 & 1 \end{array} \!\!\right],$

A = [\begin{array}{cc} 0 & 0 \\ 0 & 1 \end{array}] = [\begin{array}{cc} 0 & 0 \\ \sin θ & \cos θ \end{array}] [\begin{array}{cc} 0 & \sin θ \\ 0 & \cos θ \end{array}] = L L^{T} .

$A=\left[\!\begin{array}{cc} 0 & 0 \\ 0 & 1 \end{array} \!\right] = \left[\!\begin{array}{cc} 0 & 0 \\ \sin\theta & \cos\theta \end{array} \!\right] \left[\!\begin{array}{cc} 0 & \sin\theta \\ 0 & \cos\theta \end{array} \!\right]=LL^T.$

Jednakże, ponieważ mamy macierz , który jest znany być Laplace'a matryca rzeczywiście możemy uniknąć bardziej wyrafinowanych narzędzi algebry liniowej jak dekompozycji Cholesky lub znalezienia pierwiastek kwadratowy z pozytywnym pół określonej macierzy takie, że możemy odzyskać . Na przykład, jeśli mamy macierz Laplace'a , możemy użyć teorii grafów do odzyskania pożądane matrycy . Robimy to, formułując zorientowaną matrycę występowania. Jeśli zdefiniujemy liczbę krawędzi na wykresie jako $G$ $G$ $A$ $G\in\mathbb{R}^{4\times 4}$

G = [\begin{array}{cccc} 3 & - 1 & - 1 & - 1 \\ - 1 & 1 & 0 & 0 \\ - 1 & 0 & 1 & 0 \\ - 1 & 0 & 0 & 1 \end{array}]

$G=\left[\!\begin{array}{cccc} 3 & -1 & -1 & -1\\ -1 & 1 & 0 & 0 \\ -1 & 0 & 1 & 0 \\ -1 & 0 & 0 & 1 \\ \end{array}\!\right]$

A

$A$

m

$m$ a liczba wierzchołków, które mają być a zorientowana macierz padania będzie macierzą podaną przez gdzie oznacza krawędź łączącą wierzchołki i . Jeśli weźmiemy wykres dla z czterema wierzchołkami i trzema krawędziami, otrzymamy zorientowaną macierz padania

n

$n$

A

$A$

m \times n

$m\times n$

A_{e v} = {\begin{array}{lc} 1 & if e = (v, w) and v < w \\ - 1 & if e = (v, w) and v > w \\ 0 & otherwise, \end{array}

$A_{ev} = \left\{\begin{array}{lc} 1 & \textrm{if }e=(v,w)\textrm{ and }v<w \\ -1 & \textrm{if }e=(v,w)\textrm{ and }v>w \\ 0 & \textrm{otherwise}, \end{array} \right.$

e = (v, w)

$e=(v,w)$

v

$v$

w

$w$

G

$G$

A = [\begin{array}{cccc} 1 & - 1 & 0 & 0 \\ 1 & 0 & - 1 & 0 \\ 1 & 0 & 0 & - 1 \end{array}],

$A = \left[\!\begin{array}{cccc} 1 & -1 & 0 & 0\\ 1 & 0 & -1 & 0 \\ 1 & 0 & 0 & -1 \\ \end{array}\!\right],$

G = A^{T} A

$G=A^TA$ . W przypadku problemu matrycy opisać byłoby skonstruować wykres dla w tej samej ilości, jak krawędzie wierzchołków, a następnie powinien mieć możliwość odtworzenia macierzy , gdy są podane jedynie laplasjan macierz .

G

$G$

A

$A$

G

$G$

Aktualizacja:

Jeśli zdefiniujemy macierz diagonalną stopni wierzchołków wykresu jako a macierz przyległości wykresu jako , to macierz Laplaciana na wykresie jest zdefiniowana przez . Na przykład na poniższym wykresie $N$ $M$ $G$ $G=N-M$

widzimy, że macierz Laplaciana to Teraz odnosimy do zorientowanej macierzy padania używając krawędzi i węzłów podanych na przedstawionym wykresie. Znów znajdujemy wpisy z

G = [\begin{array}{cccc} 3 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{array}] - [\begin{array}{cccc} 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{array}] .

$G=\left[\!\begin{array}{cccc} 3 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{array}\!\right] - \left[\!\begin{array}{cccc} 0 & 1 & 1 & 1\\ 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ \end{array}\!\right].$

G

$G$

A

$A$

A

$A$

A_{e v} = {\begin{array}{lc} 1 & if e = (v, w) and v < w \\ - 1 & if e = (v, w) and v > w \\ 0 & otherwise, \end{array} .

$A_{ev} = \left\{\begin{array}{lc} 1 & \textrm{if }e=(v,w)\textrm{ and }v<w \\ -1 & \textrm{if }e=(v,w)\textrm{ and }v>w \\ 0 & \textrm{otherwise}, \end{array} \right..$

e_{1}

$e_1$

v_{1}

$v_1$ i . Aby ustalić , zauważamy, że indeks jest mniejszy niż indeks (lub mamy przypadek w definicji ). Zatem . Podobnie, porównując indeksy, możemy znaleźć . Dajemy poniżej w bardziej wyraźny sposób, odnosząc się do pokazanych krawędzi i wierzchołków.

v_{2}

$v_2$

A_{e_{1}, v_{1}}

$A_{e_1,v_1}$

v_{1}

$v_1$

v_{2}

$v_2$

v < w

$v<w$

A_{e v}

$A_{ev}$

A_{e_{1}, v_{1}} = 1

$A_{e_1,v_1} = 1$

A_{e_{1}, v_{2}} = - 1

$A_{e_1,v_2} = -1$

A

$A$

A = \begin{array}{ccccc} v_{1} & v_{2} & v_{3} & v_{4} \\ e_{1} & 1 & - 1 & 0 & 0 \\ e_{2} & 1 & 0 & - 1 & 0 \\ e_{3} & 1 & 0 & 0 & - 1 \end{array} .

$A = \begin{array}{c|cccc} & v_1 & v_2 & v_3 & v_4 \\ \hline e_1 & 1 & -1 & 0 & 0\\ e_2 & 1 & 0 & -1 & 0 \\ e_3 & 1 & 0 & 0 & -1 \\ \end{array}.$

Następnie uogólniamy pojęcie macierzy Laplaciana na ważony niekierowany wykres. Niech będzie nieukierunkowym skończonym wykresem zdefiniowanym przez i jego wierzchołek i krawędź. Aby rozważyć ważony wykres, definiujemy funkcję wagi która przypisuje nieujemną wagę rzeczywistą do każdej krawędzi wykresu. Oznaczymy ciężar przypisany do krawędzi łączących wierzchołki i przez . W przypadku wykresu ważonego określamy stopień każdego wierzchołka jako sumę wszystkich ważonych krawędzi połączonych z , tj. $Gr$ $V$ $E$

w : V \times V \to R^{+},

$w: V\times V\rightarrow \mathbb{R}^+,$

u

$u$

v

$v$

w (u, v)

$w(u,v)$

u \in V

$u\in V$

u

$u$

d_{u} = \sum_{v \in V} w (u, v) .

$d_u = \sum_{v\in V}w(u,v).$ Z podanego wykresu możemy zdefiniować ważoną macierz przylegania jako z wierszami i kolumnami indeksowanymi przez których wpisy są podane przez . Niech będzie macierzą diagonalną indeksowaną przez ze stopniami wierzchołków na przekątnej, wtedy możemy znaleźć ważoną macierz Laplaciana tak jak przed

G r

$Gr$

A d (G r)

$Ad(Gr)$

n \times n

$n\times n$

V

$V$

w (u, v)

$w(u,v)$

D (G r)

$D(Gr)$

V

$V$

G

$G$

G = D (G r) - A d (G r) .

$G = D(Gr) - Ad(Gr).$

W problemie z oryginalnego postu wiemy, że Z znanych nam komentarzy szukamy faktoryzacji dla gdzie i określamy, że ma postać gdzie . Dla pełnej ogólności załóżmy, że macierz nie ma zerowych wpisów. Zatem jeśli sformułujemy macierz zorientowaną ważoną częstości występowania w celu znalezienia , potrzebujemy ważonej macierzy przyległości

G = [\begin{array}{ccc} \frac{3}{4} & - \frac{1}{3} & - \frac{5}{12} \\ - \frac{1}{3} & \frac{2}{3} & - \frac{1}{3} \\ - \frac{5}{12} & - \frac{1}{3} & \frac{3}{4} \end{array}] .

$G=\left[\!\begin{array}{ccc} \tfrac{3}{4} & -\tfrac{1}{3} & -\tfrac{5}{12} \\ -\tfrac{1}{3} & \tfrac{2}{3} & -\tfrac{1}{3} \\ -\tfrac{5}{12} & -\tfrac{1}{3} & \tfrac{3}{4} \\ \end{array}\!\right].$

G

$G$

G = A^{T} A

$G=A^TA$

A

$A$

A = I - 1_{n} w^{T}

$A=I-1_nw^T$

w^{T} 1_{n} = 1

$w^T1_n=1$

A

$A$

A

$A$

A d (G r)

$Ad(Gr)$ aby nie mieć również zerowych wpisów, tj. wykres ważony będzie miał pętle. Właściwie obliczenie ważonej zorientowanej macierzy częstości wydaje się trudne (chociaż może to wynikać z mojego braku doświadczenia z ważonymi wykresami). Możemy jednak znaleźć faktoryzację formy, której szukamy w sposób ad hoc, jeśli założymy, że wiemy coś o pętlach na naszym wykresie. Podzieloną ważoną macierz Laplaciana dzielimy na macierze stopnia i przylegania w następujący sposób

G

$G$

G = [\begin{array}{ccc} \frac{5}{4} & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & \frac{11}{12} \end{array}] - [\begin{array}{ccc} \frac{1}{2} & \frac{1}{3} & \frac{5}{12} \\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ \frac{5}{12} & \frac{1}{3} & \frac{1}{6} \end{array}] = D (G r) - A d (G r) .

$G=\left[\!\begin{array}{ccc} \tfrac{5}{4} & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & \tfrac{11}{12} \\ \end{array}\!\right]-\left[\!\begin{array}{ccc} \tfrac{1}{2} & \tfrac{1}{3} & \tfrac{5}{12} \\ \tfrac{1}{3} & \tfrac{1}{3} & \tfrac{1}{3} \\ \tfrac{5}{12} & \tfrac{1}{3} & \tfrac{1}{6} \\ \end{array}\!\right] = D(Gr)-Ad(Gr).$
Tak więc wiemy, że pętle na , i mają odpowiednio wagi , i . Jeśli umieścimy wagi na pętlach w wektorze = wówczas możemy odzyskać macierz którą chcemy w żądanej formie

v_{1}

$v_1$

v_{2}

$v_2$

v_{3}

$v_3$

1 / 2

$1/2$

1 / 3

$1/3$

1 / 6

$1/6$

w

$w$

[\frac{1}{2}

$[\frac{1}{2}$

\frac{1}{3}

$\frac{1}{3}$

\frac{1}{6}]^{T}

$\frac{1}{6}]^T$

A

$A$

A = I - 1_{n} w^{T} = [\begin{array}{ccc} \frac{1}{2} & - \frac{1}{3} & - \frac{1}{6} \\ - \frac{1}{2} & \frac{2}{3} & - \frac{1}{6} \\ - \frac{1}{2} & - \frac{1}{3} & \frac{5}{6} \end{array}] .

$A = I-1_nw^T = \left[\!\begin{array}{ccc} \tfrac{1}{2} & -\tfrac{1}{3} & -\tfrac{1}{6} \\ -\tfrac{1}{2} & \tfrac{2}{3} & -\tfrac{1}{6} \\ -\tfrac{1}{2} & -\tfrac{1}{3} & \tfrac{5}{6} \\ \end{array}\!\right].$

Okazuje się, że jeśli mamy wiedzę na temat pętli na naszym wykresie ważonym, możemy znaleźć macierz w pożądanej formie. Znów zostało to zrobione w sposób ad hoc (ponieważ nie jestem teoretykiem grafów), więc może to być hack, który zadziałał tylko dla tego prostego problemu. $A$

— Andrew Winters
źródło

Odzyskiwanie w przypadku Laplaciana jak to opisujesz , nie powinno stanowić problemu (w twoim przykładzie tylko jeden wiersz / kolumna zawiera niezerowe elementy). Myślę, że sprawy komplikują ogólny „pełny” Laplacian jak w moim przykładzie. Biorąc pod uwagę stopień swobody , nie jestem pewien, czy rozwiązanie można uzyskać, z zastrzeżeniem ograniczeń, które podam powyżej.

A

$A$

G

$G$

O (n^{2})

$O(n^2)$

G

$G$

— usero

Tak, przykład który podam, jest bardzo uproszczony, ale będzie to możliwe w ogólnym przypadku, gdy jest pełną matrycą. Problem teorii grafów staje się bardziej skomplikowany w miarę zwiększania liczby krawędzi i wierzchołków. Zasadniczo zastępujemy trudny problem faktoryzacji macierzy trudnym problemem teorii grafów.

G

$G$

G

$G$

— Andrew Winters,

Ok, będę wdzięczny, jeśli starają się zrekonstruować jak podano powyżej z danymi .

A

$A$

G

$G$

— usero

@AndrewWinters: Czy możesz wyjaśnić, w jaki sposób określa się podstawie ? Nie jest dla mnie jasne, jak działa twój algorytm w ogólnym przypadku.

A

$A$

G

$G$

— Geoff Oxberry

1

Nie sądzę, aby było to możliwe dla ogólnego ponieważ wydaje się, że specyficzna forma faktoryzacji będzie istnieć tylko dla niektórych typów wykresów ważonych. Zatem macierze Laplaciana które mają postać są podzbiorem wszystkich możliwych macierzy Laplaciana.

G

$G$

A = I - 1_{n} w^{T}

$A=I-1_nw^T$

G

$G$

G = A^{T} A = (I - 1_{n} w^{T})^{T} (I - 1_{n} w^{T})

$G=A^TA=(I-1_nw^T)^T(I-1_nw^T)$

— Andrew Winters,

9

Myślę, że są mylące wyjątkowy macierzy kwadratowych korzeń hermitowskiego pozytywny semi-definitywna macierzy , tj Hermitian pozytywny semi-definitywna macierz zaspokojenia, $A$ $B$

B^{2} = A,

$B^2 = A,$

z nie unikalnym problemem znalezienia macierzy spełniającej $C$

C^{H} C = A,

$C^H C = A,$

gdzie wyraźnie mapowanie , dla dowolnego jednolitego , zachowuje tożsamość. Jak zauważyłeś, faktoryzacja Cholesky'ego stanowi jedno z możliwych rozwiązań. Należy jednak pamiętać, że Cholesky działa tylko w przypadku pustelnikowo-dodatnich macierzy hermitowskich (z możliwym wyjątkiem Hermitianowskiej dodatniej półokreślonej macierzy, która jest dodatnio-dodatnia, jeśli ostatni wiersz i kolumna zostaną usunięte). $C \mapsto Q C$ $Q$

Na koniec można konstruktywnie zdefiniować unikalny pierwiastek kwadratowy macierzy Hermitian dodatniej półokreślonej macierzy poprzez jej rozkład wartości własnej, powiedzmy

A = U Λ U^{H},

$A = U \Lambda U^H,$

gdzie jest jednostkowe, a jest ukośna z nieujemnymi wpisami, ponieważ jest dodatnim półokreślonym. Pierwiastek kwadratowy macierzy hermitowskiej można łatwo zidentyfikować jako $U$ $\Lambda$ $A$

B = U \sqrt{Λ} U^{H} .

$B = U \sqrt{\Lambda} U^H.$

— Jack Poulson
źródło

Masz rację co do pierwiastka kwadratowego z macierzy . Oczywiście istnieją różne sposoby osiągnięcia faktoryzacji, ale mogą zagwarantować, że (z mojej wyprawy.) Może być napisane tak, jak sformułowałem.

A

$A$

— usero

6

W istocie to, o co prosisz, to znalezienie pierwiastka kwadratowego A macierzy G, tak aby Jest wiele sposobów na zrobienie tego, jeśli jest macierzą symetryczną. Na przykład, jeżeli jest symetryczne, a rozkład Cholesky'ego zapewnia z jednej odpowiedzi: . Ale już znalazłeś inną odpowiedź, z macierzą którą już masz. Oznacza to po prostu, że istnieje wiele „pierwiastków kwadratowych” macierzy , a jeśli chcesz mieć jeden konkretny, musisz ponownie sformułować pytanie w taki sposób, aby określić właściwości strukturalne „gałęzi” pierwiastek kwadratowy, który Cię interesuje.

G = A^{T} A .

$G = A^T A.$

G

$G$

G

$G$

G = L^{T} L

$G=L^TL$

A = L

$A=L$

A

$A$

G

$G$

Powiedziałbym, że ta sytuacja nie różni się od wyliczenia pierwiastka kwadratowego spośród liczb rzeczywistych za pomocą liczb zespolonych: tam też, ogólnie rzecz biorąc, masz dwa pierwiastki i musisz powiedzieć, która z nich ma uczynić odpowiedź unikalną.

— Wolfgang Bangerth
źródło

Zdecydowanie masz rację. Innym sposobem byłoby podejście do rozkładu widmowego, jak stwierdziłem powyżej. Dokonałem edycji, aby rozwiązanie było unikalne. Mam nadzieję, że to nie skomplikuje sprawy.

— usero

Czy zawsze istnieje rozwiązanie z ograniczeniem, które podam powyżej? Być może dotyczy to tylko niektórych przypadków, a nie ogólnie.

— usero

W rzeczywistości Cholesky nie działa w jego przypadku, ponieważ (zasadniczo) wymaga, aby matryca była pustelnikiem-dodatnim.

— Jack Poulson,

4

Myślę, że możesz zastosować faktoryzację do swojej macierzy A. Ponieważ macierz ma nie ujemne wartości własne, macierz diagonalna D będzie miała nieujemne wpisy wzdłuż przekątnej. Następnie możesz łatwo podzielić na czynniki pierwsze . I dostajesz macierz . Skład eigend nie jest stabilny numerycznie, więc myślę, że powinieneś unikać tego rodzaju rozkładu. $LDL^{T}$ $\hat{D} = \sqrt{D}$ $G = L\hat{D}$

— Willowbrook
źródło

Muszę się nie zgadzać z dwóch powodów: (1) faktoryzacja nie działa dla macierzy pojedynczych (jego macierz jest pojedyncza), oraz (2) rozkład wartości własnych macierzy hermitowskich jest uważany za stabilny, ponieważ ich macierze własne są jednolite.

L D L^{T}

$LDL^T$

— Jack Poulson,

1

@JackPoulson Próbuję pojedynczej macierzy A w Matlabie i uruchamiam ldl, to działa. Zerowe wartości własne odpowiadają zerom na przekątnej D.

— Willowbrook

2

Myślę, że przekonasz się, że procedura 'ldl' MATLAB-a oblicza dekompozycję bloku z przechylaniem , tj. , gdzie nie musi być ukośne (może mieć bloki). Aby uniknąć podziału przez zero, ponieważ macierz jest pojedyncza, zerowe wpisy po przekątnej są obracane w prawym dolnym rogu matrycy.

L D L^{T}

$LDL^T$

P A P^{'} = L D L^{T}

$PAP'=LDL^T$

D

$D$

2 \times 2

$2 \times 2$

— Jack Poulson,