# large dense low rank assignment problem

Is there a reasonably cheap method to solve the large, dense, low rank assignment problem $\max_\pi \sum_i A_{\pi i,i}$, where $\pi$ runs over all permutations.of $1:n$?

Here $A$ is an $n\times n$ matrix of low rank $r$. Typical sizes would be $n=10000~~$ (possibly much larger), $r=15$.

• By $\pi i$ do you mean the product so that you're striding through the matrix for different $\pi$? – Bill Barth Mar 7 '13 at 14:24
• $\pi$ runs over all permutations. – Arnold Neumaier Mar 8 '13 at 11:48
• Shouldn't it be $A_{\pi(i),i}$ then? – Jack Poulson Mar 8 '13 at 20:41
• @JackPoulson: $\i(i)$ and $\pi i$ are two different notations for the image of $i$ under the permutation $\pi$. – Arnold Neumaier Mar 11 '13 at 9:02
• Interesting question! Are you looking to exploit the low-rank structure just for storage reasons---that is, to save from having to form the entire matrix when applying a traditional assignment algorithm? Or are you looking for a way to exploit the low rank to accelerate the search? – Michael Grant Mar 22 '13 at 16:14

Since $A=R_1R_2^T$ with $R_1, R_2\in \mathbb{R}^{n \times r}$, we have $$\sum_i A_{\pi i, i} = \sum_i (P_{\pi} A)_{i, i} = \text{trace}(P_{\pi}R_1R_2^T)$$ where $P_{\pi}$ is the permutation matrix corresponding to $\pi$.
For any $\pi$, the trace can be computed as $$\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}.$$ (This quantity is also known as Frobenius product, $P_{\pi}R_1:R_2$).
This idea doesn't take away the burden of having to go through all permutations and brute-force search for the maximum of all Frobenius products, and in fact is has the same arithmetic complexity as explicitly computing $A=R_1R_2^T$. However, it has much lower memory requirements since you never have to actually form $A$.