9
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ By $\pi i$ do you mean the product so that you're striding through the matrix for different $\pi$? $\endgroup$ – Bill Barth Mar 7 '13 at 14:24
  • $\begingroup$ $\pi$ runs over all permutations. $\endgroup$ – Arnold Neumaier Mar 8 '13 at 11:48
  • $\begingroup$ Shouldn't it be $A_{\pi(i),i}$ then? $\endgroup$ – Jack Poulson Mar 8 '13 at 20:41
  • $\begingroup$ @JackPoulson: $\i(i)$ and $\pi i$ are two different notations for the image of $i$ under the permutation $\pi$. $\endgroup$ – Arnold Neumaier Mar 11 '13 at 9:02
  • $\begingroup$ 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? $\endgroup$ – Michael Grant Mar 22 '13 at 16:14
3
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.