# Fast computation of component-wise $\exp(-XY^T)G$ for random $G$

I have the following question:

Suppose I have two matrices $X, Y$ both of size $m\times p$ and a random i.i.d Gaussian matrix $G$ of size $m \times k$, $m\gg p>k$.

Is there a fast way to compute $\exp(-XY^T)G$? Perhaps by using the fact that both $X$ and $Y$ are much smaller than $XY^T$? Here, $\exp(\cdot)$ means entry-wise exponent (i.e. of $\textbf{each}$ entry of the matrix). Clearly, without the exponent, it's easy and can be done simply by $X(Y^TG)$, but the problem is that the element-wise exponent is no longer low rank.

The motivation for the question is multiplying a kernel of the form

$D_{ij}=\exp(-d_{ij})$ or $D_{ij}=\exp(-d_{ij}^2)$

with $d_{ij}=\Vert x_i-y_j \Vert$ and $x_i, y_i \in \mathbb{R}^p$ by a random matrix efficiently.

An approximated solution is also fine.

• I find the question clear (I don't have any ideas myself unfortunately), but the fact that the exponential is component-wise I think is going to mislead a lot of people - $\exp(A)$ is a very standard notation for matrix exponential, especially in the theory of ODEs and PDEs. Could you maybe rephrase the title a bit? – Kirill Nov 16 '15 at 19:50
• Define fast? Do you mean in a vectorized way without looping over the whole matrix $-XY^T$? – nluigi Nov 17 '15 at 17:24
• Computational complexity lower than $\mathbb{O}(m^2k)$. – Gil Nov 17 '15 at 21:54
• NIPS'16 paper that might be relevant papers.nips.cc/paper/6246-orthogonal-random-features – Memming Feb 21 '17 at 13:50
• I looked into the paper, it is very helpful. Thanks! @Memming – Gil Feb 28 '17 at 12:15

If approximations suffice, maybe we could begin by developing the $\exp$ operator as follows: $$\exp(Z) = \sum\limits_{k=0}^{\infty} \frac{Z^k}{k!} = 1+Z+\frac{Z^2}{2} + \frac{Z^3}{6} + \frac{Z^4}{24} + ...$$ Note that the power terms follow your element-wise notation and refer to the Hadamard powers, slightly abusing the standard conventions.
This gives possibilities for re-writing the expression: \begin{align} \exp{(-XY^T)}G &= \Big(I-XY^T+\frac{(XY^T)^2}{2} - \frac{(XY^T)^3}{6} + \frac{(XY^T)^4}{24} - ...\Big)G \\ &=G-XY^TG+\frac{(XY^T)^2G}{2} - \frac{(XY^T)^3G}{6} + \frac{(XY^T)^4G}{24} - ... \end{align} where $I$ is an appropriately sized identity matrix. If one could live with a first order approximations, then: \begin{align} \exp{(-XY^T)}G &= G-XY^TG+ O(max(|XY^T|)^2)\\ &\approx G-XY^TG = G-X(Y^TG) \end{align} resulting in an easier operation. For higher order approximations, you would like to work out the solution for the Hadamard power, which is probably a bit harder or I haven't seen an immediate solution yet.
• Good idea. Small detail: that $O(n^2)$ should be something like $O((\|X\|\|Y\|)^2)$ instead. – Federico Poloni Dec 24 '17 at 9:47
• Well, using norms looks appropriate enough to me, but if you prefer you can write it as $O(\max(|XY^T|)^2)$. – Federico Poloni Dec 24 '17 at 10:07