Ile regulacji należy dodać, aby zapewnić stabilność SVD?

10

Korzystałem z SVD Intela MKL ( dgesvdprzez SciPy) i zauważyłem, że wyniki są znacząco różne, kiedy zmieniam precyzję pomiędzy float32i float64kiedy moja matryca jest źle uwarunkowana / nie w pełni ustawiona. Czy istnieje przewodnik dotyczący minimalnej ilości regularyzacji, którą powinienem dodać, aby wyniki były niewrażliwe na float32-> float64zmianę?

W szczególności robienie A=UDVT, Widzę to L norma VTXprzesuwa się o około 1, gdy zmieniam precyzję pomiędzy float32i float64.L2 norma A jest 105 i ma około 200 zerowych wartości własnych z 784 ogółem.

Włączanie SVD λI+A z λ=103 sprawiło, że różnica zniknęła.

Jarosław Bułatow
źródło
Jaki jest rozmiar N z N×N matryca Adla tego przykładu (czy to w ogóle macierz kwadratowa)? 200 zerowych wartości własnych czy pojedynczych wartości? Norma Frobeniusa||A||Fna reprezentatywny przykład byłby również pomocny.
Anton Menshov
W tym przypadku macierz 784 x 784, ale bardziej interesuje mnie ogólna technika znalezienia dobrej wartości lambda
Jarosław Bułatow
Więc jest różnica w Vtylko w ostatnich kolumnach odpowiadających zerowym wartościom pojedynczym?
Nick Alger
2
Jeśli istnieje kilka równych wartości pojedynczych, svd nie jest unikalny. W twoim przykładzie wydaje mi się, że problem pochodzi z wielu zerowych wartości pojedynczych i że inna precyzja prowadzi do innego wyboru podstawy dla odpowiedniej liczby pojedynczej. Nie wiem, dlaczego to się zmienia, kiedy regulujesz ...
Dirk
1
...co jest X?
Federico Poloni

Odpowiedzi:

1

Chociaż pytanie ma świetną odpowiedź, oto ogólna zasada dla małych pojedynczych wartości z fabułą.

Jeśli pojedyncza wartość jest niezerowa, ale bardzo mała, należy zdefiniować jej odwrotność jako zero, ponieważ jej pozorna wartość jest prawdopodobnie artefaktem błędu zaokrąglenia, a nie znaczącą liczbą. Prawdopodobna odpowiedź na pytanie „jak mały jest mały?” polega na edycji w ten sposób wszystkich pojedynczych wartości, których stosunek do największej jest mniejszy niżN razy dokładność maszyny ϵ .

- Przepisy numeryczne str. 795

Dodano: poniższe kilka linii oblicza tę zasadę.

#!/usr/bin/env python2

from __future__ import division
import numpy as np
from scipy.sparse.linalg import svds  # sparse, dense or LinOp

#...............................................................................
def howsmall( A, singmax=None ):
    """ singular values < N float_eps sing_max  may be iffy, questionable
        "How small is small ?"
        [Numerical Recipes p. 795](http://apps.nrbook.com/empanel/index.html?pg=795)
    """
        # print "%d singular values are small, iffy" % (sing < howsmall(A)).sum()
        # small |eigenvalues| too ?
    if singmax is None:
        singmax = svds( A, 1, return_singular_vectors=False )[0]  # v0=random

    return max( A.shape ) * np.finfo( A.dtype ).eps * singmax


Macierz Hilberta wydaje się być szeroko stosowana jako przypadek testowy dla błędu zaokrąglenia:

wprowadź opis zdjęcia tutaj

Tutaj bity niskiego rzędu w mantysach macierzy Hilberta są zerowane A.astype(np.float__).astype(np.float64), a następnie np.linalg.svdsą wprowadzane float64. (Wyniki dla svdwszystkich float32są prawie takie same.)

Po prostu obcięcie do float32może być nawet przydatne do odrzucania danych wielowymiarowych, np. Do klasyfikacji pociągu / testu.

Prawdziwe przypadki testowe byłyby mile widziane.

denis
źródło
btw, scipy wydaje się dodawać współczynnik 1e3 dla float32 i 1e6 dla float64, ciekawe, skąd one pochodzą
Jarosław Bułatow
@Yaroslav Bulatov numpyi scipy.linalg.svdwywołaj LAPACK gesdd , patrz parametr JOBRw dgejsv: „Określa ZAKRES dla wartości w liczbie pojedynczej. Wydaje licencję na zerowanie małych dodatnich wartości w liczbie pojedynczej, jeśli są poza ...” ( scipy.sparse.linalg.svdsotacza ARPACK i ma parametr tolTolerancja dla pojedynczych wartości.)
den
13

Dekompozycja wartości osobliwych dla macierzy symetrycznej A=AT jest taki sam jak jego kanoniczny skład eigend (tj. z ortonormalną matrycą wektorów własnych), podczas gdy to samo dotyczy macierzy niesymetrycznej M=UΣVT jest tylko kanonicznym rozkładem wartości własnej macierzy symetrycznej

H=[0MMT0]=[U00V][0ΣΣ0][U00V]T
Zatem bez utraty ogólności rozważmy ściśle powiązane pytanie: jeśli dwie macierze symetryczne są w przybliżeniu takie same, to czy powinniśmy oczekiwać, że ich kanoniczne składy eigend będą w przybliżeniu takie same?

Odpowiedź brzmi zaskakująco nie. Pozwolićϵ>0 bądź mały i rozważ dwie matryce

Aϵ=[1ϵϵ1]=VΛϵVT,Bϵ=[1+ϵ001ϵ]=UΛϵUT
oba mają wartości własne Λϵ=diag(1+ϵ,1ϵ), ale których wektorami własnymi są
V=12[1111],U=[1001].
Podczas gdy matryce AϵBϵ są w przybliżeniu takie same, ich matryce wektorów własnych V i Usą bardzo różne. Rzeczywiście, ponieważ kompozycje eigend są wyjątkoweϵ>0, naprawdę nie ma wyboru U,V takie, że UV

Teraz, stosując tę ​​wiedzę z powrotem do SVD ze skończoną precyzją, napiszmy M0=U0Σ0V0Tjako float64 precyzyjna matryca , orazMϵ=UϵΣϵVϵT jak ta sama matryca w float32precyzji. Jeśli założymy, że same SVD są dokładne, to liczby osobliweΣ0,Σϵ musi różnić się nie więcej niż małym stałym współczynnikiem wynoszącym ϵ107, ale pojedyncze wektory U0,Uϵ i V0,Vϵ może różnić się dowolnie dużą ilością. Dlatego, jak pokazano, nie ma sposobu, aby SVD była „stabilna” w sensie pojedynczych wektorów.

Richard Zhang
źródło
Czy ten przykład pochodzi z: users.math.msu.edu/users/markiwen/Teaching/MTH995/Papers/… ?
Memming
1
To świetny przykład. Nie wiem, tego konkretnego przykładu nauczyłem się wiele lat temu na lekcji matematyki :-)
Richard Zhang