masalah tugas peringkat rendah padat tinggi

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

Di sini adalah matriks peringkat rendah . Ukuran tipikal adalah (mungkin jauh lebih besar), . $A$ $n\times n$ $r$ $n=10000~~$ $r=15$

optimization Arnold Neumaier
sumber

Dengan maksud Anda produk sehingga Anda sedang striding melalui matriks untuk berbeda ?

π i

$\pi i$

π

$\pi$

Bill Barth

π

$\pi$ menjalankan semua permutasi.

Arnold Neumaier

Bukankah seharusnya begitu?

A_{π (i), i}

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

Jack Poulson

@JackPoulson: dan adalah dua notasi yang berbeda untuk gambar bawah permutasi .

\i (i)

$\i(i)$

π i

$\pi i$

i

$i$

π

$\pi$

Arnold Neumaier

Pertanyaan menarik! Apakah Anda mencari untuk mengeksploitasi struktur peringkat rendah hanya untuk alasan penyimpanan --- yaitu, untuk menyelamatkan dari keharusan membentuk seluruh matriks ketika menerapkan algoritme penugasan tradisional? Atau apakah Anda mencari cara untuk mengeksploitasi peringkat rendah untuk mempercepat pencarian?

Michael Grant

Jawaban:

Karena dengan , kami memiliki di mana adalah matriks permutasi yang sesuai dengan . $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$

Untuk apa pun , jejak dapat dihitung sebagai (Kuantitas ini juga dikenal sebagai produk 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$

Ide ini tidak mengambil beban harus melalui semua permutasi dan brute-force pencarian untuk maksimum dari semua produk Frobenius, dan pada kenyataannya adalah memiliki kompleksitas aritmatika sama dengan eksplisit komputasi . Namun, ia memiliki persyaratan memori yang jauh lebih rendah karena Anda tidak pernah harus benar-benar membentuk . $A=R_1R_2^T$ $A$

Nico Schlömer
sumber