Przestrzeń zerowa prostokątnej gęstej matrycy

Biorąc pod uwagę gęstą macierz jaki jest najlepszy sposób na znalezienie podstawy zerowej w granicach tolerancji ?

A \in R^{m \times n}, m >> n; m a x (m) \approx 100000

$A \in R^{m \times n}, m >> n; max(m) \approx 100000$

ϵ

$\epsilon$

Czy na tej podstawie mogę powiedzieć, że niektóre cols są liniowo zależne od ? Innymi słowy, po obliczeniu podstawy zerowej przestrzeni, jakie kolumny należy usunąć, aby uzyskać macierz niesingularną? $\epsilon$ $A$

Referencje są mile widziane.

linear-algebra Alexander
źródło

Odpowiedzi:

Standardowe metody określania pustej przestrzeni macierzy to wykorzystanie rozkładu QR lub SVD. Jeśli dokładność jest najważniejsza, preferowane jest SVD; rozkład QR jest szybszy.

Używając SVD, jeśli , to kolumny odpowiadające małym pojedynczym wartościom (tj. Małym ukośnym wpisom ) stanowią podstawę dla przestrzeni zerowej. Odpowiednią tolerancją jest tutaj to, co uważa się za „małą” wartość pojedynczą. Na przykład MATLAB zajmuje małą wartość , gdzie jest związany z dokładnością maszyny (patrz tutaj w dokumentacji MATLAB ). $A = U\Sigma V^{H}$ $V$ $\Sigma$ $\max(m,n) \cdot \varepsilon$ $\varepsilon$

Używając rozkładu QR, jeśli , a ranga jest , to ostatnie kolumny tworzą pustą przestrzeń , zakładając, że rozkład QR ujawnia rangę. Aby wyznaczyć , obliczyć liczbę wpisów na głównej przekątnej których wielkość przekracza tolerancję (podobną do tej stosowanej w podejściu SVD). $A^{T} = QR$ $A$ $r$ $n-r$ $Q$ $A$ $r$ $R$

Nie używaj rozkładu LU. Dokładnie w arytmetyce jest to realne podejście, ale w przypadku arytmetyki zmiennoprzecinkowej nagromadzenie błędów numerycznych czyni ją niedokładną.

Wikipedia obejmuje te tematy tutaj .

Geoff Oxberry
źródło

Geoff, mówiąc w kategoriach QR, przypuśćmy, że mam rozkład, w jaki sposób powiązać podstawę zerową i kolumny w oryginalnej macierzy? Innymi słowy, jakie kolumny powinienem usunąć z

, aby pozbyć się pustego miejsca? Chodzi tutaj o pracę z samym

, a nie z jego rozkładem.

A

$A$

A

$A$

Alexander

Procedury, które obliczają rozkład QR zwykle zawierają opcję zwrócenia wektora permutacji wskazującego sposób permutacji kolumn w celu uzyskania faktoryzacji QR. Ostatnie

wpisy tego permutacji wektora odpowiadałaby wierszy

(kolumny z

), które znajdują się w nullspace. Pierwsza

Wpisy tego wektora odpowiadają kolumny

, które są liniowo niezależne. Nie jestem pewien, co masz na myśli mówiąc „pozbyć się pustego miejsca”. Czy masz na myśli, że chcesz usunąć kolumny

aby uzyskać macierz niesingularną?

n - r

$n-r$

A

$A$

A^{T}

$A^{T}$

r

$r$

A^{T}

$A^{T}$

A

$A$

Geoff Oxberry,

Tak, mam na myśli to. Popatrzę na permutację, dzięki.

Alexander

To jest inne pytanie. Co byś wtedy zamiast zrobić to obliczyć QR rozkładowi (lub SVD) z

. Jeśli obliczasz rozkład QR dla

, możesz obliczyć rangę

jak w powyższej odpowiedzi (nie trzeba transponować macierzy), a następnie pierwsze wpisy

(gdzie

jest rangą

) wektora permutacji odpowiadają do niezależnych kolumnach

. Ten sam rodzaj algorytmu dotyczy SVD; jeśli możesz zwrócić wektor permutacji wraz z rozkładem, powinno to dostarczyć niezbędnych informacji.

A

$A$

A

$A$

A

$A$

r

$r$

r

$r$

A

$A$

A

$A$

Geoff Oxberry,

Jeśli , jak Twoje pytanie wskazuje, można zaoszczędzić trochę pracy przez pierwsze zbieranie indeks ustawiony z (powiedzmy) losowych wierszy i używając prostopadły faktoryzacji . (Faktoryzacja QR to ta, w której jest kwadratem, a jest prostokątem o randze , a pozostałe kolumny wynoszą zero. Użycie permutacji faktoryzacji QR zwiększy stabilność; permutacja musi być następnie uwzględniona w bardziej szczegółowy przepis.) $m\gg n$ $I$ $p\approx 5n$ $A_{I:}^T=QR$ $Q$ $R$ $r$ $n-r$ $R$

Zazwyczaj będzie to daje znacznie niższe wymiarowej podprzestrzeni łączony przez kolumny , ostatnie kolumny . To podprzestrzeń zawiera przestrzeń NULL . Teraz wybierz inny, losowy zbiór rozłączny indeksu i obliczyć QR faktoryzacji . Pomnóż wynikową pustą przestrzeń po lewej stronie przez aby uzyskać lepszą o prawdopodobnie jeszcze niższym wymiarze. Iteruj, aż wymiar nie będzie się już zmniejszał. Wtedy prawdopodobnie masz poprawną pustą przestrzeń i możesz to sprawdzić, obliczając $N$ $n-r$ $Q$ $A$ $(A_{I:}N)^T$ $N$ $N$ $N$ $AN$ . Jeśli nie jest to jeszcze nieistotne, wykonaj kolejne iteracje z najbardziej znaczącymi wierszami.

Edycja: Gdy masz , możesz znaleźć maksymalny zestaw liniowo niezależnych kolumn przez ortogonalne rozkładanie z obrotem. Rzeczywiście, zestaw indeksów niewybranych jako osie przestawne będzie miał tę właściwość. $N$ $J$ $A$ $N^T=QR$ $J$

Arnold Neumaier
źródło

+1 za skuteczny sposób na określenie pustej przestrzeni dużej macierzy. Będę musiał pamiętać o zapoznaniu się z tą odpowiedzią później, kiedy będę jej potrzebować.

Geoff Oxberry,

Rzeczywiście, to brzmi rozsądnie, jednak moje matryce mieszczą się w 16 GB pamięci RAM, więc pozostałbym przy standardowym matlabie qr.

Alexander

Prof. Neumaier, postanowiłem przetestować ten algorytm, ale nie rozumiem dokładnie, co to jest

i co oznacza „obliczanie faktoryzacji QR dla

”? Czy mógłbyś wyjaśnić nieco więcej.

N

$N$

(A_{I :} N)^{T}

$(A_{I:}N)^T$

Alexander

Trochę zredagowałem swoją odpowiedź.

oblicza się według przepisu Geoffa Oxberry.

N

$N$

Arnold Neumaier

Dziękuję Ci. Zaimplementowałem to. Jednakże, o ile widzę, to algorytm nie pozwala zdefiniować mi zbiór liniowo niezależnych kolumn

(ponieważ rozkładają

zamiast

), ale po prostu pomaga oszacować podstawę nullspace sama?

A

$A$

A_{I :}^{T}

$A_{I:}^T$

A_{I :}

$A_{I:}$

Alexander