2
$\begingroup$


Let $Y,Z$ be $n\times k$ matrices and assume all columns have been standardized such that their means are zero and variances 1. I seek an $n\times n$ permutation matrix $P$ such that

$$\left\Vert Y^{T}P^{T}Z-\Omega\right\Vert$$

is small, where $\Omega$ is a specified cross-correlation matrix. For intuition, you might consider matching $n$ pairs of individuals up to form couples that are correlated on $k$ traits (represented by $Y$, $Z$) such that a particular cross-couple correlation structure $\Omega$ is induced.


When the above norm $\left\Vert \cdot\right\Vert $ is the Frobenius norm, this is the quadratic assignment problem (QAP):

$$\min_{P\in\mathcal{P}}\ \mathrm{tr\,}YY^{T}P^{T}ZZ^{T}P-2\mathrm{tr\,}P^T Z\Omega Y^T,$$

which seems to be a particularly nasty NP-hard problem. In practice, I don't really care what norm $\left\Vert \cdot\right\Vert $ is: given a finite amount of computation, I'd just as soon get closer to the optimal solution to a similar problem. In my application $n$ is large, so I presume I'll be solving a relaxation of the above (e.g., solve over the space of doubly stochastic matrices). My question is, is there any choice of $\left\Vert \cdot\right\Vert $ for which this problem becomes substantially easier in terms of finding a "good enough" solution?

Improve this question
$\endgroup$
5
  • $\begingroup$ Seems quite nasty even for $k=1$ where there is no choice of the norm (all norms are the same up to a constant factor). What would you consider a "good enough solution" in that case? $\endgroup$
    – fedja
    Commented Apr 6, 2022 at 22:37
  • $\begingroup$ @fedja For $k=1$ there is a heuristic solution that works very well when $Y$ and $Z$ are drawn from Gaussian distributions: Order $Y$ and $Z$ on a linear combination of their values and independent Gaussian noise. It's relatively straightforward to figure out what coefficients for the linear combination will yield the desired value of $\Omega$. This is admittedly a far less general problem, but I imagine similar solutions are available for other forms of $Y,Z$. $\endgroup$
    – nothing
    Commented Apr 6, 2022 at 23:22
  • $\begingroup$ Unfortunately, though this works great for $k=1$, it can only be used for particular values of $\Omega$ when $k>1$. E.g., when $Y,Z$ have orthogonal columns, this can only be used for constant matrices of the form $\Omega = \alpha 1_k 1_k ^T$... $\endgroup$
    – nothing
    Commented Apr 6, 2022 at 23:23
  • $\begingroup$ Have you considered using the (vectorised) $1$-norm and writing it as an integer program? $\endgroup$
    – Rodrigo de Azevedo
    Commented Apr 7, 2022 at 11:49
  • $\begingroup$ Somewhat related $\endgroup$
    – Rodrigo de Azevedo
    Commented Apr 7, 2022 at 11:52

0

Reset to default

You must log in to answer this question.