计算科学 - 大密集低秩分配问题 - 吾爱随笔录

计算科学优化

2021-12-15 08:40:54

有没有一种相当便宜的方法来解决大的、密集的、低等级的分配问题 $\max_\pi \sum_i A_{\pi i,i}$ ，在哪里 $\pi$ 运行在所有 permutations.of $1:n$ ?

这里 $A$ 是一个 $n\times n$ 低秩矩阵 $r$ . 典型尺寸为 $n=10000~~$ （可能更大）， $r=15$ .

1个回答

自从 $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}.$ （这个量也称为Frobenius 积，

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

$P_{\pi}R_1:R_2$ ）。

这个想法并没有消除必须通过所有排列和蛮力搜索所有 Frobenius 产品的最大值的负担，实际上它具有与显式计算相同的算术复杂性 $A=R_1R_2^T$ . 但是，它的内存要求要低得多，因为您不必实际形成 $A$ .

其它你可能感兴趣的问题