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.

  • 5
    $\begingroup$ 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? $\endgroup$
    – Kirill
    Nov 16, 2015 at 19:50
  • $\begingroup$ Define fast? Do you mean in a vectorized way without looping over the whole matrix $-XY^T$? $\endgroup$
    – nluigi
    Nov 17, 2015 at 17:24
  • $\begingroup$ Computational complexity lower than $\mathbb{O}(m^2k)$. $\endgroup$
    – Gil
    Nov 17, 2015 at 21:54
  • 1
    $\begingroup$ NIPS'16 paper that might be relevant papers.nips.cc/paper/6246-orthogonal-random-features $\endgroup$
    – Memming
    Feb 21, 2017 at 13:50
  • 1
    $\begingroup$ I looked into the paper, it is very helpful. Thanks! @Memming $\endgroup$
    – Gil
    Feb 28, 2017 at 12:15

1 Answer 1


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.

  • $\begingroup$ Good idea. Small detail: that $O(n^2)$ should be something like $O((\|X\|\|Y\|)^2)$ instead. $\endgroup$ Dec 24, 2017 at 9:47
  • $\begingroup$ @FedericoPoloni, I agree. If you could introduce a more appropriate notation than using the norms of matrices, I would be happy to update. $\endgroup$ Dec 24, 2017 at 10:03
  • $\begingroup$ Well, using norms looks appropriate enough to me, but if you prefer you can write it as $O(\max(|XY^T|)^2)$. $\endgroup$ Dec 24, 2017 at 10:07
  • $\begingroup$ ok, updated it. $\endgroup$ Dec 30, 2017 at 10:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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