grande problema de atribuição de classificação baixa e densa

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

Aqui $A$ é uma matriz $n\times n$ de baixo nível $r$ . Os tamanhos típicos seriam $n=10000~~$ (possivelmente muito maiores), $r=15$ .

optimization Arnold Neumaier
fonte

Por

π i

$\pi i$ , você quer dizer o produto para que você esteja caminhando pela matriz para diferentes

π

$\pi$ ?

Bill Barth

π

$\pi$ executa todas as permutações.

Arnold Neumaier

Não deveria ser

A_{π (i), i}

$A_{\pi(i),i}$ então?

precisa

@JackPoulson:

\i (i)

$\i(i)$ e

π i

$\pi i$ são duas notações diferentes para a imagem de

i

$i$ sob a permutação

π

$\pi$ .

Arnold Neumaier 11/03/2013

Pergunta interessante! Você está procurando explorar a estrutura de baixo escalão apenas por razões de armazenamento - ou seja, para evitar a formação de toda a matriz ao aplicar um algoritmo de atribuição tradicional? Ou você está procurando uma maneira de explorar a classificação baixa para acelerar a pesquisa?

22613 Michael Grant

Respostas:

Como com , temos que é a matriz de permutação correspondente 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 qualquer , o rastreamento pode ser calculado como (Essa quantidade também é conhecida como produto 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$

Esta ideia não tirar o fardo de ter que passar por todas as permutações e de força bruta busca do máximo de todos os produtos Frobenius, e de fato é tem a mesma complexidade aritmética como computação explicitamente . No entanto, tem requisitos de memória muito mais baixos desde que você nunca tem que realmente formam . $A=R_1R_2^T$ $A$

Nico Schlömer
fonte