Liczba warunkowa preparatów A'A i AA '

9

Pokazano (Yousef Saad, Iteracyjne metody dla rzadkich układów liniowych , s. 260), które $cond(A'A) \approx cond(A)^2$

Czy dotyczy to również ? $AA'$

W przypadku, gdy jest z , obserwuję, że $A$ $N\times M$ $N \ll M$ $cond(A'A) \gg cond(AA')$

Czy to oznacza, że w tym przypadku preferowane jest sformułowanie w kategoriach $AA'$ ?

linear-algebra condition-number Alexander
źródło

2

Porównujesz liczby warunków dwóch macierzy o bardzo różnych rozmiarach. Bez wyjaśnienia dlaczego wydaje się, że to porównanie prawdopodobnie nie ma znaczenia. Oczywiście, jeśli możesz osiągnąć to, czego potrzebujesz, używając znacznie mniejszej matrycy, powinieneś (nawet jeśli warunkowanie było podobne).

David Ketcheson

1

Nowa odpowiedź Stefano M poniżej jest poprawna. Proszę przeczytać i zagłosować.

David Ketcheson

6

Jeśli z , to tak że nie może mieć pełnej rangi, tzn. jest liczbą pojedynczą. $A\in\mathbb{R}^{N\times M}$ $N<M$

r a n k (A^{T} A) = r a n k (A A^{T}) = r a n k (A) \leq N < M

$\mathop{\mathrm{rank}}(A^TA) = \mathop{\mathrm{rank}}(AA^T) = \mathop{\mathrm{rank}}(A) \leq N < M$

A^{T} A \in R^{M \times M}

$A^TA \in \mathbb{R}^{M\times M}$

Odpowiednio, warunkiem jest . Ze względu na skończoną precyzję arytmetyki, jeśli obliczasz w Matlabie, otrzymujesz dużą liczbę, a nie . $\kappa_2(A^TA)=\infty$ cond(A'A)Inf

Stefano M.
źródło

@OscarB: wartości w liczbie pojedynczej to tylko , nie ma czegoś takiego jak ta liczba osobliwa! Twoje wyprowadzenie jest prawidłowe, ale pamiętaj, że jeśli , są sv , to , podczas gdy z końcowymi zerami .

A

$A$

N

$N$

M

$M$

σ_{i}

$\sigma_i$

i = 1 \dots N

$i=1\dots N$

A

$A$

S S^{T} = d i a g (σ_{1}^{2}, \dots, σ_{n}^{2})

$SS^T=\mathop{\mathrm{diag}}(\sigma_1^2,\dots,\sigma_n^2)$

S^{T} S = d i a g (σ_{1}^{2}, \dots, σ_{n}^{2}, 0, \dots, 0)

$S^TS = \mathop{\mathrm{diag}}(\sigma_1^2,\dots,\sigma_n^2, 0, \dots, 0)$

M - N

$M-N$

Stefano M

8

Cóż, wygląd Spójrzmy prawdzie w dlaczego ma w przybliżeniu kwadrat o liczbę warunek . Używając rozkładu SVD , z , , , możemy wyrazić jako $A^TA$ $A$ $A=USV^T$ $U \in \mathbb{R}^{N \times N}$ $S \in \mathbb{R}^{N \times M}$ $V \in \mathbb{R}^{M \times M}$ $A^T A$

$A^T A=(USV^T)^T USV^T=VS^T U^T U S V^T=V S^T S V^T$

Które otrzymujemy od stwierdzenia, że jest ortonormalna takie, że . Ponadto zauważamy, że jest macierzą diagonalną, tak że ostateczny rozkład można wyrazić jako , przy czym oznacza , otrzymując macierz diagonalną z pierwszymi N liczbą pojedynczą z kwadracie po przekątnej. Oznacza to, że ponieważ liczba warunków jest stosunkiem pierwszej i ostatniej liczby pojedynczej, dla , $U$ $U^T U=I$ $S$ $A^TA$ $V S^2 V^T$ $S^2$ $S^T S$ $S$ $cond(A)=\frac{s_1}{s_N}$ $A \in \mathbb{R}^{N \times M}$

$cond(A^T A)=\frac{s_1^2}{s_M^2}=(\frac{s_1}{s_M})^2=cond(A)^2$

Teraz możemy wykonać to samo ćwiczenie z : $AA^T$

$AA^T=USV^T (USV^T)^T=USV^T V S^T U^T=U S^2 U^T$

Co oznacza, że otrzymujemy wynik , ponieważ tutaj oznacza , subtelną różnicę w stosunku do powyższej notacji. $cond(AA^T)=\frac{s_1^2}{s_N^2}$ $S^2$ $SS^T$

Ale zauważ tę subtelną różnicę! Dla liczba warunków ma M-tą liczbę pojedynczą w mianowniku, podczas gdy ma N-tą liczbę pojedynczą. To wyjaśnia, dlaczego widzisz znaczące różnice w liczbie warunków - będzie rzeczywiście „lepiej uwarunkowany” niż . $A^TA$ $AA^T$ $AA^T$ $A^TA$

Mimo to David Ketcheson miał rację - porównujesz liczby warunków między dwiema zupełnie różnymi macierzami. W szczególności, co można osiągnąć z nie będzie takie samo jak to, co można osiągnąć z . $A^TA$ $AA^T$

OscarB
źródło

To świetne wytłumaczenie! Teraz wyraźnie widzę różnicę. Macierz A służy do budowania równań normalnych i przy niewielkich zmianach można również sformułować ją jako , a nie klasyczny . Czy możesz również powiedzieć, czy korzystniejsze jest użycie solvera takiego jak LSQR zamiast rozwiązywania normalnych równań? Ponieważ LSQR wcale nie wymaga budowania tego produktu.

A A^{'}

$AA'$

A^{'} A

$A'A$

Alexander

Cieszę się, że to miało sens. Ogólnie rzecz biorąc, należy wziąć pod uwagę uwarunkowanie problemu. Ale jeśli to nie jest problem, możesz użyć albo normalnych równań / faktoryzacji QR (z A) / LSQR, w zależności od wielkości problemu (między innymi). O ile twój problem nie jest duży lub źle uwarunkowany, prawdopodobnie zastosowałbym faktoryzację QR, ale bez większej wiedzy o problemie, który próbujesz rozwiązać, trudno powiedzieć. Jestem pewien, że inni z większym doświadczeniem mogą udzielić bardziej szczegółowych porad.

OscarB

Samo A jest źle uwarunkowane (z liczbą warunków ), gęste i duże. QR nie jest opcją. Ponieważ jest to źle uwarunkowane, muszę dodać trochę regularyzacji. Teraz wydaje się, że wystarczy zwykła regularyzacja Tichonowa. Chodzi o to, że jeśli (w moim przypadku z ), to użycie LSQR wydaje się zawsze preferowane, ponieważ nie musisz tworzyć żadnego produktu w wszystko. Pytanie brzmi, czy rozwiązania uzyskane przy pomocy równań normalnych i LSQR są identyczne?

\approx 10^{7}

$\approx 10^7$

c o n d (A) < c o n d (A A^{T}) < c o n d (A^{T} A)

$cond(A) < cond(AA^T) < cond(A^T A)$

N < M

$N < M$

Alexander

Cóż, jak rozumiem, LSQR zapewni identyczne rozwiązanie normalnych równań po „nieskończenie wielu” iteracjach z dokładną dokładnością. Jednak w przypadku źle postawionych problemów normalne rozwiązanie równań nie jest tym, czego chcesz. Zamiast tego chcesz używać LSQR do iteracji aż do osiągnięcia półkonwergencji. Jednak kontrolowanie algorytmów iteracyjnych w źle postawionych problemach to zupełnie inna gra w piłkę. Ponadto, w zależności od kosztu produktu macierzy-wektora i liczby potrzebnych iteracji (a tym samym matveców), bezpośrednie rozwiązanie Tichonowa z bidiagonalizacją może być lepsze.

OscarB

Niesamowite wyjaśnienie. +1 dla pana!

meawoppl,

2

Twierdzenie, że (dla macierzy kwadratowych) ~~w pytaniu i~~ [Edycja: źle odczytałem] w odpowiedzi Artana jest nonsensowne. Kontrprzykład $\DeclareMathOperator{\cond}{cond} \cond A^2 \approx \cond A^T A$

A = (\begin{matrix} ϵ & 1 \\ 0 & ϵ \end{matrix}), ϵ ≪ 1

$\newcommand\bigO{\mathcal{O}}A = \begin{pmatrix} \epsilon & 1 \\ 0 & \epsilon \end{pmatrix}, \quad \epsilon \ll 1$

dla których możesz łatwo sprawdzić, czy podczas gdy . $\cond A^T A = \bigO(\epsilon^{-4})$ $\cond A^2 = \bigO(\epsilon^{-2})$

Jed Brown
źródło

Ok, aby podkreślić, że i są na ogół bardzo odmienne w odniesieniu do eigs, svds, cond number: ale moim zdaniem pytanie to dotyczy .

A^{2}

$A^2$

A^{T} A

$A^T A$

[c o n d (A)]^{2}

$[\mathrm{cond}(A)]^2$

Stefano M

@StefanoM Dzięki, wydaje mi się, że źle odczytałem, choć z dyskusji, nie był jedyny.

Jed Brown

1

Dokładnie arytmetyczny cond (A ^ 2) = cond (A'A) = cond (AA '), patrz np. Golub i van Loan, 3. wydanie, str. 70. Nie jest to prawdą w przypadku arytmetyki zmiennoprzecinkowej, jeśli A ma prawie niedobór rangi. Najlepiej jest postępować zgodnie z powyższymi przepisami przy rozwiązywaniu najmniejszych kwadratowych problemów, najbezpieczniejszym jest podejście SVD, str. 257. Zamiast tego używaj \ varepsilon-rank podczas obliczania SVD, gdzie \ varepsilon jest rozdzielczością danych macierzy.

Artan
źródło

Przepraszam, spojrzałem na Goluba i Van Loana 3. ed str. 70, i nie mogłem znaleźć niczego, co tworzy kopię instrukcji cond (A ^ 2) = cond (A ^ TA) = cond (AA ^ T). Czy mógłbyś być bardziej szczegółowy w odniesieniu do swojego odniesienia?

OscarB

Nie ma tam żadnego zdania, ale można wywnioskować z twierdzenia 2.5.2 i pseudoinwersji, sekcja 5.5.4, że cond (AA ') = cond (A'A). Powodem, dla którego biorę pseudo-odwrotność, jest to, że ma to znaczenie dla problemu najmniejszych kwadratów. Równość po warunku (A ^ 2) powinna wynosić \ ok, przepraszam za literówkę.

Artan,

Nie, ta odpowiedź jest całkowicie niepoprawna. Zobacz mój kontrprzykład.

Jed Brown

Saad musiał zwrócić uwagę na jakiś konkretny kontekst. Dla omawianego pytania istotny jest przebieg postępowania.

Artan,

Liczba warunkowa preparatów A'A i AA '

Odpowiedzi: