Zufällige Matrizen mit Einschränkungen für die Zeilen- und Spaltenlänge

Ich muss zufällige, nicht quadratische Matrizen mit Zeilen und Spalten erzeugen , Elemente, die zufällig mit dem Mittelwert = 0 verteilt sind und so beschränkt sind, dass die Länge (L2-Norm) jeder Zeile und die Länge jeder Spalte beträgt $R$ $C$ $1$ . Entsprechend ist die Summe der Quadratwerte 1 für jede Zeile und $\sqrt{\frac{R}{C}}$ für jede Spalte. $\frac{R}{C}$

Bisher habe ich einen Weg gefunden, dies zu erreichen: einfach die Matrixelemente nach dem Zufallsprinzip zu initialisieren (z. B. aus einer gleichmäßigen, normalen oder Laplace-Verteilung mit einem Mittelwert von Null und einer willkürlichen Varianz) und dann abwechselnd Zeilen und Spalten auf normalisieren , endet mit der Zeilennormalisierung. Dies scheint ziemlich schnell zum gewünschten Ergebnis zu konvergieren (z. B. für und beträgt die Varianz der Spaltenlänge nach Iterationen in der Regel ~ ), aber ich bin nicht sicher, ob ich mich auf diese schnelle Konvergenzrate in verlassen kann allgemein (für verschiedene Matrixdimensionen und Anfangselementverteilungen). ${\rm length} = 1$ $R=40$ $C=80$ $~0.00001$ $2$

Meine Frage ist: ist es eine Möglichkeit , das gewünschte Ergebnis (zu erreichen , ${\rm row \ lengths} = 1$ ) direkt ohne Iteration zwischen Zeilen- / Spaltennormalisierung? ZB so etwas wie der Algorithmus zum Normalisieren eines Zufallsvektors (Elemente zufällig initialisieren, Summe der Quadratwerte messen, dann jedes Element mit einem gemeinsamen Skalar skalieren). Wenn nicht, gibt es eine einfache Charakterisierung für die Konvergenzrate (zB num Iterationenbis Fehler) des iterativen Verfahrens oben beschrieben? ${\rm column \ lengths} = \sqrt{\frac{R}{C}}$ $< \epsilon$

random-generation normalization markov-process random-matrix Tyler Streeter
quelle

Dies ähnelt dem Sinkhorn-Knopp-Algorithmus, der auch als iterative proportionale Anpassung bezeichnet wird.

Kardinal

Außerdem sollten Sie definieren, was Sie mit "zufälligen" Matrizen meinen. Zum Beispiel wird die von Ihnen beschriebene Prozedur (fast zweifellos) keine zufälligen Matrizen gleichmäßig über den gewünschten Raum erzeugen.

Kardinal

@ Kardinal Guter Punkt. Beachten Sie jedoch, dass Sie mindestens identische (marginale) Verteilungen für alle Komponenten erzielen können, indem Sie nachträglich mit einem Paar zufälliger Permutationsmatrizen multiplizieren (um sowohl Zeilen als auch Spalten zufällig anzuordnen).

whuber

@whuber: Ja, obwohl die gemeinsame Aufteilung noch recht seltsam sein könnte. Mit "Nachmultiplizieren" meine ich, links und rechts nach der Konvergenz zu multiplizieren (anstatt z. B. rechts zu multiplizieren).

Kardinal

Eigentlich denke ich, dass Ihr Algorithmus genau der Sinkhorn-Knopp-Algorithmus mit einer sehr geringen Modifikation ist. Sei

Ihre ursprüngliche Matrix und sei

eine Matrix der gleichen Größe, so dass

. Dann ist der Algorithmus äquivalent Anwendung Sinkhorn-Knopp bis

, wobei im letzten Schritt Sie die gewünschte Form gewinnen , indem man

X

$X$

Y

$Y$

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

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

Y

$Y$

. Die Konvergenz von Sinkhorn-Knopp ist nur unter pathologischen Umständen gewährleistet. Das Nachlesen sollte sehr hilfreich sein.

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

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

Kardinal

Wie @ cardinal in einem Kommentar sagte:

Eigentlich denke ich, dass Ihr Algorithmus genau der Sinkhorn-Knopp-Algorithmus mit einer sehr geringen Modifikation ist. Sei Ihre ursprüngliche Matrix und sei eine Matrix der gleichen Größe, so dass . Dann ist der Algorithmus äquivalent Anwendung Sinkhorn-Knopp bis , wobei im letzten Schritt Sie die gewünschte Form gewinnen , indem man $X$ $Y$ $Y_{ij}=X^2_{ij}$ $Y$ . Die Konvergenz von Sinkhorn-Knopp ist nur unter pathologischen Umständen gewährleistet. Das Nachlesen sollte sehr hilfreich sein. $\hat{X}_{ij}=sgn(X_{ij})\sqrt{Y_{ij}}$

... der iterative Algorithmus, den ich in der ursprünglichen Frage vorgeschlagen habe, scheint dem Sinkhorn-Knopp-Algorithmus sehr ähnlich zu sein. Interessanterweise scheint es auch der iterativen proportionalen Anpassung (IPF) sehr ähnlich zu sein , die, wie auf der IPF-Wikipedia-Seite beschrieben, mit Newtons Methode und Erwartungsmaximierung zusammenhängt (alle haben das gleiche Limit).

Diese iterativen Methoden werden häufig auf Probleme angewendet, bei denen keine geschlossene Lösung vorliegt. Daher gehe ich versuchsweise davon aus, dass die Antwort auf die Frage negativ ist: Es gibt keine Möglichkeit, die gewünschte Lösung ohne Zeilen- / Spalteniteration zu erzielen.

Tyler Streeter
quelle

(+1) Für Ihr anhaltendes Interesse an dieser Frage und Ihr unabhängiges Follow-up. :-)

Kardinal

Zufällige Matrizen mit Einschränkungen für die Zeilen- und Spaltenlänge

Antworten: