grand problème d'affectation dense de bas rang

$\max_\pi \sum_i A_{\pi i,i}$ $\pi$ $1:n$

Ici est une matrice de bas rang . Les tailles typiques seraient (peut-être beaucoup plus grandes), . $A$ $n\times n$ $r$ $n=10000~~$ $r=15$

optimization Arnold Neumaier
la source

Par vous voulez dire le produit afin que vous parcouriez la matrice pour différents ?

π i

$\pi i$

π

$\pi$

Bill Barth

π

$\pi$ parcourt toutes les permutations.

Arnold Neumaier

Cela ne devrait-il pas être alors?

A_{π (i), i}

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

Jack Poulson

@JackPoulson: et sont deux notations différentes pour l'image de sous la permutation .

\i (i)

$\i(i)$

π i

$\pi i$

i

$i$

π

$\pi$

Arnold Neumaier

Question interessante! Cherchez-vous à exploiter la structure de bas rang uniquement pour des raisons de stockage , c'est-à-dire pour éviter d'avoir à former la matrice entière lors de l'application d'un algorithme d'affectation traditionnel? Ou cherchez-vous un moyen d'exploiter le bas rang pour accélérer la recherche?

Michael Grant

Réponses:

Puisque avec , nous avons où est la matrice de permutation correspondant à . $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$

Pour tout , la trace peut être calculée comme (Cette quantité est également connue sous le nom de produit Frobenius , ). $\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}.$

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

$P_{\pi}R_1:R_2$

Cette idée ne supprime pas le fardeau d'avoir à passer par toutes les permutations et la recherche de la force brute pour le maximum de tous les produits Frobenius, et en fait est a la même complexité arithmétique de calcul explicite . Cependant, il a beaucoup plus faibles besoins en mémoire puisque vous ne devez former réellement . $A=R_1R_2^T$ $A$

Nico Schlömer
la source