gran problema de asignación de bajo rango denso

¿Existe un método razonablemente barato para resolver el problema de asignación grande, denso y de bajo rango , donde ejecuta sobre todas las permutaciones. De ? $\max_\pi \sum_i A_{\pi i,i}$ $\pi$ $1:n$

Aquí es una matriz de bajo rango . Los tamaños típicos serían (posiblemente mucho más grande), . $A$ $n\times n$ $r$ $n=10000~~$ $r=15$

optimization Arnold Neumaier
fuente

Por ¿te refieres al producto para que estés avanzando a través de la matriz por diferentes ?

π i

$\pi i$

π

$\pi$

Bill Barth

π

$\pi$ recorre todas las permutaciones.

Arnold Neumaier

¿No debería ser entonces?

A_{π (i), i}

$A_{\pi(i),i}$

Jack Poulson

@JackPoulson: y son dos notaciones diferentes para la imagen de bajo la permutación .

\i (i)

$\i(i)$

π i

$\pi i$

i

$i$

π

$\pi$

Arnold Neumaier

¡Interesante pregunta! ¿Está buscando para explotar la estructura de bajo rango sólo para almacenamiento razones --- es decir, para salvar de tener que formar la matriz entera cuando se aplica un algoritmo de asignación tradicional? ¿O estás buscando una manera de explotar el rango bajo para acelerar la búsqueda?

Michael Grant

Respuestas:

Como con , tenemos donde es la matriz de permutación correspondiente a . $A=R_1R_2^T$ $R_1, R_2\in \mathbb{R}^{n \times r}$

\sum_{i} A_{π i, i} = \sum_{i} (P_{π} A)_{i, i} = trace (P_{π} R_{1} R_{2}^{T})

$\sum_i A_{\pi i, i} = \sum_i (P_{\pi} A)_{i, i} = \text{trace}(P_{\pi}R_1R_2^T)$

P_{π}

$P_{\pi}$

π

$\pi$

Para cualquier , la traza se puede calcular como (Esta cantidad también se conoce como $\pi$

trace (P_{π} R_{1} R_{2}^{T}) = \sum_{i} \sum_{k} (P_{π} R_{1})_{i, k} (R_{2}^{T})_{k, i} = \sum_{i, k} ((P_{π} R_{1}) \circ R_{2})_{i, k} .

$\text{trace}(P_{\pi}R_1R_2^T) = \sum_{i} \sum_{k} (P_{\pi}R_1)_{i,k} (R_2^T)_{k,i} = \sum_{i,k} ((P_{\pi}R_1)\circ R_2)_{i,k}.$ Producto Frobenius ,

P_{π} R_{1} : R_{2}

$P_{\pi}R_1:R_2$

Esta idea no quita la carga de tener que pasar por todas las permutaciones y la búsqueda de fuerza bruta para obtener el máximo de todos los productos Frobenius, y de hecho tiene la misma complejidad aritmética que computar explícitamente . Sin embargo, tiene requisitos de memoria mucho más bajos, ya que nunca tenga que formar en realidad . $A=R_1R_2^T$ $A$

Nico Schlömer
fuente