duży, gęsty problem przydziału niskiej rangi

Czy istnieje rozsądnie tania metoda rozwiązania dużego, gęstego problemu przypisania niskiej rangi , gdzie działa na wszystkich permutacjach. ? $\max_\pi \sum_i A_{\pi i,i}$ $\pi$ $1:n$

Tutaj $A$ jest $n\times n$ macierzą niskiego stopnia $r$ . Typowe rozmiary to $n=10000~~$ (prawdopodobnie znacznie większy), $r=15$ .

optimization Arnold Neumaier
źródło

Przez na myśli produkt, który kroczysz przez matrycę dla różnych ?

π i

$\pi i$

π

$\pi$

Bill Barth

π

$\pi$ działa na wszystkich permutacjach.

Arnold Neumaier

Czy nie powinno to być ?

A_{π (i), i}

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

Jack Poulson,

@JackPoulson: i to dwie różne notacje dla obrazu w permutacji .

\i (i)

$\i(i)$

π i

$\pi i$

i

$i$

π

$\pi$

Arnold Neumaier

Interesujące pytanie! Czy chcesz wykorzystać niskopoziomową strukturę tylko z powodów związanych z przechowywaniem - to znaczy, aby uniknąć konieczności tworzenia całej macierzy przy zastosowaniu tradycyjnego algorytmu przypisywania? A może szukasz sposobu na wykorzystanie niskiej rangi w celu przyspieszenia wyszukiwania?

Michael Grant

Odpowiedzi:

Ponieważ z , mamy gdzie jest macierzą permutacji odpowiadającą . $A=R_1R_2^T$ $R_1, R_2\in \mathbb{R}^{n \times r}$

\sum_{ja} {ZA}_{π ja, ja} = \sum_{ja} ({P.}_{π} ZA)_{ja, ja} = ślad ({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$

Dla każdego ślad można obliczyć jako (Ta ilość jest również znana jako produkt Frobenius , ). $\pi$

ślad ({P.}_{π} R_{1} R_{2)}^{T.}) = \sum_{ja} \sum_{k} ({P.}_{π} R_{1})_{ja, k} (R_{2)}^{T.})_{k, ja} = \sum_{ja, k} (({P.}_{π} R_{1}) \circ R_{2)})_{ja, 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$

Pomysł ten nie odbiera ciężar konieczności przechodzenia przez wszystkich permutacji i brute-force poszukiwaniu maksimum wszystkich produktów Frobenius, aw rzeczywistości to ma taką samą średnią arytmetyczną złożoności obliczeniowej jako jawnie . Jednakże, ma znacznie mniejsze zapotrzebowanie na pamięć, ponieważ nie musisz faktycznie tworzą . $A=R_1R_2^T$ $A$

Nico Schlömer
źródło