большая плотная задача низкого ранга

Есть ли достаточно дешевый метод для решения большой, плотной задачи низшего ранга $\max_\pi \sum_i A_{\pi i,i}$ где $\pi$ пробегает все перестановки. $1:n$ ?

Здесь $A$ - матрица $n\times n$ низкого ранга $r$ . Типичные размеры будут $n=10000~~$ (возможно, намного больше), $r=15$ .

optimization Арнольд Ноймайер
источник

Под

π i

$\pi i$ имею в виду продукт, чтобы вы проходили матрицу по разным

π

$\pi$ ?

Билл Барт

π

$\pi$ пробегает все перестановки.

Арнольд Ноймайер

Разве это не

A_{π (i), i}

$A_{\pi(i),i}$ тогда?

Джек Поулсон

@JackPoulson:

\i (i)

$\i(i)$ и

π i

$\pi i$ - две разные записи для образа

i

$i$ при перестановке

π

$\pi$ .

Арнольд Ноймайер

Интересный вопрос! Вы хотите использовать низкоранговую структуру только по причинам хранения - то есть, чтобы избежать необходимости формировать всю матрицу при применении традиционного алгоритма назначения? Или вы ищете способ использовать низкое звание для ускорения поиска?

Майкл Грант

Ответы:

Поскольку с , мы имеем где - матрица перестановок, соответствующая . $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$

Для любого трасса может быть вычислена как (Это количество также известно как произведение Фробениуса , ). $\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$

Эта идея не отнимает бремя, чтобы пройти через все перестановки и перебор поиск максимума всех продуктов Фробениуса, и на самом деле имеет ту же арифметическую сложность, явно вычисляя . Тем не менее, она имеет гораздо более низкие требования к памяти , так как вы никогда не должны фактически формировать . $A=R_1R_2^T$ $A$

Нико Шлёмер
источник