Matrices aleatorias con restricciones en la longitud de la fila y la columna

Necesito generar matrices aleatorias no cuadradas con filas y columnas , elementos distribuidos aleatoriamente con media = 0, y restringidos de modo que la longitud (norma L2) de cada fila sea y la longitud de cada columna sea . De manera equivalente, la suma de los valores cuadrados es 1 para cada fila y para cada columna. $R$ $C$ $1$ $\sqrt{\frac{R}{C}}$ $\frac{R}{C}$

Hasta ahora, he encontrado una manera de lograr esto: simplemente inicialice los elementos de la matriz al azar (por ejemplo, desde una distribución uniforme, normal o laplace con media cero y varianza arbitraria), luego normalice alternativamente filas y columnas a , terminando con la normalización de fila. Esto parece converger al resultado deseado con bastante rapidez (por ejemplo, para y , la varianza de la longitud de la columna es típicamente ~ después de iteraciones), pero no estoy seguro si puedo depender de esta rápida tasa de convergencia en general (para varias dimensiones de matriz y distribuciones de elementos iniciales). ${\rm length} = 1$ $R=40$ $C=80$ $~0.00001$ $2$

Mi pregunta es esta: ¿hay alguna manera de lograr el resultado deseado ( , ) directamente sin iterar entre normalización de fila / columna? Por ejemplo, algo así como el algoritmo para normalizar un vector aleatorio (inicializar elementos aleatoriamente, medir la suma de valores cuadrados, luego escalar cada elemento por un escalar común). Si no, ¿hay una caracterización simple para la tasa de convergencia (por ejemplo, iteraciones numéricas hasta el error ) del método iterativo descrito anteriormente? ${\rm row \ lengths} = 1$ ${\rm column \ lengths} = \sqrt{\frac{R}{C}}$ $< \epsilon$

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

Esto es bastante similar al algoritmo Sinkhorn-Knopp, también conocido alternativamente como ajuste proporcional iterativo.

cardenal

Además, debe definir qué quiere decir con matrices "aleatorias". Por ejemplo, el procedimiento que describa no producirá (casi indudablemente) matrices aleatorias uniformemente sobre el espacio deseado.

cardenal

@cardinal Buen punto. Pero tenga en cuenta que al menos puede lograr distribuciones idénticas (marginales) para todos los componentes mediante la multiplicación posterior por un par de matrices de permutación aleatorias (para organizar aleatoriamente tanto filas como columnas).

whuber

@whuber: Sí, aunque la distribución conjunta aún podría ser bastante extraña. Por "post multiplicación" supongo que se refiere a multiplicar a la izquierda y a la derecha "post-convergencia" (en lugar de, por ejemplo, multiplicar a la derecha).

cardenal

En realidad, después de pensarlo un poco, creo que su algoritmo es exactamente el algoritmo Sinkhorn-Knopp con una modificación muy pequeña. Deje que

sea su matriz original y deje que

sea una matriz del mismo tamaño tal que

. Luego, su algoritmo es equivalente a aplicar Sinkhorn-Knopp a

, en donde en el paso final a recuperar su forma deseada mediante la adopción de

X

$X$

Y

$Y$

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

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

Y

$Y$

. Se garantiza que Sinkhorn-Knopp converja, excepto en circunstancias bastante patológicas. Leerlo debería ser muy útil.

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

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

cardenal

Como @cardinal dijo en un comentario:

En realidad, después de pensarlo un poco, creo que su algoritmo es exactamente el algoritmo Sinkhorn-Knopp con una modificación muy pequeña. Deje que X sea su matriz original y deje que Y sea una matriz del mismo tamaño tal que Y i j = X 2 i j . Luego, su algoritmo es equivalente a aplicar Sinkhorn-Knopp a Y , en donde en el paso final a recuperar su forma deseada mediante la adopción de X i j = s g n ( X i j ) $X$ $Y$ $Y_{ij}=X^2_{ij}$ $Y$ $\hat{X}_{ij}=sgn(X_{ij})\sqrt{Y_{ij}}$

... parece que el algoritmo iterativo que sugerí en la pregunta original es muy similar al algoritmo Sinkhorn-Knopp. Curiosamente, también parece muy similar al ajuste proporcional iterativo (IPF), que, como se describe en la página de Wikipedia de IPF, está relacionado con el método de Newton y la maximización de expectativas (todos tienen el mismo límite).

Estos métodos iterativos a menudo se aplican a problemas que carecen de una solución de forma cerrada, por lo que supongo tentativamente que la respuesta a la pregunta es negativa: no hay forma de lograr la solución deseada sin la iteración de fila / columna.

Tyler Streeter
fuente

(+1) Por su continuo interés en esta pregunta y su seguimiento independiente. :-)

cardenal

Matrices aleatorias con restricciones en la longitud de la fila y la columna

Respuestas: