Losowe macierze z ograniczeniami długości wierszy i kolumn

Muszę wygenerować losowe macierze nie kwadratowe z wierszami i kolumnami , elementy losowo rozmieszczone ze średnią = 0 i ograniczone tak, że długość (norma L2) każdego wiersza wynosi a długość każdej kolumny wynosi $R$ $C$ $1$ . Odpowiednio suma wartości kwadratowych wynosi 1 dla każdego wiersza i $\sqrt{\frac{R}{C}}$ $\frac{R}{C}$ dla każdej kolumny.

Do tej pory znalazłem jeden sposób, aby to osiągnąć: po prostu zainicjuj elementy macierzy losowo (np. Z rozkładu równomiernego, normalnego lub laplace'a z zerową średnią i dowolną wariancją), a następnie naprzemiennie normalizuj wiersze i kolumny, aby , kończąc na normalizacji wiersza. Wydaje się, że dość szybko zbliża się do pożądanego wyniku (np. Dla i , wariancja długości kolumny wynosi zwykle ~ po iteracjach), ale nie jestem pewien, czy mogę polegać na tym szybkim współczynniku zbieżności w ogólne (dla różnych wymiarów macierzy i początkowych rozkładów elementów). ${\rm length} = 1$ $R=40$ $C=80$ $~0.00001$ $2$

Moje pytanie brzmi: czy istnieje sposób na osiągnięcie pożądanego rezultatu ( , ${\rm row \ lengths} = 1$ ) bezpośrednio, bez iteracji między normalizacją wiersza / kolumny? Np. Algorytm normalizujący losowy wektor (inicjowanie elementów losowo, pomiar sumy wartości kwadratowych, a następnie skalowanie każdego elementu za pomocą wspólnego skalara). Jeśli nie, to czy istnieje prosta charakterystyka współczynnika konwergencji (np. Liczba iteracji aż do błędu) metody iteracyjnej opisanej powyżej? ${\rm column \ lengths} = \sqrt{\frac{R}{C}}$ $< \epsilon$

random-generation normalization markov-process random-matrix Tyler Streeter
źródło

Jest to dość podobne do algorytmu Sinkhorn-Knopp, znanego również jako iteracyjne dopasowanie proporcjonalne.

kardynał

Powinieneś także zdefiniować, co rozumiesz przez „losowe” macierze. Na przykład opisana procedura (prawie bez wątpienia) nie wytworzy losowo macierzy jednorodnie w pożądanej przestrzeni.

kardynał

@cardinal Dobra uwaga. Należy jednak pamiętać, że można uzyskać co najmniej identyczne (marginalne) rozkłady dla wszystkich składników, mnożąc po przez parę losowych macierzy permutacji (aby losowo rozmieścić zarówno wiersze, jak i kolumny).

whuber

@whuber: Tak, chociaż wspólna dystrybucja może być nadal dość dziwna. Przez „mnożenie po” zakładam, że masz na myśli mnożenie po lewej i prawej „po zbieżności” (zamiast np. Mnożenie po prawej).

kardynał

Właściwie, po krótkiej przemyśleniu, myślę, że algorytm jest dokładnie algorytmem Sinkhorn-Knopp z bardzo niewielką modyfikacją. Niech

będzie twoją oryginalną macierzą, a

niech będzie macierzą tego samego rozmiaru, tak że

. Następnie algorytmu jest równoważne zastosowaniu Sinkhorn-Knopp do

, w którym w ostatnim kroku odzyskania pożądanego kształtu poprzez

X

$X$

Y

$Y$

Y_{i j} = X_{i j}^{2}

$Y_{ij} = X_{ij}^2$

Y

$Y$

. Sinkhorn-Knopp gwarantuje zbieganie się, z wyjątkiem dość patologicznych okoliczności. Czytanie tego powinno być bardzo pomocne.

{\hat{X}}_{i j} = s g n (X_{i j}) \sqrt{Y_{i j}}

$\hat{X}_{ij} = \mathrm{sgn}(X_{ij}) \sqrt{Y_{ij}}$

kardynał

Jak powiedział @cardinal w komentarzu:

Właściwie, po krótkiej przemyśleniu, myślę, że algorytm jest dokładnie algorytmem Sinkhorn-Knopp z bardzo niewielką modyfikacją. Niech X będzie twoją oryginalną macierzą, a Y niech będzie macierzą tego samego rozmiaru, tak że Y i j = X 2 i j . Następnie algorytmu jest równoważne zastosowaniu Sinkhorn-Knopp do Y , w którym w ostatnim kroku odzyskania pożądanego kształtu poprzez X i J = y g n ( X i j ) $X$ $Y$ $Y_{ij}=X^2_{ij}$ $Y$ $\hat{X}_{ij}=sgn(X_{ij})\sqrt{Y_{ij}}$

... wydaje się, że iteracyjny algorytm, który zasugerowałem w pierwotnym pytaniu, jest bardzo podobny do algorytmu Sinkhorn-Knopp. Co ciekawe, wydaje się również bardzo podobny do iteracyjnego dopasowania proporcjonalnego (IPF), które, jak opisano na stronie wikipedii IPF, jest związane z metodą Newtona i maksymalizacją oczekiwań (wszystkie mają ten sam limit).

Te metody iteracyjne są często stosowane do problemów, które nie mają rozwiązania w formie zamkniętej, więc wstępnie założę, że odpowiedź na pytanie jest przecząca: nie ma sposobu na osiągnięcie pożądanego rozwiązania bez iteracji wierszy / kolumn.

Tyler Streeter
źródło

(+1) Za ciągłe zainteresowanie tym pytaniem i niezależne działania następcze. :-)

kardynał

Losowe macierze z ograniczeniami długości wierszy i kolumn

Odpowiedzi: